- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

We show that for all \el an \epsilon>0 there is a constant c=c(\ell,\epsilon)>0 such that every \ell-coloring of the triples of an N-element set contains a subset S of size c\sqrt{\log N} such that at least 1-\epsilon fraction of the triples of S have the same color. This result is tight up to the constant c and answers an open question of Erd\H{o}s and Hajnal from 1989 on discrepancy in hypergraphs. For \ell \geq 4 colors, it is known that there is an \ell-coloring of the triples of an N-element set whose largest monochromatic subset has cardinality only \Theta(\log \log N). Thus, our result demonstrates that the maximum almost monochromatic subset that an \ell-coloring of the triples must contain is much larger than the corresponding monochromatic subset. This is in striking contrast with graphs, where these two quantities have the same order of magnitude. To prove our result, we obtain a new upper bound on the \ell-color Ramsey numbers of complete multipartite 3-uniform hypergraphs, which answers another open question of Erd\H{o}s and Hajnal. (This is joint work with D. Conlon and J. Fox.)

Series: Combinatorics Seminar

In this work (joint with Derrick Hart), we show that there exists a constant c > 0 such that the following holds for all n sufficiently large: if S is a set of n monic polynomials over C[x], and the product set S.S = {fg : f,g in S}; has size at most n^(1+c), then the sumset S+S = {f+g : f,g in S}; has size \Omega(n^2). There is a related result due to Mei-Chu Chang, which says that if S is a set of n complex numbers, and |S.S| < n^(1+c), then |S+S| > n^(2-f(c)), where f(c) -> 0 as c -> 0; but, there currently is no result (other than the one due to myself and Hart) giving a lower bound of the quality >> n^2 for |S+S| for a fixed value of c. Our proof combines combinatorial and algebraic methods.

Series: Combinatorics Seminar

The study of random tilings of planar lattice regions goes back to the solution of the dimer model in the 1960's by Kasteleyn, Temperley and Fisher, but received new impetus in the early 1990's, and has since branched out in several directions in the work of Cohn, Kenyon, Okounkov, Sheffield, and others. In this talk, we focus on the interaction of holes in random tilings, a subject inspired by Fisher and Stephenson's 1963 conjecture on the rotational invariance of the monomer-monomer correlation on the square lattice. In earlier work, we showed that the correlation of a finite number of holes on the triangular lattice is given asymptotically by a superposition principle closely paralleling the superposition principle for electrostatic energy. We now take this analogy one step further, by showing that the discrete field determined by considering at each unit triangle the average orientation of the lozenge covering it converges, in the scaling limit, to the electrostatic field. Our proof involves a variety of ingredients, including Laplace's method for the asymptotics of integrals, Newton's divided difference operator, and hypergeometric function identities.

Series: Combinatorics Seminar

Part of Spielman and Teng's smoothed analysis of the Simplex algorithm relied on showing that most minors of a typical random rectangular matrix are well conditioned (do not have any singular values too close to zero). Motivated by this, Vershynin asked the question as to whether it was typically true that ALL minors of a random rectangular matrix are well conditioned. Here I will explain why that the answer to this question is in fact no: Even an n by 2n matrix will typically have n by n minors which have singular values exponentially close to zero.

Series: Combinatorics Seminar

In this talk, I will discuss chip-firing games on graphs, and the related Jacobian groups. Additionally, I will describe elliptic curves over finite fields, and how such objects also have group structures. For a family of graphs obtained by deforming the sequence of wheel graphs, the cardinalities of the Jacobian groups satisfy a nice reciprocal relationship with the orders of elliptic curves as we consider field extensions. I will finish by discussing other surprising ways that these group structures are analogous. Some of this research was completed as part of my dissertation work at the University of California, San Diego under Adriano Garsia's guidance.

Series: Combinatorics Seminar

Expanders via Random Spanning Trees Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_{n,p}, for p > c (log n)/n, two spanning trees give an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary — each spanning tree can be produced independently using an algorithm by Aldous and Broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with O(n log n/eps^2) edges that achieve approximation within factors 1+eps and 1-eps. Their methods, based on independent sampling of edges, need Omega(n log n) edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size O(n) that approximate every cut to within a factor of O(log n). This is joint work with Navin Goyal and Santosh Vempala.

Series: Combinatorics Seminar

In 1968, Vizing proposed the following conjecture which claims that if G is an edge chromatic critical graph with n vertices, then the independence number of G is at most n/2. In this talk, we will talk about this conjecture and the progress towards this conjecture.

Series: Combinatorics Seminar

Given a set of linear equations Mx=b, we say that a set of integers S is (M,b)-free if it contains no solution to this system of equations. Motivated by questions related to testing linear-invariant Boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and Xie: we say that a set of integers S \subseteq [n], is \epsilon-far from being (M,b)-free if one needs to remove at least \epsilon n elements from S in order to make it (M,b)-free. The conjecture was that for any system of homogeneous linear equations Mx=0 and for any \epsilon > 0 there is a *constant* time algorithm that can distinguish with high probability between sets of integers that are (M,0)-free from sets that are \epsilon-far from being (M,0)-free. Or in other words, that for any M there is an efficient testing algorithm for the property of being (M,0)-free. In this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogeneous linear equations. As opposed to most results on testing Boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of Gowers, R\"odl et al. and Austin and Tao.

Series: Combinatorics Seminar

We will discuss some extensions/generalizations of the striking and elegant fact (proved independently by Furstenberg and Sarkozy) that any subset of the integers of positive upper density necessarily contains two distinct elements whose difference is a perfect square. This is joint work with Akos Magyar.

Series: Combinatorics Seminar

Consider the following random graph process. We begin with the empty graph on n vertices and add edges chosen at random one at a time. Each edge is chosen uniformly at random from the collection of pairs of vertices that do not form triangles when added as edges to the existing graph. In this talk I discuss an analysis of the triangle-free process using the so-called differential equations method for random graph processes. It turns out that with high probability the triangle-free process produces a Ramsey R(3,t) graph, a triangle-free graph whose independence number is within a multiplicative constant factor of the smallest possible.