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

From papers

For an integer t2t\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(logt)nct(\log t)n

edges, for an absolute constant cc. The weaker linear bound is known with cttcloglogtc_t\leq t^{c\log\log t}, while this ctlogtct\log t estimate is conjectured to be best possible.

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

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

Solutions 0

No solutions have been posted yet.