Seminars in 2015



16:15 on Tuesday, December 1, 2015 in the coffee room (MA B1 524)

Clement Hongler (EPFL)


“String theory for graph theorists”



Abstract: String theory is, to quote Polyakov, a beautiful and dangerous subject.


I will show some identities involving sums over diagrams, trees, planar graphs and circuits, and then wave my hands to explain why one can think of them as tips of an iceberg, aimed at unifying all forces of nature. If time allows, we will try to understand some subtleties of the 26th dimension.





11.15 on Monday, November 23, 2015 in the coffee room (MA B1 524)

Gunter Rote (Freie Universität Berlin)

“Minimal dominating sets in trees: counting, enumeration, and extremal results”

Abstract:A tree with $n$ vertices has at most 9*5^{n/13} minimal dominating sets.
The corresponding growth constant lambda = sqrt[13]{95} ~ 1.4194908
is best possible. These results are obtained more or less automatically by computer,
starting from the dynamic-programming recursion for computing the number of minimal dominating sets of a given tree. This recursion defines a bilinear operation on sixtuples, and
the growth constant arises as a kind of “dominant eigenvalue” of
this operation. We also derive an output-sensitive algorithm for listing all minimal dominating sets
with linear set-up time and linear delay between reporting successive solutions.
It is open whether the delay can be reduced to a constant delay,
for an appropriate modification of the problem statement.




10.15 on Tuesday, November 17, 2015 in the coffee room (MA B1 524)

Radoslav Fulek (IST)

“Easy and hard planarity variants”

Abstract: How hard is it to decide if a pair of planar graphs sharing edges can be simultaneously embedded in the plane? This question asked a decade ago by Brass et al. [WADS 2003, Computational Geometry 2007] became arguably the most prominent open problem in the algorithmic theory of graph planarity variants, simply because it turned out that its tractability would imply tractability for a myriad of planarity variants, whose tractability status is unknown.

I will discuss several seemingly unrelated open problems that happen to be (very) special cases of the problem of simultaneous embeddability of two planar graphs. Nevertheless, usual tools for solving planarity variants seem to be not powerful enough to tackle even these, probably much simpler, problems. We support our claim about the lack of theoretical foundations by establishing various special cases of one of these problems using a diverse array of tools ranging from Hall’s marriage theorem [1935] to efficient algorithms for finding simultaneous PQ-orderings by Blaesius and Rutter [SODA 2013].
Our approach is inspired by the theory of obstructions to piecewise linear embeddability pioneered by van Kampen and Hanani. Parts of my talk are based on a joint work with Marcus Schaefer, Michael Pelsmajer and Daniel Stefankovic and a joint work with Jan Kyncl, Igor Malinovic and Domotor Palvolgyi.



10.15 on Tuesday, November 10, 2015 in the coffee room (MA B1 524)

Géza Tóth (Rényi Institute, Budapest)

Saturated 1-planar graphs”

Abstract: A graph is called 1-planar, if it can be drawn in the plane such that each edge is crossed at most once. It is known that the maximum number of edges of a 1-planar graph is $4n-8$. Brandenburg et al. observed a very interesting phenomenon. They noticed that maximal 1-planar graphs (no edge can be added so that it remains 1-planar) can have much fewer edges.

I review the estimates of Brandenburg et al. for the minimum number of edges of a maximal 1-planar graph and give an improvement of the lower bound.

Joint work with Jànos Baràt.



11.15 on Monday, November 9, 2015 in the coffee room (MA B1 524)

Andrey Gavriliuk (Systems Analysis Institute of Russian Academy of Sciences)

“Voronoi’s conjecture and canonical scalings for tilings”

Abstract: Voronoi’s conjecture is a hundred years’ old problem that remains open. Amazingly enough, new results on the topic appeared recently, after decades of silence. The main object for the problem is a parallelotope. It is a convex polytope in a Euclidean space which tiles the space with its translates. The conjecture suggests nice (and efficient) classification for parallelotopes: they are conjectured to be affine images of Dirichlet domains for lattice points.
Voronoi himself suggested a sophisticated method, which he applied to the so-called primive parallelotopes. This method was enhanced with a novel study of canonical scalings. This method provides a nice treatment for local geometry of tilings and have led to new results (in 2005 by Ordine and in 2015 by our group).

We will discuss aapproach for proving Voronoi’s conjecture, the role of canonical scalings, methods for generating local canonical scalings and our recent results dealing with these concepts.



10.15 on Tuesday, November 3, 2015 in the coffee room (MA B1 524)

A Compact Geometric Structure for Global Illumination
Nabil Mustafa
(Universite Paris-Est)

Abstract: One of the most challenging problems in computer graphics is efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. To reduce computations one can group the VPLs into a small number of clusters. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. Empirical results indicate that our method outperforms previous state-of-the-art methods. Joint work with Norbert Bus and Venceslas Biri appearing in Eurographics 2015.

No background in computer graphics will be assumed!




10.15 on Tuesday, October 27, 2015 in the coffee room (MA B1 524)

