Kneser,s Conjecture
المؤلف:
Godsil, C. and Royle, G
المصدر:
Algebraic Graph Theory. New York: Springer-Verlag
الجزء والصفحة:
...
12-1-2022
1281
Kneser's Conjecture
A combinatorial conjecture formulated by Kneser (1955). It states that whenever the 
-subsets of a 
-set are divided into 
classes, then two disjoint subsets end up in the same class.
Lovász (1978) gave a proof based on graph theory. In particular, he showed that the Kneser graph, whose vertices represent the 
-subsets, and where each edge connects two disjoint subsets, is not 
-colorable. More precisely, his results says that the chromatic number is equal to 
, and this implies that Kneser's conjecture is always false if the number of classes is increased to 
.
An alternate proof was given by Bárány (1978).
REFERENCES
Bárány, I. "A Short Proof of Kneser's Conjecture." J. Comb. Th. A 25, 325-326, 1978.
Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 160, 2001.
Kneser, M. "Aufgabe 300." Jahresber. Deutsch. Math.-Verein 58, 1955.
Lovász, L. "Kneser's Conjecture, Chromatic Numbers and Homotopy." J. Comb. Th. A 25, 319-324, 1978.
الاكثر قراءة في نظرية المجموعات
اخر الاخبار
اخبار العتبة العباسية المقدسة
