The bipartite Erdős–Hajnal conjecture for separately k-intersecting curve families

At least 6 years old · documented by

A family of curves is kk-intersecting if any two curves in the family intersect in at most kk points. Let A\mathcal{A} and B\mathcal{B} be two families of nn curves each.

Bipartite curve-family conjecture. For every kk there is a constant ck>0c_k>0 such that there are subfamilies A0⊆A\mathcal{A}_0\subseteq\mathcal{A} and B0⊆B\mathcal{B}_0\subseteq\mathcal{B} with

∣A0∣=∣B0∣≥ckn,|\mathcal{A}_0|=|\mathcal{B}_0|\ge c_k n,

such that either every α∈A0\alpha\in\mathcal{A}_0 intersects every β∈B0\beta\in\mathcal{B}_0, or every α∈A0\alpha\in\mathcal{A}_0 is disjoint from every β∈B0\beta\in\mathcal{B}_0.

The surrounding discussion shows that this would strengthen known results for intersection graphs of kk-intersecting curves by requiring only the two families separately to be kk-intersecting. It is open in the paper's context.

References

Primary source

Dániel Korándi, János Pach and István Tomon, “Large homogeneous submatrices”, arXiv:1903.06608 (2020).

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.