Description
When is it true that if we r-color all ordered pairs of disjoint k-element subsets of [n], then there are three pairwise disjoint sets A,B,C such that (A,B) and (B,C) receive the same color? If k=1, this is some sort of Shift graph construction, and a similar notion is known as the arc-chromatic number. However, for larger k our definition is more restrictive, resembling Kneser graphs.
In general, define KSh(p,n,k) as the simple graph whose vertices are ordered (p-1)-tuples of pairwise disjoint k-sets of [n], and two vertices are adjacent if they have the form (A1,..,A{p-1}) and (A2,..,Ap) where A1 and Ap are also disjoint. Our main result is that the chromatic number of KSh(p,n,k) goes to infinity as n-pk goes to infinity or every fixed prime p. Our proof is similar in spirit to the proof of the Erdős-Szekeres theorem on monotone sequences, but it uses the topological Zp-Tucker lemma.
The new result implies lower bounds for the chromatic number of Kneser hypergraphs (weaker than already known), but not vice versa, afaik. I used the theorem to derive some new results in Euclidean Ramsey theory (which are not implied by the recent characterization by OpenAI) and I expect it to have further applications. For the full paper, see https://arxiv.org/abs/2608.10865 <https://arxiv.org/abs/2608.10865>.
In memory of my co-author, ChatGPT-5.5, who will leave us before next Thursday.
ZOOOOM!
https://zoom.us/j/2961946869?omn=98245035028
(If we are able to start it without Ervin.)