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

Series: Combinatorics Seminar

The purpose of this talk is to explain the following result.
Let n > 2 be an integer. Let H be a 3-connected minor of a
3-connected graph G. If G is sufficiently large (relative to
n and the size of H) then G has a 3-connected minor obtained
from H by “adding” K_{3,n} or W_n.

Series: Combinatorics Seminar

We discuss some recent developments on the critical behavior of percolation on finite random networks. In a seminal paper, Aldous (1997) identified the scaling limit for the component sizes in the critical window of phase transition for the Erdos-Renyi random graph (ERRG). Subsequently, there has been a surge in the literature, revealing several interesting scaling limits of these critical components, namely, the component size, diameter, or the component itself when viewed as a metric space. Fascinatingly, when the third moment of the asymptotic degree distribution is finite, many random graph models has been shown to exhibit a universality phenomenon in the sense that their scaling exponents and limit laws are the same as the ERRG. In contrast, when the asymptotic degree distribution is heavy-tailed (having an infinite third moment), the limit law turns out to be fundamentally different from the ERRG case and in particular, becomes sensitive to the precise asymptotics of the highest degree vertices. In this talk, we will focus on random graphs with a prescribed degree sequence. We start by discussing recent scaling limit results, and explore the universality classes that arise from heavy-tailed networks. Of particular interest is a new universality class that arises when the asymptotic degree distribution has an infinite second moment. Not only it gives rise to a completely new universality class, it also exhibits several surprising features that have never been observed in any other universality class so far. This is based on joint works with Shankar Bhamidi, Remco van der Hofstad, Johan van Leeuwaarden and Sanchayan Sen.

Series: Combinatorics Seminar

How can d+k vectors in R^d be arranged so that they are as close
to orthogonal as possible? We show intimate connection of this problem to
the problem of equiangular lines, and to the problem of bounding the first
moment of isotropic measures. Using these connections, we pin down the
answer precisely for several values of k and establish asymptotics for all k.
Joint work with Chris Cox.

Series: Combinatorics Seminar

Spectral algorithms, such as principal component analysis and spectral
clustering, typically require careful data transformations to be
effective: upon observing a matrix A, one may look at the spectrum of
ψ(A) for a properly chosen ψ. We propose a simple and generic
construction for sparse graphs based on graph powering. It is shown
that graph powering regularizes the graph and decontaminates its
spectrum in the following sense: (i) If the graph is drawn from the
sparse Erd˝os-R´enyi ensemble, which has no spectral gap, it is shown
that graph powering produces a “maximal” spectral gap, with the latter
justified by establishing an Alon-Boppana result for powered graphs;
(ii) If the graph is drawn from the sparse SBM, graph powering is
shown to achieve the fundamental limit for weak recovery.
(Joint work with E. Abbe, E. Boix, C. Sandon.)

Series: Combinatorics Seminar

In 1973 Erdos asked whether there are n-vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integer g \ge 4 for which some g-element vertex-set contains at least g-2 triples.)
We answer this question, by showing existence of approximate Steiner triple systems with arbitrary high girth. More concretely, for any fixed \ell \ge 4 we show that a natural constrained random process typically produces a partial Steiner triple system with (1/6-o(1))n^2 triples and girth larger than \ell. The process iteratively adds random triples subject to the constraint that the girth remains larger than \ell. Our result is best possible up to the o(1)-term, which is a negative power of n.
Joint work with Tom Bohman.

Series: Combinatorics Seminar

For integers k>2 and \ell0, there exist \epsilon>0 and C>0 such that for sufficiently large n that is divisible by k-\ell,
the union of a k-uniform hypergraph with minimum vertex degree \alpha n^{k-1} and a binomial random k-uniform hypergraph G^{k}(n,p) on the same n-vertex set
with p\ge n^{-(k-\ell)-\epsilon} for \ell\ge 2 and p\ge C n^{-(k-1)} for \ell=1 contains a Hamiltonian \ell-cycle with high probability. Our result is best possible up to
the values of \epsilon and C and completely answers a question of Krivelevich, Kwan and Sudakov.
This is a joint work with Jie Han.

Series: Combinatorics Seminar

An old question in additive number theory is determining the length of the longest progression in a sumset A+B = {a + b : a in A, b in B}, given that A and B are "large" subsets of {1,2,...,n}. I will survey some of the results on this problem, including a discussion of the methods, and also will discuss some open questions and conjectures.

Series: Combinatorics Seminar

We give a complete description of the coefficients of the characteristic polynomial $\chi_H(\lambda)$ of a ($k$-uniform) hypergraph $H$, defined by the hyperdeterminant $\det(\mathcal{A} - \lambda \mathcal{I})$, where $\mathcal{A}$ is of the adjacency tensor/hypermatrix of $H$, and the hyperdeterminant is defined in terms of resultants of homogeneous systems associated to its argument. The co-degree $k$ coefficients can be obtained by an explicit formula yielding a linear combination of subgraph counts in $H$ of certain ``Veblen hypergraphs''. This generalizes the Harary-Sachs Theorem for graphs, provides hints of a Leibniz-type formula for symmetric hyperdeterminants, and can be used in concert with computational algebraic methods to obtain the full characteristic polynomial of many new hypergraphs, even when the degrees of these polynomials is enormous. Joint work with Greg Clark of USC.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

A recent extension by Guth (2015) of the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial for a given set of k-dimensional varieties in R^d, such that its zero set subdivides space into open cells, each meeting only a small fraction of the given varieties. For k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. This, in particular, applies to the setting of n algebraic curves, or, in fact, just lines, in 3-space. In this work we present an efficient algorithmic construction for this setting almost matching the bounds of Guth (2015); For any D > 0, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open cells, each of which meets at most O(n/D^2) curves from the input. The construction time is O(n^2), where the constant of proportionality depends on the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation using a range search machinery. As a main application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently been studied by Aronov et al. Joint work with Boris Aronov and Josh Zahl.