# Seminars & Events for Discrete Mathematics Seminar

##### The Erdos-Stone Theorem for finite geometries

For any class of graphs, the growth function h(n) of the class is defined to be the maximum number of edges in a graph in the class on n vertices. The Erdos-Stone Theorem remarkably states that, for any class of graphs that is closed under taking subgraphs, the asymptotic behaviour of h(n) can (almost) be precisely determined just by the minimum chromatic number of a graph not in the class. I will present a surprising version of this theorem for finite geometries, obtained in joint work with Jim Geelen. This result is a corollary of the famous Density Hales-Jewett Theorem of Furstenberg and Katznelson.

##### Apollonian structure in the abelian sandpile

The Abelian sandpile is a diffusion process on configurations of chips on the integer lattice, in which a vertex with at least 4 chips can "topple", distributing one of its chips to each of its 4 neighbors. Though the sandpile has been the object of study from a diverse set of perspectives, even some of the most basic questions about the terminal configurations produced by the process have remained unanswered. One of the most striking features of the sandpile is that when begun from a large concentration of n chips, the resulting terminal configurations seem to converge to a peculiar fractal pattern as n goes to infinity.

##### What have we learned about graph partitioning?

The graph partitioning problem consists of cutting a graph into two or more large pieces so as to minimize the number of edges between them. Since the problem is NP-hard, one needs to resort to approximation. This talk will give a quick survey of techniques for graph partitioning, focusing on work in the past 7-8 years that uses semidefinite programming and spectral techniques.

##### Extremal problems in Eulerian digraphs

Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex. In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least m^2/2n^2 +m/2n, and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs.

##### Directed width parameters: algorithms and structural properties

Treewidth of an undirected graph measures how close the graph is to being a tree. Several problems that are NP-hard on general graphs are solvable in polynomial time on graphs with bounded treewidth. Motivated by the success of treewidth, several directed analogues of treewidth have been introduced to measure the similarity of a directed graph to a directed acyclic graph (DAG). Directed treewidth, D-width, DAG-width and Kelly-width are some such width parameters. In this talk, I will present some of the algorithms and structural properties of these parameters with emphasis on Kelly-width and its equivalent characterizations. I will present some recent results and new research directions.

##### Expanders with respect to random regular graphs

The discrete Poincare inequality (PI) for a regular graph G=(V,E) is the following: For any mapping f:V-->H of the vertices into Hilbert space, the average of ||f(u)-f(v)||^2 over all pairs of vertices is at most the average of ||f(u)-f(v)||^2 over the edges (E) times 1/(1-lambda_2(G)), where lambda_2(G) is the second normalized eigenvalue of G. This inequality has a natural metric interpretation: There is no way to embed a constant degree expander in Hilbert space while "uniformly" preserving the shortest path metric, since in the shortest path metric the average square distance over all pairs is unbounded, whereas the average over the edges is (at most) 1. Motivated by this application, PI has been strengthen by replacing Hilbert space with other metric spaces X.

##### On the Erdos-Sos conjecture

We are going to prove that if k is large enough then a graph with average degree k contains all trees on k vertices. This is joint work with Miklos Ajtai, Janos Komlos and Miklos Simonovits.

##### How long does it take to catch a drunk miscreant?

We discuss the answer to a question of Churchley who asked how long it will take a cop to catch a drunk robber who moves randomly. We begin by discussing other variants of the cop-robber paradigm. This is

joint work with Alex Scott, Colin McDiarmid, and Ross Kang. We rely heavily on work of Komarov and Winkler.

##### A Szemeredi-Trotter theorem in R^4

The Szemeredi-Trotter theorem states that m points and n lines in the plane can have at most O(m^{2/3}n^{2/3}+m+n) incidences. This theorem has seen a number of generalizations, including a theorem of Toth that obtains the same result for (complex) points and lines in the complex plane. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

##### Cover-decomposition and polychromatic numbers

In the cover-decomposition problem we are given a ground set of points and a collection of its subsets. Suppose that we want to colour some subsets blue and the others red, so that every point lies in both a blue subset and a red subset. An obvious necessary condition is that every point lies in at least two subsets; is there an exact or approximate converse? What about when there are many colours? Using probabilistic methods and iterated linear programming we'll give positive answers in some settings. This is joint work with Bela Bollobas, Thomas Rothvoss and Alex Scott.

##### Polar codes and randomness extraction for structured sources

Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to matroid theory and randomness extraction are discussed.

##### Discrepancy of graphs and hypergraphs

How uniformly is it possible to distribute edges in a graph? For instance, is there a graph of density 1/2 in which every induced subgraph has approximately the same number of edges as nonedges? Erdos and Spencer showed in 1971 that every graph on n vertices has an induced subgraph in which the numbers of edges and nonedges differ by at least cn^{3/2} (and gave a similar result for hypergraphs). Erdos, Goldberg, Pach and Spencer subsequently proved a weighted extension of this for graphs with density p. We shall discuss generalizations of these results and related questions involving intersections of pairs of graphs or hypergraphs. Joint work with Bela Bollobas.

##### Graph constructions, graph decompositions, and random graphs

Recent work of Kolaitis and Kopparty relates the number of copies of a subgraph in the random graph G(n; p) to questions about logic and circuit complexity. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

##### Informal and formal verification of nonlinear inequalities with applications to discrete geometry

This talk will describe some tools for the automated verification of nonlinear inequalities involving a small number of real independent variables. Various problems in discrete geometry can be reduced to finite collections of nonlinear inequalities. In this way computer-assisted proofs of various conjectures in discrete geometry can be obtained.

##### Even-cycle decompositions of graphs with no odd-K_4-minor

A graph is ``even-cycle decomposable'' if its edge set can be partitioned into even length cycles. Evidently, every Eulerian bipartite graph is even-cycle decomposable. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

##### Transversal signed-graphic matroids

Signed-graphic matroids are a genuine generalization of graphic matroids, and a lot of research has been done on determining to what extent we can transfer properties of graphic matroids to signed-graphic matroids. In this talk we focus on two theorems from the 1970s. The first one, due to Matthews, characterizes graphs whose bicircular matroids are graphic. We characterize graphs whose bicircular matroids are signed-graphic. The second one, due to Bondy and Las Vergnas, characterizes graphs whose cycle matroids are transversal. We attempt to characterize signed graphs whose frame matroids are transversal. Time permitting, we will discuss the issue of basis counting in different classes of matroids, and progress on a related conjecture of Welsh.

##### On Relative Approximations in Geometric Hypergraphs

Motivated by range counting problems, relative approximations have become a central tool in computational geometry. In fact, they were introduced by Har-Peled and Sharir, who derived them from the seminal work of Li, Long, and Srinivasan in the theory of machine learning. In this talk I will discuss properties of relative approximations, and present improved upper bounds for their size under certain favorable assumptions. Our approach is probabilistic, where we apply the constructive version of the Asymmetric Lovasz Local Lemma.

##### A polynomial time algorithm for lossy population recovery

PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length n from lossy samples: for some parameter μ each coordinate of the sample is preserved with probability μ and otherwise is replaced by a ‘?’.