GeomTop Seminar: "Chromatic number of Kneser hypergraphs and a conjecture of Frick"

---

This will be a report of a recent joint work with Soheil Azarpendar. For integers n, k, r where n>kr-1 The Kneser hypergraph KG^r(n,k) was defined by Lovasz, Alon and Frankl as the r-uniform hypergraph with all k-subsets of {1,...,n} as vertices and its hyperedges are all r-subsets {A_1,...,A_r} of vertices that are pairwise disjoint. It was proved by them using topological methods that its chromatic number is the ceiling of (n-r(k-1))/(r-1).
Ziegler conjectured that if we take the induced sub hypergraph whose vertices are all r-stable (i.e subsets that for any two distinct elements i and j in them r-1< |i-j|2. In this talk we prove a weaker version of this conjecture, due to Frick et al, that states if {P_1,...,P_t} is a partition of {1,..,n} where the size of each P_i is at most r and we take the induced sub hypergraph of KG^r(n,k) whose vertices are those k-subsets that have at most one element from each P_i then we still get the same chromatic number. Our proof for this conjecture is combinatorial and uses Z_p Tucker lemma. If time permits some topological methods related to similar problems will be explained.

---

Download ICS Download invitation