Holroyd–Johnson conjecture for intersecting k-separated sets

About 24 years old · traced to

Let [n]k(r)[n]^{(r)}_k denote the collection of kk-separated rr-sets in [n](r)[n]^{(r)}: sets A={a1,…,ar}A=\{a_1,\dots,a_r\} with a1<a2<⋯<ara_1<a_2<\cdots<a_r satisfying ai+1−ai>ka_{i+1}-a_i>k for i=1,…,ri=1,\dots,r, where ar+1=a1+na_{r+1}=a_1+n. Let nn, kk, and rr be positive integers satisfying

n≥(k+1)r.n\geq (k+1)r.

For an intersecting family A⊆[n]k(r)\mathcal{A}\subseteq[n]^{(r)}_k, define the star at 11 by

A1∗={A∈[n]k(r):1∈A}.\mathcal{A}_1^*=\{A\in[n]^{(r)}_k:1\in A\}.

Holroyd and Johnson's conjecture. If A⊆[n]k(r)\mathcal{A}\subseteq[n]^{(r)}_k is intersecting, then

∣A∣≤∣A1∗∣.|\mathcal{A}|\leq|\mathcal{A}_1^*|.

The conjecture asserts an Erdős–Ko–Rado-type bound for intersecting families of kk-separated sets. The supplied text does not state whether it has been resolved; the status is therefore recorded as open.

References

Primary source

John Talbot, “Intersecting Families of Separated Sets”, arXiv:math/0211314 (2002).

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.