## 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

## 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 C_{1}, …, C_{k}, contained in S, we have

perimeter(C_{1})+…+perimeter( C_{k}) ≤ perimeter(S)+2(k-1)diameter(S)

**Polynomials on Products**

**By ****Frank de Zeeuw** (EPFL, Lausanne)

^{4/3}. This technique has already found many applications, including very recently the extension of the bound cn

^{4/3}to the general Elekes-Rónyai problem, by Raz, Sharir, and Solymosi.

_{x},p

_{y},q

_{x},q

_{y}) 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 cn

^{4/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 cm^{3/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(K_{r}). 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.