Dense minimizer conjecture for induced subgraphs of the Kneser graph

Let n,k,mNn,k,m\in\mathbb{N} satisfy (nk)/2m(nk)\binom{n}{k}/2\leq m\leq\binom{n}{k}, and let tt be the smallest natural number such that (tk)m\binom{t}{k}\geq m. For a family F([n]k)\mathcal{F}\subseteq\binom{[n]}{k}, write Δ(F)\Delta(\mathcal{F}) for the maximum degree of the induced subgraph of the Kneser graph on F\mathcal{F}.

Dense minimizer conjecture. There exists a family

F([t]k)\mathcal{F}\subseteq\binom{[t]}{k}

of size F=m|\mathcal{F}|=m such that Δ(F)\Delta(\mathcal{F}) is minimum among all subfamilies of ([n]k)\binom{[n]}{k} of size mm. This is the dense-case analogue of the minimization problem studied in the paper; it is presented as a conjecture and no resolution is given here.

Sources & referencesView supporting material

Primary source

Hou Tin Chau, David Ellis, Ehud Friedgut and Noam Lifshitz, “On the maximum degree of induced subgraphs of the Kneser graph”, arXiv:2312.06370 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.