Dense minimizer conjecture for induced subgraphs of the Kneser graph

About 3 years old · traced to

Let n,k,m∈Nn,k,m\in\mathbb{N} satisfy (nk)/2≤m≤(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.

References

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.