Seminars in 2016

2016. Dec. 15. (Thursday) 11:00: Rico Zenklusen (ETH Zurich)

“Analyzing k-Trails through Algorithmic Matroid Theory”



The notion of degree-constrained spanning hierarchies, also called k-trails, was recently introduced in the context of network routing problems. They describe graphs that are homomorphic images of connected graphs of degree at most k. First results highlight several interesting advantages of k-trails compared to traditional routing approaches. However, so far, only little was known regarding computational aspects of k-trails.
In this talk I will show how k-trails can be analyzed using techniques from algorithmic matroid theory. This connection will allow us to settle several open questions about k-trails in a unified way. In particular, I will present an approach to efficiently recognize whether a graph is a k-trail through matroid intersection.
This is joint work with Mohit Singh.




2016. Dec. 7. (Wednesday) 11:00: Konrad Swanepoel (LSE, London)

“Almost-equidistant sets”



What is the largest number of unit vectors in d-dimensional Euclidean space such that between any 3 of the vectors, some two are orthogonal? With a neat algebraic argument, Moshe Rosenfeld (1991) gave the tight answer of 2d. We consider a related question. What is the largest number of elements in a set of points in d-dimensional Euclidean space such that between any 3 of the points, some two are at distance one? This problem seems to be harder. We give some new estimates as d becomes large, and more exact values when d is small. Joint work in progress with Martin Balko, Attila Por, Manfred Scheucher and Pavel Valtr.



2016. Dec. 6. (Tuesday) 11:00: Bartosz Walczak (Jagiellonian University in Kraków)

Coloring curves that cross a fixed curve”



A class of graphs is χ-bounded if the chromatic number of all graphs in the class is bounded by some function of their clique number. String graphs are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are χ-bounded. In particular, it is known since 2012 that the class of all string graphs is not χ-bounded. We prove that for every integer t≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is χ-bounded. This result is best possible in several aspects; for example, the upper bound t on the number of crossings with the fixed curve cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called k-quasi-planar topological graphs. This is joint work with Alexandre Rok.



2016. Nov. 29. (Tuesday) 11:00: Ivan Izmestiev (Université de Fribourg)

“Simplicial moves on colored triangulations”



Bistellar flips (aka Pachner moves) allow to transform a triangulation of a manifold to any other triangulation of the same manifold. In this talk I will describe a set of moves (so called cross-flips) that allow to connect any two vertex-colored triangulations of the same manifold while respecting the colorings. These moves are related to the cross-polytope in the same way as the Pachner moves are related to the simplex. This is a joint work with Steve Klee and Isabella Novik.
2016. Nov. 15. (Tuesday) 11:00: Zsolt Lángi (EPFL)

On maximum area convex polygons circumscribed about a convex polygon”

Abstract. A convex polygon Q is circumscribed about a convex polygon P if every vertex of P lies on at least one side of Q. In this talk we to give an algorithm to find, for any given convex polygon P, a maximal area convex polygon circumscribed about P. In addition, we point out an application of the problem to statistics, and disprove a related conjecture of Farris. The results are joint work with Markus Aussenhofer, Susanna Dann and Geza Toth.


2016. Nov. 8. (Tuesday) 11:00: Andrei Kupavskii (EPFL)

“Large families with no matchings of size s”

Abstract. This talk, as well as a recent one on Octoberfest, is devoted to families of sets with no s pairwise disjoint sets. I plan to explain a new, much simpler, approach to prove an 50-year-old result of Kleitman determining the maximal size of such families in some cases, and to overview the recent progress in the area.



2016. Nov. 1. (Tuesday) 11:00: Rado Fulek (IST Austria)

Approximating maps in the plane by embeddings

Abstract. A (possibly degenerate) drawing $\varphi$ of a graph G in the plane is approximable by an embedding of G if $\varphi$ can be turned into an embedding by an arbitrarily small perturbation.

By answering in the affirmative a conjecture of M. Skopenkov (2003), we show that we can test in polynomial time whether $\varphi$ is approximable by an embedding.
Joint work with J. Kyncl.

2016. Oct. 26. (Wednesday) 11:00: Mehdi Makhul (RISC,Linz)

Ordinary circles”

Abstract. We will discuss the circle variant of the Dirac-Motzkin conjecture and orchard problem. We proved the following structure theorem: If n is sufficiently large depending on K, and P is a set of n points in the plane spanning at most O(Kn^2) ordinary circles (circles containing exactly three points of P), then all but O(K) points of P lie on an algebraic curve of degree at most four. Our proof relies on a recent result of Green-Tao on ordinary lines. This is joint work with Aaron Lin, Hossein Nassajian Mojarrad, Josef Schicho, Konrad Swanepoel, and Frank de Zeeuw.


2016. Oct. 25. (Tuesday) 11:00: Micha Sharir (Tel Aviv University)

Eliminating depth cycles for lines and triangles, with applications to bounding incidences”

The talk presents three related results.

