Hilton–Milner-type conjecture for nontrivial Erdős matching families

About 10 years old · traced to

Let n,k,sn,k,s be positive integers, and let F⊂([n]k)\mathcal F\subset {[n]\choose k} be a kk-uniform family. Write ν(F)\nu(\mathcal F) for its matching number and τ(F)\tau(\mathcal F) for its covering number. For i∈[k]i\in[k], let

Ai(k)(n,s):={A∈([n]k):∣A∩[(s+1)i−1]∣≥i},\mathcal A_i^{(k)}(n,s):=\Bigl\{A\in {[n]\choose k}:\bigl|A\cap[(s+1)i-1]\bigr|\ge i\Bigr\},

and define

H(k)(n,s):={H∈([n]k):H∩[s]≠∅}∪{[s+1,s+k]}−{H∈([n]k):H∩[s]={s}, H∩[s+1,s+k]=∅}.\mathcal H^{(k)}(n,s):=\Bigl\{H\in {[n]\choose k}:H\cap[s]\ne\emptyset\Bigr\}\cup\bigl\{[s+1,s+k]\bigr\}-\Bigl\{H\in {[n]\choose k}:H\cap[s]=\{s\},\ H\cap[s+1,s+k]=\emptyset\Bigr\}.

Hilton–Milner-type conjecture. If ν(F)=s\nu(\mathcal F)=s and τ(F)>s\tau(\mathcal F)>s, then

∣F∣≤max⁡{{∣Ai(k)(n,s)∣:i=2,…,k},∣H(k)(n,s)∣}.|\mathcal F|\le\max\Bigl\{\bigl\{|\mathcal A_i^{(k)}(n,s)|:i=2,\ldots,k\bigr\},|\mathcal H^{(k)}(n,s)|\Bigr\}.

This conjecture seeks the sharp bound for families with matching number exactly ss that are not covered by ss elements, generalizing the Hilton–Milner phenomenon; its resolution status is not specified in the source.

References

Primary source

Peter Frankl and Andrey Kupavskii, “Two problems on matchings in set families - in the footsteps of Erdős and Kleitman”, arXiv:1607.06126 (2018).

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.