Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ...

share|improve this question
    
Is a rule with which the charge of a vertex/face is redistributed to other vertices/faces? –  Jernej May 9 '12 at 19:13
    
@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. –  Bruce Westbury May 9 '12 at 20:13
    
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. –  David Roberts May 10 '12 at 4:50
    
@David. Yes, we need to define a charged graph but I don't see any issues there. –  Bruce Westbury May 10 '12 at 9:51

1 Answer 1

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 .

share|improve this answer
    
The article you link to reminds me that this proof technique does more than prove the four colour theorem. That's a good point. –  Bruce Westbury May 10 '12 at 9:45
    
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. –  Bruce Westbury May 10 '12 at 9:51
    
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. –  Brendan McKay May 11 '12 at 1:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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