# Seminars & Events for Discrete Mathematics Seminar

##### The structure of graphs with no cycles of length divisible by three

For a graph G, let #E(G) be the number of stable sets of even size and let #O(G) be the number of stable sets of odd size. We are interested in the relation between the structure of a graph and the value of |#E(G)-#O(G)|. As it turns out, |#E(G)-#O(G)| has small value in many natural situations, and the simplest examples where |#E(G)-#O(G)| is larger than 1 are complete graphs, and cycles of length divisible by 3. Kalai and Meshulam made a conjecture that if |#E(H)-#O(H)| is bounded for all induced subgraphs H of G, then the chromatic number of G is bounded; they also conjectured that if G has no induced cycle of length divisible by 3, then G has bounded chromatic number.

##### Three-coloring graphs with no induced 6-edge paths

Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Results of Kaminski and Lozin, and Hoyler, show that the problem remains NP-complete unless H is a disjoint union of paths. Recently the complexity of coloring graphs with a fixed-length induced path forbidden has received considerable attention, and only a few cases of that problem remain open for k-coloring when k>=4. However, little is known for 3-coloring. Recently we have settled the first open case for 3-coloring; namely we showed that deciding 3-colorability for graphs with no induced 6-edge paths can be done in polynomial time. In this talk we will discuss some of the ideas of the algorithm.

##### Turan's theorem for random graphs

PLEASE NOTE DIFFERENT TIME. CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. Write t_r(G) (resp. b_r(G)) for the maximum size of a K_r-free (resp. (r-1)-partite) subgraph of a graph G. Of course t_r(G) is at least b_r(G) for any G, while Turan's Theorem (or Mantel's Theorem if r = 3) says that equality holds if G = K_n.

##### Some wonderful conjectures (but very few theorems) at the boundary between analysis, combinatorics and probability

PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. Many problems in combinatorics, statistical mechanics, number theory and analysis give rise to power series (whether formal or convergent) of the form f(x,y) = sum_{n \ge 0} a_n(y) x^n, where a_n(y) are formal power series or analytic functions satisfying a_n(0) \neq 0 for n = 0,1 and a_n(0) = 0 for n \ge 2.

##### On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions

Let P be a collection of n points in the plane, each moving along some straight line and at unit speed. Three points of P form a Delaunay triangle if their circumscribing circle contains no further point of P. These triangles form the famous Delaunay triangulation, denoted by DT(P). We obtain an almost tight upper bound of O(n^{2+eps}), for any eps>0, on the maximum number of discrete changes that DT(P) experiences during this motion. Our analysis is cast in a purely topological setting; we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice. These assumptions hold for unit speed motions.

##### Simple eigenvalues of vertex-transitive graphs

A simple eigenvalue of a graph is an eigenvalue of the adjacency matrix with multiplicity 1. It has been observed that graphs having many simple eigenvalues tend to have small automorphism groups. The only vertex-transitive graph with all eigenvalues simple is K_2 and it is well-known that a k-regular vertex-transitive graph will have at most k+1 simple eigenvalues. We will look at structural properties of vertex-transitive graphs with many simple eigenvalues.

##### Fragile matroids and excluded minors

Matroids abstract the notions of linear/geometric/algebraic dependence. More specifically, a matroid consists of a finite collection of points, and a distinguished family of dependent subsets. PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.

##### Component games on regular graphs

We study the Maker-Breaker component game, played on the edge set of a regular graph. Given a graph G, the s-component (1:b) game is defined as follows: in every round Maker claims one free edge of G and Breaker claims b free edges. Maker wins this game if her graph contains a connected component of size at least s; otherwise, Breaker wins the game. For all values of Breaker's bias b, we determine whether Breaker wins (on every d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths. Joint work with Alon Naor.

##### Sum-free subgroups

The study of sum and product problems in finite fields motivates the investigation of additive structures in multiplicative subgroups of such fields. It turns out that such subgroups that are sufficiently large with respect to the size of the field must contain rich structures of additive relations, while even prime fields may contain sum-free multiplicative subgroups of substantial size. The study of this topic combines combinatorial techniques with tools from algebraic and analytic number theory. Joint work with Jean Bourgain.

##### Recent progress in distinct distances problems

PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. During 2013, significant progress has been made on several problems that are related to the Erdos distinct distances problem. In this talk I plan to briefly describe some of these results and the tools that they rely on. I will focus on the following two results.

##### Polynomial bounds for the grid-minor theorem