A discrete geometric version of Hall’s theorem

Andreas Holmsen (KAIST, EPFL)

Abstract: I will present a recent discrete geometric version of Hall’s marriage theorem based on joint work with Luis Montejano and Leonardo Martinez. Given n finite sets in the d-dimensional space, we give combinatorial conditions under which it is possible to choose n points, one point from each set, in such a way that the selected points are in general position. When the dimension is 1 we recover Hall’s theorem. The combinatorial conditions relate a certain domination parameter in hypergraphs to the homological connectedness of independence complexes.





10.15 on Tuesday, October 20, 2015 in the coffee room (MA B1 524)

Erdos-Ko-Rado theorem for (-1,0,1)-vectors

Andrey Kupavskii (EPFL)

Abstract: We determine the maximum number of (-1,0,1)-vectors subject to the following condition. All vectors have length n, exactly k of the coordinates are +1 and one is -1, n>2k-1. Moreover, there are no two vectors whose scalar product equals the possible minimum, -2. Thus, this problem may be seen as an extension of the classical Erd\H os-Ko-Rado theorem. We obtain a complete solution for this problem. Rather surprisingly, there is a phase transition in the behaviour of the maximum at n=k^2. The main tools are from extremal set theory and some of them might be of independent interest.

Joint work with Peter Frankl.








10.15 on Tuesday, October 13, 2015 in the coffee room (MA B1 524)

“On VC-dimension, Voronoi diagrams of moving points, density Hales-Jewett phenomena and a problem in sensor networks

Shakhar Smorodinsky (Ben-Gurion University & EPFL)

Abstract: Think of the following simple fact: Given a set P of n points on the line and a parameter 1 < k < n, one can (TRIVIALLY) select a subset P’ of the given points of size O(k) such that between any two consecutive points of P’ there are at most O(n/k) points of P.

Now lets add a bit of complication: Assume that the points are moving linearly. Each point p is now a linear function and so the location of p at time t is given by p(t) = at+b. Can one still select O(k) of the given points with the above property preserved at all times?

In this talk we consider this problem and show how it relates to the density version of Hales Jewett theorem. We show how to tackle a much more general problem using the theory of VC-dimension. Time permitting we show a nice application to sensor networks.




10.15 on Tuesday, October 6, 2015 in the coffee room (MA B1 524)

Beyond the Richter-Thomassen conjecture

Natan Rubin (Ben-Gurion University, Israel)

Abstract: If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. We establish the following Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least Omega(loglog n)^{1/8}). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1-o(1))n^2.

Joint work with Janos Pach and Gabor Tardos.




10.15 on Tuesday, September 29, 2015 in the coffee room (MA B1 524)

“Every finite family of pseudodiscs must contain a small pseudodisc

Rom Pinchasi (Technion)

Abstract: We show that there exists an absolute constant c<200 such that
in every finite family F of pseduodiscs one can find one disc D with
the following property. Among the members of F that intersect D,
there are at most c pairwise disjoint pseduodiscs. This result has some
nice applications in two and three dimensions.

17:00 on Tuesday, July 14, 2015 in the coffee room (MA B1 524)

”Ordered graphs and Ramsey numbers”

Martin Balko (Charles University in Prague)

Abstract: An ordered graph is a pair (G,<) where G is a graph and < is a total ordering of its vertices. Recently, an analogue of Ramsey numbers for ordered graphs has been introduced. The ordered Ramsey number OR(G,<) is the minimum number N such that every ordered complete graph with N vertices and with edges colored by two colors contains a monochromatic copy of (G,<).


In this talk, we discuss the effects of different vertex orderings on the ordered Ramsey number of a given graph and compare the ordered and unordered Ramsey numbers. We also mention some new open problems concerning ordered Ramsey numbers.



11:15am on Wednesday, May 27, 2015 in the coffee room (MA B1 524)

On the Planarity Testing of Trees with Additional Constraints”
Radoslav Fulek (IST Austria)

Abstract: Let T=(V=V_1 U V_2 U V_3,E) denote a tree whose vertex set V

is partitioned into three parts. We prove that there exists a polynomial
time algorithm to test if there exists a planar graph G=(V,E’) such that
(i) E \subseteq E’ and (ii) the sub-graph of G induced by V_i, G[V_i], is connected for all i=1,2,3.In other words, we show that testing clustered planarity (c-planarity) is solvable in a polynomial timefor flat clustered graphs with three clusters if the underlying abstract graph is a tree. Previously, an analogous result was known just for cycles.



11:15am on Wednesday May 20, 2015 in the coffee room (MA B1 524)

Low-diameter decomposition technique

Nabil Mustafa (Universite Paris-Est)

Abstract: The low-diameter decomposition lemma states broadly that a set of n points in a metric space can be partitioned into smaller-diameter subsets such that for every pair of points p, q, the probability of the edge pq crossing the cut is proportional to d(p,q)*log n. I will present an elegant proof of this, together with some applications.



