I spent the last week visiting the Institute for Pure and Applied Mathematics at UCLA, for a workshop on combinatorial geometry. Rather than post here about the many exciting new results I heard about (for which see the conference program) I thought I'd describe a few open problems that came up in some of the talks.

Jacob Fox began the conference by describing his work with János Pach on separator theorems for string graphs. He mentioned a problem that he attributed to Erdős: suppose that \( A \) is a collection of line segments in the plane, no three of which intersect pairwise. How many colors are needed, in the worst case, to color the segments of \( A \) so that no two crossing segments have the same color. In other words, what is the chromatic number of a triangle-free intersection graph of line segments? It is not even known whether this number has a finite bound. For instance, the line segments below represent the Grötzsch graph, a triangle-free graph requiring four colors.

Representation of the Grötzsch graph as a line segment intersection graph

ETA 7/2012: A solution to this problem has been announced!

Rom Pinchasi spoke about "some unrelated problems", one of which concerned blocking visibilities among sets of points in the plane. If one is given \( n \) blue points, how many additional red points must one place so that there is a red point between every pair of blue points? If the points are in sufficiently general position (so that any red point can block at most two pairs of blue points) then a quadratic number of blockers is needed, but it seems to be the case that, even if one carefully arranges the blue points so that they are easily blocked, a superlinear number of blockers may be needed. Specifically, Pinchasi conjectured that if no three blue points are collinear, they can't be blocked with fewer than \( \Omega(n\log n) \) red points. He also considered a version of the problem where the blue points may have collinearities and in which, on each line determined by two or more blue points, one needs only to place a red point somewhere between the two extreme blue points. For this variation, he proved that at least \( n/2 \) blockers are necessary (unless all blue points are on one line). However, the arrangement below (one of two examples of point sets with few ordinary lines) was the only one he could find in which fewer than \( n \) were sufficient.

Seven blue points and six red points, with a red point between two blue points somewhere on each blue line

Although Richard Ehrenborg's talk was about something else, he began with another unrelated problem, concerning spanning trees in bipartite graphs. He defined a class of graphs that he called Ferrers graphs, a bipartite variation of threshold graphs, as follows. From any Ferrers diagram with \( x \) rows and \( y \) columns, we form a bipartite graph with \( x \) vertices \( u_i \) on one side of the bipartition and \( y \) vertices \( v_i \) on the other side, where \( u_i \) is connected to \( v_i \) if there's a dot or square in the \( i \)th row and \( j \)th column of the diagram; I've drawn an example below. For these graphs, there's a very simple formula for the number of spanning trees: multiply together all the degrees of all the vertices, and divide this product by \( xy \). Ehrenborg conjectures that the same formula (the product of the degrees divided by the numbers of vertices on each side of the bipartition) is an upper bound for the number of spanning trees in any bipartite graph.

A Ferrers diagram and its Ferrers graph

József Solymosi finished off the conference by a talk about the famous and still unsolved problem of how many pairs of points can be at unit distance among \( n \) points in the plane, or equivalently how many edges can be in a unit distance graph. He asked about a related problem, progress on which would lead to progress in the original graph: given \( n \) unit circles in the plane, how many points can there be that are crossed by three or more of the circles? One can get a superlinear lower bound by placing circle centers on a grid with a carefully chosen spacing. For instance, in the grid of circles shown below, the radius of the circles is \( 5/2 \) times the grid spacing, and the points of triple intersection (some of which are marked in green) form a diagonal grid twice as dense as the grid of circle centers. However, for upper bounds, nothing better than the trivial \( O(n^2) \) is known.

A grid of circles with radius 5/2 times the grid spacing