Seminars and Colloquia by Series

Nearly orthogonal vectors

Series
Combinatorics Seminar
Time
Friday, October 19, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Boris BukhCarnegie Mellon University
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.

Graph powering and spectral robustness

Series
Combinatorics Seminar
Time
Friday, October 12, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peter RalliPrinceton University
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.)

Large girth approximate Steiner triple systems

Series
Combinatorics Seminar
Time
Friday, September 28, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lutz WarnkeGeorgia Tech
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.

Hamiltonicity in randomly perturbed hypergraphs.

Series
Combinatorics Seminar
Time
Friday, September 21, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yi ZhaoGeorgia State University
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.

Long progressions in sumsets

Series
Combinatorics Seminar
Time
Friday, September 14, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ernie CrootGeorgia Tech
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.

A Generalization of the Harary-Sachs Theorem to Hypergraphs

Series
Combinatorics Seminar
Time
Friday, September 7, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Joshua CooperUniversity of South Carolina
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.

Constructive Polynomial Partitioning for Algebraic Curves in 3-space

Series
Combinatorics Seminar
Time
Monday, August 20, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Esther EzraGeorgia Tech
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.

Intersections of Finite Sets: Geometry and Topology

Series
Combinatorics Seminar
Time
Friday, April 27, 2018 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Florian FrickCornell University
Given a collection of finite sets, Kneser-type problems aim to partition this collection into parts with well-understood intersection pattern, such as in each part any two sets intersect. Since Lovász' solution of Kneser's conjecture, concerning intersections of all k-subsets of an n-set, topological methods have been a central tool in understanding intersection patterns of finite sets. We will develop a method that in addition to using topological machinery takes the topology of the collection of finite sets into account via a translation to a problem in Euclidean geometry. This leads to simple proofs of old and new results.

On large multipartite subgraphs of H-free graphs

Series
Combinatorics Seminar
Time
Thursday, March 29, 2018 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jan VolecMcGill
A long-standing conjecture of Erdős states that any n-vertex triangle-free graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most 4n^2/25+O(n) edges. In the case of H=K_6, we actually prove the exact bound 4n^2/25 and show that this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of Füredi on stable version of Turán's theorem. This is a joint work with P. Hu, B. Lidický, T. Martins-Lopez and S. Norin.

Pages