# Seminars & Events for Discrete Mathematics Seminar

##### Domination when the stars are out

We algorithmize the recent structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that several domination problems are fixed-parameter tractable, and even possess polynomial-sized kernels, on claw-free graphs. To complement these results, we establish these problems are not fixed-parameter tractable on the slightly larger class of graphs that exclude $K_{1,4}$ as an induced subgraph. Our results provide a dichotomy for $K_{1,L}$-free graphs and show that the problems are fixed-parameter tractable if and only if $L\geq 3$. The algorithms we obtain generalize and unify several earlier algorithms for problems on claw-free graphs, and turn the existential decomposition by Chudnovsky and Seymour into an efficient constructive decomposition.

##### Erdos-Ko-Rado-like theorems for rainbow matchings

Let $f(n,k,r)$ be the smallest number such that every set of more than $f(n,k,r)$ r-sets in $[n]$ contains a matching of size $k$. The Erdos-Ko-Rado theorem states that $f(n,2,r)=(n-1)(r-1)$. A natural conjecture is that if $F_1, F_2, ...F_k \subseteq {[n]}{r}$ are all of size larger than $f(n,k,r)$ then they possess a rainbow matching, that is, a choice of disjoint edges, one from each $F_i$. This is known for $k=2$ (Matsumoto-Tokushige) and $r=2$ (Meshulam). We consider the analogue of this conjecture in $r$-partite hypergraphs, and prove the cases $r=3$ and $k=2$.

Joint work with David Howard.

##### The size of a hypergraph and its matching number

More than 40 years ago, Erdos asked to determine the maximum possible number of edges in a $k$-uniform hypergraph on n vertices with no matching of size $t$ (i.e., with no $t$ disjoint edges). Although this is one of the most basic problem on hypergraphs, progress on Erdos' question remained elusive. In addition to being important in its own right, this problem has several interesting applications. In this talk we present a solution of Erdos' question for $t < n/(3k^2$). This improves upon the best previously known range $t = O (n/k3)$, which dates back to the 1970's.

Joint work with H. Huang and P. Loh.

##### On the strong coloring of graphs with bounded degree

Let $G$ be a graph with $n$ vertices and let $r$ be a number dividing $n$. We say that $G$ is strongly $r$-colorable if for every partition of the vertices of $G$ into sets of size $r$, there exists a proper coloring of $G$ in which every set in the partition is colored in all colors. Alon was the first who showed that if $r>cd$ then $G$ must be strongly $r$-colorable, where $d$ is the maximum degree in the graph and $c$ is some constant number. This result raises the question, for a fixed number $d$, what is the minimum number $s(d)$ with the property that every graph with maximum degree $d$ is strongly $s(d)$-colorable? It is not hard to show that $s(d)$ is at least $2d$ and the natural conjecture is $s(d)=2d$. The result closest to this conjecture is Haxell's proof that $s(d) \leq 11d/4+o(d)$.

##### Existence of small families of t-wise independent permutations and t-designs via local limit theorems

We show existence of rigid combinatorial objects that previously were not known to exist. Specifically, we consider two families of objects:

##### Subgraph densities in signed graphs and local extremal graph problems

Let G be a graph whose edges are signed by +1 or -1. We can "count" labeled copies of a graph F in G by multiplying the edge signatures and summing over all copies of F. The density of F in G is obtained by dividing by the total number of maps from V(F) to V(G). There are interesting inequalities between the densities of various subgraphs in signed graphs. One of the main inequalities is that the density of a bipartite graph with girth 2r cannot exceed the density of the 2r-cycle. This study is motivated by the Simonovits--Sidorenko conjecture, which states that the density of a bipartite graph F with m edges in any graph G is at least the m-th power of the edge density of G. Another way of stating this is that the graph G with given edge density minimizing the number of copies of F is, asymptotically, a random graph.

##### Beyond Total Unimodularity

A matrix is TOTALLY UNIMODULAR if the determinant of each square submatrix is in {-1, 0, 1}. Such matrices are a cornerstone of the theory of integer programming. The deepest result on such matrices is Seymour's decomposition theorem. The only known way to test efficiently whether a matrix is totally unimodular makes use of this theorem. Recently, Whittle introduced several classes of matrices with similar properties: the determinants of the submatrices are restricted to a certain set. In this talk I will discuss some results from the theory of totally unimodular matrices from the point of view of matroid theory, and outline which of those results will, won't, or might generalize to Whittle's classes. In particular I will sketch an extension of Kirchhoff's matrix tree theorem to quaternionic unimodular matrices.

##### Graph regularity and removal lemmas

Szemeredi's regularity lemma is one of the most powerful tools in graph theory. It was introduced by Szemeredi in his proof of the celebrated Erdos-Turan conjecture on long arithmetic progressions in dense subsets of the integers. Roughly speaking, it says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost all pairs of parts is random-like. One of the most important applications is the graph removal lemma, which roughly says that every graph with few copies of a fixed graph H can be made H-free by removing few edges. It remains a significant problem to estimate the bounds in the regularity lemma and the removal lemma, and their variants. In this talk I discuss recent joint work with David Conlon which makes progress on this problem.

##### Noisy interpolation of sparse polynomials, and applications

Let f in $F_q[x]$ be a polynomial of degree $d < q/2$. It is well-known that f can be uniquely recovered from its values at some 2d points even after some small fraction of the values are corrupted. In this talk we will establish a similar result for sparse polynomials. We show that a k-sparse polynomial $f$ in $F_q[x]$ of degree $d < q/2$ can be recovered from its values at O(k) randomly chosen points, even if a small fraction of the values of f are adversarially corrupted. Our proof relies on an iterative technique for analyzing the rank of a random minor of a matrix. We use the same technique to establish a collection of other results on locally decodable codes and rigid matrices. Based on joint work with Sergey Yekhanin.

