Pinchasi–Sharir conjecture on planar tangent graphs

A tangent graph has one vertex for each disc and an edge when the corresponding discs are tangent. Pinchasi–Sharir tangent-incidence conjecture. (i) Planar tangent graphs with nn vertices have at most n4/3polylog(n)n^{4/3}\operatorname{polylog}(n) edges. (ii) More generally, mm red discs and nn blue discs, including the special case of nn blue points, can touch at most ((mn)2/3+m+n)polylog(m,n)((mn)^{2/3}+m+n)\operatorname{polylog}(m,n) times. The source reports a best known upper bound of n3/2lognn^{3/2}\log n and leaves the conjecture open.

Sources & referencesView supporting material

Primary source

Gil Kalai, “Some old and new problems in combinatorial geometry I: Around Borsuk's problem”, arXiv:1505.04952 (2015).

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.