We first consider the problem of eliminating all depth cycles in a set of n lines in 3-space.
For two lines l_1, l_2 in 3-space (in general position), we say that l_1 lies below l_2 if the
unique vertical line that meets both lines meets l_1 at a point below the point where it meets l_2.
This depth relationship typically has cycles, which can be eliminated if we cut the lines into
smaller pieces. A 25-year old problem asks for a sharp upper bound on the number of such cuts.
We show that this can be done with O(n^{3/2} polylog(n)) cuts, almost meeting the known worst-case
lower bound Omega(n^{3/2}).

The second topic extends the previous result to eliminating depth cycles in a set of pairwise
disjoint triangles in 3-space. (This is the “real” problem one would like to solve, motivated
by applications to computer graphics.) The depth relationship is defined in an analogous manner,
and cycles can be eliminated by cutting the triangles into simply-shaped pieces for which the
depth relationship is acyclic. A well known (albeit non-trivial) way of doing this is to use
a binary space partition, which produces quadratically many cuts (into triangular pieces).
We extend the cycle elimination result for lines to this setup, and show that all depth cycles
can be eliminated by cutting the triangles into O(n^{3/2+eps}) pieces, for any eps>0, where
each piece is a semialgebraic region of constant complexity (where this complexity depends on eps).
The extension is fairly involved, as it needs to use fairly sophisticated topological arguments
(unnecessary for the case of lines) to control the number of pieces.

The third topic is based on a straightforward, albeit technically demanding, extension of the
first result to eliminating cycles in a set of n algebraic arcs of constant degree in 3-space, with
a similar upper bound, close to n^{3/2}, on the number of required cuts. Combining this with a recent
idea of Ellenberg, Solymosi, and Zahl, we obtain new incidence bounds for points and arbitrary
fixed-degree algebraic curves in the plane.

All these developments are based on the polynomial partitioning technique of Guth and Katz, and
constitute a somewhat “unorthodox” application of this tool, which we hope will have follow-up
applications of a similar nature.

Based on joint works with Boris Aronov, Ed Miller, and Joshua Zahl.


2016. Oct. 18. (Tuesday) 11:00: Will Sawin (ETH)

Slice Rank and Sunflowers”

Abstract. Building on the recent breakthrough of Croot, Lev, and Pach and the subsequent work of Ellenberg, Gijswijt, and Tao, Eric Naslund and I proved strong new bounds for two analogues of the Erdos-Rado sunflower problem (though not the original problem). I will explain the general slice rank method and how it can be used to give these bounds. I will also discuss limitations of the method and say why these bounds may be hard to improve.


2016. Oct. 11. (Tuesday) 11:00: Leonardo Martinez (Ben-Gurion Univ. of the Negev)

Snakes, lattice path matroids and a conjecture by Merino and Welsh”

Abstract. In 1999 Criel Merino and Dominic Welsh studied relationships between some values of the Tutte polynomial of a graph that have a combinatorial interpretation. Specifically, they found relationships between the number of spanning trees, the number of acyclic orientations and the number of totally cyclic orientations. They conjectured an inequality that relates these three parameters and they proved its validity for some specific cases.

Although the conjecture is still open, there has been constant progress towards its solution. Two stronger (but easier to handle) versions were posed, as well as a natural generalization to matroids. These variants have been verified for various families of graphs and matroids.

During the talk I will speak about the current status of the problem. I will also present progress made in a joint work with Jorge Ramírez-Alfonsin and Kolja Knauer: we prove the conjecture for the well-studied family of lattice path matroids via a decomposition into smaller matroids which we call “snakes”. This allows us to prove an even sharper version of the conjectured inequality and find the cases in which equality holds.


2016. Oct. 10: Joel Spencer (NYU): Counting Connected Graphs

Place: CM1


Let C(n,k) be the number of labelled connected graphs with n vertices and n-1+k edges. For k=0 (trees) we have Cayley’s Formula. We examine the asymptotics of C(n,k). There are several ranges depending on the asymptotic relationship between n and k. The approaches are a virtual cornucopia of modern probabilistic techniques. These include supercritical dominant components in random graphs, local limit laws, Brownian excursions, Parking functions and more.



2016. Oct. 4. (Tuesday) 11:00: Frank de Zeeuw (EPFL)

Incidence bounds over arbitrary fields”

Abstract. I will discuss some recent progress in extending the point-line incidence bound of Szemeredi and Trotter to arbitrary fields. All known proofs of the Szemeredi-Trotter theorem use special properties of the real field, and for that reason do not work over arbitrary fields, in particular not over finite fields. Bourgain, Katz, and Tao showed in 2004 that, nevertheless, some such incidence bound should hold over any field, although their bound was quantitatively weak. I will show a quantitative improvement of their result (not-yet-published joint work with Sophie Stevens).
I will introduce the problem and its history, and then sketch some of the new proof, which involves some wonderful geometry. The point-line incidence problem is converted to a point-plane incidence problem, which is then reduced using a method of Rudnev to a line-line incidence problem in space, where a theorem of Guth and Katz can be applied. There are various applications; for instance, we can reproduce the best known sum-product bound over arbitrary fields, using a classical argument of Elekes.