##### The chromatic number of random Cayley graphs

The study of random Cayley graphs of finite groups is related to the investigation of expanders and to problems in combinatorial number theory and in information theory. I will discuss this topic, focusing on the question of estimating the chromatic number of a random Cayley graph of a given group with a prescribed number of generators.

##### On Sidorenko's Conjecture

The Erdos-Simonovits-Sidorenko conjecture is well-known in combinatorics but it has equivalent formulations in analysis and probability theory. The shortest formulation is an integral inequality related to Mayer integrals in statistical mechanics and Feynman integrals in quantum field theory. We present new progress in the area. Part of the talk is based on joint results with J.L. Xiang Li. In particular we present a type of calculus (based on logarithmic functions) which can be used to prove inequalities between subgraph densities.

##### Subspace evasive sets

We describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed 'subspace-evasive' sets, started in the work of Pudlak and Rodl (2004) who showed how such constructions over the binary field can be used to construct explicit Ramsey graphs. More recently, Guruswami (2011) showed that, over large finite fields (of size polynomial in n), subspace evasive sets can be used to obtain explicit list-decodable codes with optimal rate and constant list-size. We construct subspace evasive sets over large fields (polynomial in n) and use them to derive the applications to list-decodable codes discovered by Guruswami. Our construction employs both combinatoric and algebraic methods.

##### New Classes of Tournaments Satisfying the Erdos-Hajnal Conjecture

The Erdos-Hajnal conjecture states that for every graph $H$ there exists a constant $c>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $|G|^c$. The conjecture is still open. However some time ago a version for tournaments was proven to be equivalent to the original. In the tournament version, graphs are replaced by tournaments, and cliques and stable sets by transitive subtournaments. Both the tournament and the graph versions of the conjecture are known to be true for some small graphs (or tournaments) $H$, and there are operations that build bigger graphs (or tournaments) for which the conjecture holds. I will show the conjecture for an infinite class of tournaments that is not obtained in the way described above.

##### The Traveling Salesman Problem: A Blueprint for Optimization

Given a list of cities along with the cost of travel between each pair of them, the traveling salesman problem is to find the cheapest way to visit them all and return to your starting point. Easy to state, but

difficult to solve. In this talk we discuss the problem's history, applications, and computation, laying out a blueprint for future work in discrete optimization and the practical solution of large-scale, possibly intractable, decision models.

##### Homology of Clique Complexes and an Application to Algebraic Geometry

To any graph $G$ one can associate a simplicial complex $C(G)$, called the clique complex of $G$, whose simplices are in one-to-one correspondence with the complete subgraphs of $G$. It is thus natural to study the homology groups of $C(G)$ in connection to properties of the graph $G$. I will be interested in a special class of graphs, possessing a large group of symmetries, and particularly in Kneser graphs. The relevance of these graphs to algebraic geometry (no knowledge of which will be assumed in the talk) is that the homology of their clique complexes controls the syzygies of projective embeddings of products of projective spaces. As one of the toy examples, I will explain how computing a single homology group allows one to deduce that matrices of rank 1 are defined by the vanishing of their 2x2 minors.

##### Pareto Optimal Solutions for Smoothed Analysts

Consider an optimization problem with n binary variables and $d+1$ linear objective functions. Each valid solution in ${0,1}^n$ gives rise to an objective vector in $R^{d+1}$, and one often wants to enumerate the Pareto optima among them. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in $n$ (Roeglin, Teng, FOCS 2009). Unfortunately, the bound obtained had a rather bad dependence on $d$; roughly $n^{d^d}$. In this paper we show a significantly improved

bound of $n^{2d}$.

##### Tangles, Trees, and Flowers

Identifiable regions of high connectivity in a matroid or graph are captured by the notion of ``tangles''. For a tangle of order $k$ in a matroid or graph that satisfies a certain robustness condition, we describe a tree decomposition of the matroid or graph that displays, up to a certain natural equivalence, all of the $k$-separations of the matroid or graph that are non-trivial with respect to the tangle. This is joint work

with Geoff Whittle.

##### On the Diameter of Polytopes

Santos' construction of counter-examples to the Hirsch conjecture is based on the existence of prismatoids of dimension $d$ of width greater than $d$. The case $d=5$ being the smallest one in which this can possibly occur, we here study the width of 5-dimensional prismatoids, obtaining the following results:

- There are 5-prismatoids of width six with only 25 vertices, versus the 48 vertices in Santos' original construction. This leads to lowering the dimension of the non-Hirsch polytopes from 43 to only 20.

- There are 5-prismatoids with n vertices and $width \Omega(n^(1/2))$ for arbitrarily large $n$.

This is joint work with Francisco Santos and Christophe Weibel.

##### Mantel's Theorem for Random Graphs

We'll discuss a few results concerning triangles in the random graph $G = G(n,p)$, in particular answering (up to a constant factor in the first case):

When (ie for what $p= p(n))$ is it true that the maximum sizes of triangle-free and bipartite subgraphs of $G$ coincide?

When is it true that the triangles of $G$ span its cycle space?

The first question dates to Babai, Simonovits and Spencer in 1990, while the second is an instance of a more recent question of M. Kahle.

Joint work with Bobby DeMarco and Arran Hamm.

##### A theorem on plane graphs

We prove a theorem about face-paths in 2-connected plane graphs, which has as a corollary Thomassen's well-known result that 4-connected planar graphs are Hamilton-connected (a strong extension of the famous result of Tutte stating that 4-connected planar graphs are Hamiltonian).