16
$\begingroup$

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is the single reason they are called perfect? Or is it just a aesthetic preference by Berge?

$\endgroup$
  • $\begingroup$ Presumably, he originally called them parfait and not perfect. It does mean almost the same thing. Possibly some French speaker here could tell us whether parfait in French is slightly less absolute in meaning than perfect in English. $\endgroup$ – Peter Shor Nov 21 '12 at 12:30
  • 6
    $\begingroup$ The meaning is exactly the same in our language as in yours. $\endgroup$ – Anthony Labarre Nov 21 '12 at 12:49
16
$\begingroup$

perfect graphs were first motivated by information transmission theory originating with Shannon ie Shannon Capacity of graphs. they are called "perfect" by Berge because they can be used to model a noiseless or "perfect" information channel wrt transposition errors in transmission called "confounding". from intro in [3] which also has a very detailed history in the 1st chapter cowritten by Berge.

When Claude Berge defined perfect graphs in 1961, he was motivated by a very practical problem: how do we maximize the rate at which information is sent through a (noisy) transmission channel while avoiding the introduction of errors because of the physical imperfections of the system?

[1] C. Berge, The history of the perfect graphs, Southeast Asian Bull. Math. 20, No.1 (1996) 5-10.
[2] C. Berge, Motivations and history of some of my conjectures, Discrete Mathematics 165-166 (1997) 61-70.
[3] Perfect Graphs by Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), J.L.R. Alfonsin (Author). Wiley. Ch1, Origins and Genesis by Berge & Ramírez-Alfonsín

$\endgroup$
  • 11
    $\begingroup$ I suspect this answer could use more explanation. For perfect graphs, the single-symbol zero-error capacity (encoding the information without using block codes) is equal to the asymptotic zero-error capacity. Thus, you can easily calculate the zero-error capacity, and it is obtainable using the simplest possible code. One of Lovász's celebrated results was calculating this capacity for the five-cycle, the simplest non-perfect graph. And unless progress has been made in the last couple of years, we still don't know what it is for the seven-cycle. $\endgroup$ – Peter Shor Nov 21 '12 at 18:13
  • $\begingroup$ I like the succinctness of the answer, in conjunction with the citations. This is a topic on the periphery for me, and this short answer is quite useful as an intro to a complex subject. $\endgroup$ – DukeZhou Jan 10 '18 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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