2016. Sep. 29. (Thursday) 11:15: Nabil Mustafa (ESIEE Paris)

“Spatial Partitioning for Geometric Objects

Abstract. The goal of spatial partitioning methods, given a set of geometric objects in Euclidean space, is to partition space into ‘simple’ regions such that each region intersects few of the given objects. Initially devised for algorithmic purposes, this idea has proven extremely influential in proving combinatorial bounds for a variety of problems.

In this talk I will give a historical outline of the ideas involved in both the constructions of these spatial partitions as well their applications in getting combinatorial bounds. I will then give two recent applications of such ideas.


14:15 on May 31, 2016 in the coffee room (MA B1 524)

Thang Pham (EPFL)
“Progression-free sets over finite fields”

Abstract: Let F be a finite field of order p. We say that a set A is progression-free if there are no three elements in A which form an arithmetic progression. In an important breakthrough, Ellenberg and Gijswijt, using an elegant technique of Croot-Lev-Pach, has recently proved that if A is progression-free, then |A|=O(p^{cn}), for some positive constant c<1. The main purpose of this talk is to present their simple and elegant algebraic approach.


16:15 on Wednesday, May 25, 2016 in the coffee room (MA B1 524)


Andrew Suk (UIC)


“On the Erdos-Szekeres convex polygon problem” 

Abstract: Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdos and Szekeres showed that ES(n) \leq {2n – 4\choose n-2} + 1 = 4^{n -o(n)}. In 1960, they showed that ES(n) \geq 2^{n-2} + 1 and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has been made on the upper bound over the last 81 years. In this talk, we will sketch a proof showing that ES(n) =2^{n +o(n)}. We will also discuss several related open problems including a higher dimensional variant, and on mutually avoiding sets.


16:15 on Tuesday, May 10, 2016 in the coffee room (MA B1 524)

Andreas Holmsen (KAIST)
The intersection of a matroid and an oriented matroid”

Abstract: An oriented matroid is a combinatorial abstraction of real vector configurations. I will present a “matroid intersection theorem” where we are intersecting a matroid and an oriented matroid defined on the same ground set. As a special case we obtain Barany’s “colorful caratheodory theorem” from 1982. I’ll explain all notoins from scratch, and no prior knowledge of matroids (oriented or not) will be assumed.





16:15 on Monday , May 9, 2016 in the coffee room (MA B1 524)

Dániel Korándi (ETH Zürich)
“Domination in 3-tournaments”

Abstract: A 3-tournament is a complete 3-uniform hypergraph where each edge has a special vertex designated as its tail. A vertex set $X$ dominates $T$ if every vertex not in $X$ is contained in an edge whose tail is in $X$. The domination number of $T$ is the minimum size of such an $X$. Generalizing
well-known results about usual (graph) tournaments, Gyárfás conjectured that there are 3-tournaments with arbitrarily large domination number, and that this is not the case if any four vertices induce two triples with the same tail. In this talk I will solve both problems, proving the first conjecture and refuting the second. Joint work with Benny Sudakov.






16:15 on Monday, April 25, 2016 in the coffee room (MA B1 524)

Gábor Tardos (Rényi Institute, Budapest)
“Extremal theory of ordered graphs and small forbidden patterns”
Abstract: Ordered graphs are defined as simple graphs with a linear order on the vertices. This allows for an extension of the classical (Tur\’an-type) extremal graph theory to the more subtle questions, where a certain pattern is forbidden only with a certain vertex-order.

A particularly interesting special case is where the forbidden pattern P is cycle-free and order-bipartite. A modification of a conjecture of Z. F\”uredi and P. Hajnal (1992) calls for a nearly linear upper bound on the number of edges of a P-free ordered graph. In 2006, J. Pach and I established an n times polylog upper bound for patterns of at most 6 vertices. In more recent joint work with C. Weidert, I proved a weaker, but still “almost linear” bounds for patterns of size at most 7. We hope that the proof technique can be generalized to settle the whole conjecture.





15:15 on Monday, April 11, 2016 in the coffee room (MA B1 524)

Javad Ebrahimi (Chinese University of Hong Kong)
Index coding via graph homomorphism”
Abstract: Index coding is a central problem in the area of network communication which has a simple combinatorial description. Besides its application in communication, this problem is related to various theoretical questions in computer science and mathematics.

In this talk, we formally define the problem and describe its connection to graph coloring, graph homomorphism, and orthogonal bi-representation of graphs. We show how to use these connections to get new lower bounds on the size of index codes for graphs.




16:15 on Tuesday, March 15, 2016 in the coffee room (MA B1 524)

Andrei Kupavskii (Grenoble Institute of Technology)

“Hypergraphs with no matching of size k”

Abstract: We would discuss the following problem: given a set family on [n], how many sets it can contain provided that it does not contain k pairwise disjoint sets? This is an old problem going back to Erdos. The problem was resolved in some cases by Kleitman around 50 years ago. There was little progress in this problem since then. In a recent work with P. Frankl we managed to resolve this question in some new cases and to put it into a broader context. We are going to review the history of the problem, the new results and to discuss some of the techniques that are used in the proofs.