Combinatorial topology and the coloring of Kneser graphs

Martin Kneser

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

Sujets

• Meunier
• Kneser
• Combinatorial topology
• Kneser graph
• Petersen graph

Informations

• Publié par: chaeh
• Nombre de lectures: 15
• Langue: English

Extrait

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.