Spring 2019 – schedule overview
Torsten Mütze (TU Berlin): On Hamilton cycles in highly symmetric graphs
Monday February 25, 14:00, room C417
The question whether a graph has a Hamilton cycle or not is one of the oldest and most fundamental graph-theoretic problems, and one of the prototypical NP-complete problems. In this talk I will survey some recent results on Hamilton cycles in various families of highly symmetric graphs. The starting point is a sketch of our recent short proof for the well-known middle levels conjecture. I will also mention several far-ranging generalizations of the conjecture that we proved subsequently, including the Hamiltonicity of bipartite Kneser graphs and sparse Kneser graphs. Particular emphasis will be on algorithmic variants of those questions, and I will show how to compute the corresponding Gray codes in optimal time and space. I will also mention how these results connect different well-known concepts in combinatorics, geometry and algorithms.
Tom Kelly (Waterloo): Fractional coloring with local demands
Monday March 11, 14:00, room C417
In a fractional coloring, vertices of a graph are assigned subsets of the [0, 1]-interval such that adjacent vertices receive disjoint subsets. The fractional chromatic number of a graph is at most k if it admits a fractional coloring in which the amount of "color" assigned to each vertex is at least 1/k. We investigate fractional colorings where vertices "demand" different amounts of color, determined by local parameters such as the degree of a vertex. Many well-known results concerning the fractional chromatic number and independence number have natural generalizations in this new paradigm. We discuss several such results as well as open problems. In particular, we will sketch a proof of a "local demands" version of Brooks' Theorem that considerably generalizes the Caro-Wei Theorem and implies new bounds on the independence number. Joint work with Luke Postle.
Alan Arroyo (IST): Drawings of graphs from a structural point of view
Monday March 25, 14:00, room C417
Straight-line drawings of graphs, in comparison to general topological drawings, are not just more aesthetically appealing, but it is also easier to store them in a computer. This drives to a natural question: When can we convert a topological drawing into an equivalent geometric one?
In 1988, Thomassen completely answered this question for drawings in which every edge is crossed at most once. Thomassen's answer is by means of forbidding two drawings. Following Thomassen's result, I will talk about interesting classes of graph drawings that can be characterized in terms of forbidding a set of subdrawings, and how this approach can bring new insights on tackling graph drawing problems.
This talk is based on joint work with Dan McQuillan, Bruce Richter, Gelasio Salazar and Matthew Sunohara.
Joonkyung Lee (Hamburg): Sidorenko's conjecture for blow-ups
Monday April 8, 14:00, room C417
A celebrated conjecture of Sidorenko and Erdős–Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.
Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A∪B, there is a positive integer p such that the blow-up H_Ap formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Another way of viewing this latter result is that for every bipartite H there is a positive integer p such that an Lp-version of Sidorenko’s conjecture holds for H. Joint work with David Conlon.
Abhisekh Sankaran (Cambridge): Hereditariness in the finite and prefix classes of first order logic
Monday April 15, 14:00, room C417
The Los-Tarski theorem is a result from classical model theory that states that over arbitrary (finite or infinite) structures, a first order (FO) sentence is hereditary if, and only if, it is equivalent to a universal sentence. This theorem however fails when restricted to finite structures. Tait (1959) and independently Gurevich and Shelah (1984) showed that in the finite (i.e. over the class of all finite structures), there is an FO sentence that is hereditary but that is not equivalent to any universal sentence.
In a recent paper [2], a strengthening of the above failure was shown: in the finite, for every k, there is a hereditary FO sentence that is not equivalent to any Σ^0_2 sentence that contains k existential quantifiers. We generalize this result by showing in the finite, that for every n, there is a hereditary FO sentence ϕ_n that is not equivalent to any Σ^0_n sentence. In short, (FO-)hereditariness over all finite structures is not capturable by any prefix class of FO. We show further that ¬ ϕ_n is expressible in Datalog(≠, ¬), thus answering in the negative an open question posed by Rosen and Weinstein [1], that asks whether FO ∩ Datalog(≠, ¬) is contained (semantically) inside some prefix class of FO. The methods used to show our result extend the ideas from [2] in a significant way, and involve the construction of structures that exhibit self-similarity.
This is joint work with Anuj Dawar.
[1] Eric Rosen and Scott Weinstein. Preservation theorems in finite model theory. In International Workshop on Logic and Computational Complexity, pages 480–502. Springer, 1994.
[2] Abhisekh Sankaran. Revisiting the generalized Los-Tarski theorem. In Logic and Its Applications - 8th Indian Conference, ICLA 2019, Delhi, India, March 1-5, 2019, Proceedings, pages 76–88, 2019.
Jonathan Noel (Warwick): Cycles of length three and four in tournaments
Monday April 29, 14:00, room C417
Given a tournament with d*(n choose 3) cycles of length three, how many cycles of length four must there be? Linial and Morgenstern (2016) conjectured that the minimum is asymptotically attained by "blowing up" a transitive tournament and orienting the edges randomly within the parts. This is reminiscent of the tight examples for the famous Triangle and Clique Density Theorems of Razborov, Nikiforov and Reiher. We prove the conjecture for d ≥ 1/36 using spectral methods. We also show that the family of tight examples is more complex than expected and fully characterise it for d ≥ 1/16. Joint work with Timothy Chan, Andrzej Grzesik and Daniel Král'.
Fan Wei (Stanford): On the graph removal lemma
Monday May 6, 14:00, room C417
Szemerédi's regularity lemma is an important and powerful tool in graph theory. One of its prevalent applications is the graph removal lemma, which has numerous applications to extremal problems for graphs and hypergraphs, additive combinatorics, discrete geometry, and theoretical computer science. In this talk, we initiate and prove a new removal lemma with respect to a stronger metric on graphs, which is a strengthening of the usual graph removal lemma.
Mahsa Shirmohammadi (CNRS and IRIF): On the Complexity of Value Iteration
Monday May 13, 14:00, room C417
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal n-step payoff by iterating n times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon n. In this talk, we settle the computational complexity of value iteration. We show that, given a horizon n in binary and an MDP, computing an optimal policy is EXPTIME-complete, thus resolving an open problem that goes back to the seminal 1987 paper on the complexity of MDPs by Papadimitriou and Tsitsiklis.
This result will be presented at ICALP 2018. The technical report is accessible at https://arxiv.org/abs/1807.04920