Fox–Pach sharp edge bound conjecture for K_{t,t}-free string graphs

About 13 years old · traced to

For an integer t≥2t\geq 2, a graph is Kt,tK_{t,t}-free if it contains no complete bipartite subgraph with tt vertices in each part. Fox–Pach's sharp edge bound conjecture. Every Kt,tK_{t,t}-free string graph on nn vertices has at most

ct(log⁡t)nct(\log t)n

edges, for an absolute constant cc. The weaker linear bound is known with ct≤tclog⁡log⁡tc_t\leq t^{c\log\log t}, while this ctlog⁡tct\log t estimate is conjectured to be best possible.

References

Primary source

Jacob Fox and Janos Pach, “Applications of a new separator theorem for string graphs”, arXiv:1302.7228 (2013).

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.