Two-Day Workshop on Combinatorics



 Tuesday 25 February 2014 14:15 – 15:00 MA B1 524

Limits of graphs and nondeterministic property testing

By  Katalin Vesztergombi, (Eotvos University Budapest)

Property testing is an area of computer science where properties and
parameters of very large graphs are estimated based on small samples
from the graph. One way to define a sequence of graphs to be
convergent is that they are less and less distinguishable from
bounded-size samples (Borgs and al.). Limit objects can be assigned
to such sequences in the form of graphons, i.e., symmetric measurable
functions from [0,1]x[0,1] to [0,1] (Lovasz and Szegedy). These limit
objects are often simpler than the members of the sequence that
converges to them, and they express asymptotic properties of members
of the sequence in a compact form.

One can define the notion of “nondeterministic property testing” in
analogy with nondeterministic algorithms. Somewhat surprisingly, it
turns out that (in the setting of dense graphs) nondeterministically
testable properties are also deterministically testable. This result
can be proved using the limit theory of graphs.

Joint work with Laszlo Lovasz.    25


Tuesday 25 February 2014 15:15 – 16:00 MA B1 524

An isoperimetric inequality for convex sets in the plane

By  Rom Pinchasi (Technion, Haifa) 

We prove the following conjecture raised recently by Alexey Glazyrin and Filip Moric. Given a convex set S in the plane and k pairwise disjoint convex sets C1, …, Ck, contained in S, we have

perimeter(C1)+…+perimeter( Ck) ≤ perimeter(S)+2(k-1)diameter(S)   .


Wednesday 26 February 2014 14:15 – 15:00 MA B1 524

Polynomials on Products

By  Frank de Zeeuw (EPFL, Lausanne)


In 2000, Elekes and Rónyai proved the following: Given a real polynomial f(x,y) and real sets A,B of size n, the number of values of f on AxB is
superlinear, unless f has the form f=g(h(x)+k(y)) or f=g(h(x)k(y)). One application is that the number of distinct distances between two n-point sets on two lines is superlinear, unless the lines are parallel or orthogonal.
After several intermediate results, Sharir, Sheffer, and Solymosi introduced a new technique in 2013 to prove that the number of distances must be at least cn4/3. This technique has already found many applications, including very recently the extension of the bound cn4/3 to the general Elekes-Rónyai problem, by Raz, Sharir, and Solymosi.
I will discuss these and related results, as well as work in progress of Claudiu Valculescu and myself, attempting to generalize these results to functions on algebraic curves: Given a polynomial f(p,q)=f(px,py,qx,qy) of pairs of points in the plane, and n-point sets A,B on a plane curve C, |f(A,B)| must be at least cn4/3, unless f is special or C is special.

  Wednesday 26 February 2014 15:15 – 16:00 MA B1 524

On topological graphs with at most four crossings per edge

By  Eyal Ackerman, (Technion, Haifa)

We show that if a graph G with n ≥ 3 vertices can be drawn in the plane in such a way that each of its edges is involved in at most four crossings,  then G has at most 6n-12 edges. This settles a conjecture of Pach, Radoicic, Tardos, and Toth, and yields a better bound for the famous Crossing Lemma: The crossing number, X(G), of a (not too sparse) graph G with n vertices and m edges is at least cm3/n2, where c > 1/29. This bound is known to be tight, apart from the constant c for which the previous best lower bound was 1/31.1.

As another corollary we obtain some progress on the Albertson conjecture. Albertson conjectured that if the chromatic number of a graph G is r, then X(G) ≥ X(Kr). This was verified by Albertson, Cranston, and Fox for r ≤ 12, and for r ≤ 16 by Barat and Toth. Our results imply that Albertson conjecture hold for r ≤ 18.