Combinatorial topology and the coloring of Kneser graphs

-

English
32 Pages
Read an excerpt
Gain access to the library to view online
Learn more

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

Informations

Published by
Reads 15
Language English
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.