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

From papers

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 A0A\mathcal{A}_0\subseteq\mathcal{A} and B0B\mathcal{B}_0\subseteq\mathcal{B} with

A0=B0ckn,|\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.