Borg's sum conjecture for cross-intersecting hereditary subfamilies

At least 14 years old · documented by

Let [n]={1,…,n}[n]=\{1,\ldots,n\}, let H≠{∅}\mathcal{H}\neq\{\emptyset\} be a hereditary subfamily of 2[n]2^{[n]}, and let A1,…,Ak\mathcal{A}_1,\ldots,\mathcal{A}_k be cross-intersecting subfamilies of H\mathcal{H}. A largest star S\mathcal{S} of H\mathcal{H} is a star having maximum size among the stars of H\mathcal{H}.

Borg's sum conjecture. If k≥n+1k\geq n+1, then

∑i=1k∣Ai∣\sum_{i=1}^k|\mathcal{A}_i|

is maximum when A1=⋯=Ak=S\mathcal{A}_1=\cdots=\mathcal{A}_k=\mathcal{S} for some largest star S\mathcal{S} of H\mathcal{H}.

The threshold k≥n+1k\geq n+1 is necessary in the examples given in the paper, and the conjecture is proved there for important classes of hereditary families, including families compressed with respect to an element.

References

Primary source

Peter Borg, “Cross-intersecting sub-families of hereditary families”, arXiv:1103.3858 (2011).

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.