3
$\begingroup$

This question is in the reverse direction of a common MO question. Instead of being faced with a formal definition and asking for some intuition for the definition, I have a concept with I understand intuitively but where I do not know a definition.

I have been in interested in the proofs of the 4-colour theorem which uses the notion of a "discharge rule". This evening I was discussing discharge rules with a speaker who was not familiar with the proofs of the 4-colour theorem and was embarrassed that I could not give a definition. I have seen examples of discharge rules and I feel I would know one if I saw one. However I have no recollection of reading a definition. Did I overlook a definition in one of the papers? and if not, could someone complete the following sentence:

Definition A discharge rule is ...

$\endgroup$
4
  • $\begingroup$ Is a rule with which the charge of a vertex/face is redistributed to other vertices/faces? $\endgroup$
    – Jernej
    May 9, 2012 at 19:13
  • $\begingroup$ @Jernej Yes, it is, and that would be a good starting point in a face to face discussion as it describes how discharge rules are used. However the definition needs to be more restrictive. $\endgroup$ May 9, 2012 at 20:13
  • $\begingroup$ Well, first you might want to define rigorously what is a 'charged graph', and then the set $CG$ of charged graphs comes with a map to the set $G$ of graphs. There will probably be interesting functions from $CG$ to the integers (or poss. rationals) giving invariants of a charged graph. Or maybe they will be maps to $\bigoplus \mathbb{Z}$. A discharge rule (hand-waving alert!) could be an endomorphism of $CG$ such that invariants are preserved, or decreased, or something. $\endgroup$
    – David Roberts
    May 10, 2012 at 4:50
  • $\begingroup$ @David. Yes, we need to define a charged graph but I don't see any issues there. $\endgroup$ May 10, 2012 at 9:51

1 Answer 1

1
$\begingroup$

I'm not sure there is a "definition". It is a name for a class of proof techniques so it is defined by the examples that people have given that name to. A good place to begin would be the exposition of Hlineny, here: http://kam.mff.cuni.cz/~spring/2000/texts/hlineny.ps .

$\endgroup$
3
  • $\begingroup$ The article you link to reminds me that this proof technique does more than prove the four colour theorem. That's a good point. $\endgroup$ May 10, 2012 at 9:45
  • $\begingroup$ When you say there is no "definition"; do you mean there is no published definition? (which seems to be true) or, do you mean more than that? Are you saying there is a reason there is no definition? or that I am misguided in asking for a definition? or ....? I am surprised that this key concept has no definition just plenty of examples. $\endgroup$ May 10, 2012 at 9:51
  • $\begingroup$ The discharge method is one where you define "charges" on the bits of a graph (usually vertices or faces) and then move them around in precise ways. People invent these precise ways and call them "discharge rules". So the definition can depend on who defined it. There isn't a single definition shared by everyone who uses the expression. $\endgroup$ May 11, 2012 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.