Time exception: 14: 15 pm on Thursdays April 23, 2015 in the coffee room (MA B1 524)
”Constructive discrepancy minimization for convex sets (by T. Rothvoss)”
Yuri Faenza (EPFL)
Abstract: A classical result of Spencer shows that a set system with n elements
and sets has discrepancy O(n^1/2). Recent results provided algorithms to actually
find such a coloring. I will present the latest one by Rothvoss, that deals with the
following, more general problem: find a point with many \pm 1 coordinates in a
centrally symmetric convex set of sufficiently large Gaussian measure.


11:15am on Wednesday April 22, 2015 in the coffee room (MA B1 524)
”Approximate Steiner trees”
Konrad Swanepoel (London School of Economics)

Abstract: Given a set N of n points in d-dimensional Euclidean space, we consider
Steiner minimal trees, which are shortest trees that interconnects the set
N, where we allow the trees to have additional vertices. It is well known
that these additional vertices, called Steiner points, have degree 3 and
that the angle between any two edges incident to a Steiner point is
exactly 120 degrees. In the plane, Steiner minimal trees can be
constructed with ruler and compass, but in higher dimensions this is not
true any more, and exact calculations are in practice replaced by
numerical approximations. Rubinstein, Weng and Wormald (2006) studied the
error in the length of epsilon-approximate Steiner trees,which are
approximations in which all angles at Steiner points are within epsilon of
120 degrees. We improve and extend some of their results. This is joint
work with Charl Ras and Doreen Thomas (University of Melbourne).
11:15am on Wednesday April 15, 2015 in the coffee room (MA B1 524)

”Rigidity of graphs and Erdos Geometry”

Orit Raz (Tel Aviv University)

Abstract: In the talk, I will introduce a new approach for testing the *rigidity* of graphs embedded in the plane, and will demonstrate it by analyzing the rigidity of complete bipartite graphs. A major tool in the analysis is the so-called Elekes-Sharir framework that transforms repeated distances in a planar point set into incidences of lines in three dimensions.

I will then reprove a result of Pach and De Zeeuw (2014), regarding the number of distinct distances determined by points lying on an algebraic curve in the plane, by identifying special bipartite graphs that arise in this context and by exploiting the rigidity of such graphs. This is joint work with Micha Sharir.



Exceptional time : 14:15 on Thursday March 26, 2015 in the coffee room (MA B1 524)
”PCP theorem for amateurs (by an amateur)”
Clement Hongler (EPFL)
Abstract: In this talk, I will talk about the celebrated PCP theorem, which says interesting things about proofs that can be checked easily and about graphs that are hard to color partially.
I will present the statement and the main ideas of (Irit Dinur’s new) proof of it, which uses expanders.

The prerequisite will be minimal.

11:15 am on Wednesday March 18, 2015 in the coffee room (MA B1 524)
”Improved Local Search for a Geometric Hitting Set Problem”
Nabil Mustafa (École Supérieure d’Ingénieurs en Électronique et Électrotechnique, Paris )
Abstract: Consider the following geometric hitting set problem: given a set P of points and a set of disks in the plane, compute the minimum-sized subset of P that hits all given disks. Surprisingly, Mustafa-Ray (2010) showed that the algorithm to achieve a PTAS is simple: local-search. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: large running times. In this talk I will present an algorithm that, through a better understanding of both combinatorial and algorithmic aspects of local-search, gives a 8-approximation in time n^{2.34}. This is joint work with Norbert Bus, Shashwat Garg and Saurabh Ray.
11:15am on Friday, March 6, 2015
“Essential expansion is locally forceable”
Gabor Kun, Renyi Institute Budapest

Abstract: We say that a sequence of d-regular graphs is “essentially expander”
if it can be turned into a disjoint union of expanders by removing
and adding o(n) edges. We give a spectral characterization of such
sequences. (Essential) expansion is not testable by randomly sampling
a constant number of vertices and looking at a ball of constant radius
centered at these vertices. Indeed, graphs with large girth may be
essential expanders or very far from essential expanders. Howevert,
there exists local (Benjamin-Schramm) statistics that a sequence
with this statistics is essentially expander, i.e., essential
expansion is locally forceable as showed by the next result: We
solve Bowen’s problem proving that the local (sofic) approximation
of a finitely generated group with Kazhdan Property (T) is essentially
expander. Our results extend to the strongly ergodic case and give a
non-separable(!) ergodic decomposition theorem (for ultraproducts).
We use our characterization to give an alternative construction of non-
hyperfinite 2-dimensional simplicial complexes (in the sense of
Freedman and Hastings). The talk will focus on the graph theoretical
parts, no background will be assumed in group theory and ergodic

11:15am on February 27, 2015
“On some Rogers-Shephard type volume inequalities”

Zsolt Lángi (Budapest University of Techonlogy)


Abstract: In the 1950s, Rogers and Shephard determined the minimal and maximal

volume of the convex hull of two congruent copies of a convex body in Euclidean
$n$-space, under some subsets of the isometry group of the space. In this talk we
present similar volume estimates about convex bodies both in Euclidean and, more
generally, in finite dimensional normed spaces.