 # Combinatorial topology and the coloring of Kneser graphs

- English
32 Pages

Description

Niveau: Supérieur
Combinatorial topology and the coloring of Kneser graphs Frederic Meunier May 4, 2011 Ecole des Ponts, France Ecole des Ponts, CERMICS

• probably hold

• combinatorial topology

• kneser graphs

• petersen graph

• nk ?

• graph kg

• both inequalities

• ecole des ponts

Subjects

##### Petersen graph

Informations

Report a problem Combinatorial
topology and the graphs
Ecole des Ponts, France
EcoleedsPonts,
Fre´d´ericMeunier
C
May 4, 2011
ERMCIS
coloring
of
Kneser Martin Kneser proposed in 1955 the following problem (“Aufgabe 360”):
Let k and n be two natural numbers, 2k n ; let N be a set with n elements, N k the set of all subsets of N with exactly k elements; let f : N k M with the property f(K 1 ) 6 = f(K 2 ) if K 1 K 2 = . Let m(k , n) be the minimal number of elements in M such that f exists. Prove that there are m 0 (k) and n 0 (k) such that m(k , n) = n m 0 (k) for n n 0 (k) ; here m 0 (k) 2k 2 and n 0 (k) 2k 1 ; both inequalities probably hold with equality.
EcoleedsoPtn,sECMRICS The
Kneser graphs
Kneser graph KG(n , k) :
vertex set V = { A [n] :
pairs
of
disjoint
elements
of
Ecole des Ponts, CERMICS
| A | = k }
V
as
edge
set.
en expand_more