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 C1, …, Ck, contained in S, we have
perimeter(C1)+…+perimeter( Ck) ≤ perimeter(S)+2(k-1)diameter(S)
Polynomials on Products
By Frank de Zeeuw (EPFL, Lausanne)
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.