One of the key results in Robertson and Seymour's seminal work on graph minors is the grid-minor theorem, that every graph of sufficiently large treewidth contains any fixed grid as a minor. This theorem has found many applications in graph theory and algorithms. Let f(k) be maximum such that every graph of treewidth at least k contains a grid minor of size f(k). The best current quantitative lower bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that f(k) = Omega(sqrt{ log k / loglog k }), while the best known upper bound implies that f(k) = O(sqrt{ k / log k }). In this talk we present the first polynomial relationship between treewidth and grid-minor size, by showing that f(k) = Omega(k^d) for some constant d > 0. Joint work with Chandra Chekuri.

##### Hypergraphs of bounded disjointness

A k-uniform hypergraph is said to be intersecting if no pair of edges is disjoint. The maximal size of an intersecting k-uniform hypergraph with a given groundset is given by the beautiful and well-known theorem of Erdos, Ko and Rado. A k-uniform hypergraph is s-almost intersecting if every edge is disjoint from exactly s other edges. Gerbner, Lemons, Palmer, Patkos and Szecsi made a conjecture on the maximal number of edges in such a hypergraph. We prove a strengthened version of this conjecture and determine the extremal graphs. We also give some related results and conjectures. Joint work with Elizabeth Wilmer.

##### Geometric Discrepancy Via the Entropy Method

In this talk I will present new discrepancy bounds for set systems of bounded primal shatter dimension, with the property that these bounds are sensitive to the actual set sizes. These bounds are nearly-optimal. Such set systems are abstract, but they can be realized by simply-shaped regions, as halfspaces, balls, and octants in d dimensions, to name a few. Our analysis exploits the so-called Entropy method and the technique of partial coloring, combined with the existence of small packings.

##### Maximal non-Hamiltonian graphs

One way to study Hamiltonicity of graphs is to consider (edge-)maximal non-Hamiltonian graphs. For instance, Ore's sufficient condition for a graph to be Hamiltonian can be rephrased as saying that in any maximal non-Hamiltonian graph of order n, there are two nonadjacent vertices whose degrees sum to less than n. In fact, the Bondy--Chvatal Theorem says that this property holds for every pair of nonadjacent vertices. It is easy to show that every maximal non-Hamiltonian graph of order at least 3 is spanned by a figure-eight graph (the union of two cycles sharing a point, where we allow each cycle to degenerate to an edge). I conjecture that every 2-connected maximal non-Hamiltonian graph is spanned by a theta graph (a subdivision of K_{1,1,2}) and have shown that this holds for all graphs of order at most 20.

##### The tropical Laplacian

**This is a joint Discrete Mathematics / Algebraic Geometry seminar. **The tropical Laplacian is a symmetric square matrix associated with a balanced graph on a sphere, defined in a similar way to the Laplacian of an abstract graph. We will see by examples how the tropical Laplacian appears in the study of polytopes, matroids, and graphs. The speaker will pose many elementary questions on tropical Laplacians. A related but independent talk explaining the geometric origin of the questions will be given in the Tuesday (March 4) Algebraic Geometry Seminar.

##### Between 2- and 3-colorability

A classical topic in the theory of random graphs is the chromatic number of G_{n,p}. We will discuss finer notions of colorability for random graphs at the bottom end of this scale. (Joint work with Alan Frieze.)

##### Locally decodable codes and geometry of tensor norms

PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. Locally decodable codes (LDCs) are error correcting codes that allow any single message symbol to be retrieved from a small number 'q' of randomly selected codeword symbols.

##### The existence of designs

PLEASE CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT. A Steiner Triple System on a set X is a collection T of 3-element subsets of X such that every pair of elements of X is contained in exactly one of the triples in T.

##### The structure of almost linear Boolean functions

A Boolean function f: {0,1}^n -> {0,1} is "linear" if it is a linear combination of its inputs. It is a simple exercise to show that a linear Boolean function depends on at most one coordinate. Friedgut, Kalai and Naor showed that if f is "almost" linear then it is "close" to a function depending on at most one coordinate. We consider generalizations of their result to functions on S_n and on the Johnson association scheme. Joint work with David Ellis and Ehud Friedgut.

##### The Green-Tao Theorem and a Relative Szemerédi Theorem

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and recent joint work with David Conlon and Yufei Zhao simplifying the proof. The main new ingredient in the proof of the Green-Tao theorem is a relative Szemerédi theorem, which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. Our main advance is a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. The key component in our proof is an extension of the regularity method to sparse hypergraphs.