Let H be a graph. We show that if r is large enough as a function of H,
then the r-partite Turán graph maximizes the number of copies of H among
all Kr+1-free graphs on a given number of vertices. This confirms a
conjecture of Gerbner and Palmer.
We discuss small-ball probability estimates of the smallest singular value of a rather general ensemble of random matrices which we call “inhomogeneous”. One of the novel ingredients of our family of universality results is an efficient discretization procedure, applicable under unusually mild assumption. Most of the talk will focus on explaining the ideas behind the proof of the first ingredient. Partially based on the joint work with Tikhomirov and Vershynin, and an ongoing joint work with Fernandez and Tatarko. We will also mention a related work on the cube minimal dispersion, joint with Litvak.
We show that in Euclidean 3-space any closed curve which contains the unit sphere in its convex hull has length at least $4\pi$, and characterize the case of equality, which settles a conjecture of Zalgaller. Furthermore, we establish an estimate for the higher dimensional version of this problem by Nazarov, which is sharp up to a multiplicative constant, and is based on Gaussian correlation inequality. Finally we discuss connections with sphere packing problems, and other optimization questions for convex hull of space curves. This is joint work with James Wenk.
In this talk, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph $K_{m,n}$, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189--202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613--624].
We exploit the full symmetry of the problem by developing a block-diagonalization of the underlying matrix algebra and use it to improve bounds on several concrete instances. Our results imply that $\mathrm{cr}(K_{10,n}) \geq 4.87057 n^2 - 10n$, $\mathrm{cr}(K_{11,n}) \geq 5.99939 n^2-12.5n$, $\mathrm{cr}(K_{12,n}) \geq 7.25579 n^2 - 15n$, $\mathrm{cr}(K_{13,n}) \geq 8.65675 n^2-18n$ for all~$n$. The latter three bounds are computed using a new relaxation of the original semidefinite programming bound, by only requiring one small matrix block to be positive semidefinite. Our lower bound on $K_{13,n}$ implies that for each fixed $m \geq 13$, $\lim_{n \to \infty} \text{cr}(K_{m,n})/Z(m,n) \geq 0.8878 m/(m-1)$. Here $Z(m,n)$ is the Zarankiewicz number: the conjectured crossing number of $K_{m,n}$.
This talk is based on joint work with Sven Polak.
There is a natural notion of `degree’ for functions from the symmetric group to the complex numbers, which translates roughly to saying the function counts certain weighted patterns. Low degree class functions have a classical interpretation in terms of the cycle structure of permutations. I will explain how to translate between pattern counts to cycle structure using a novel symmetric function identity analogous to the Murnaghan-Nakayama identity. This relationship allows one to lift many probabilistic properties of permutation statistics to certain non-uniform distributions, and I will present some results in this direction. This is joint work with Brendon Rhoades.
We study the minimum number of paths needed to express the edge set of a given graph as the symmetric difference of the edge sets of the paths. This can be seen as a weakening of Gallai’s path decomposition problem, and a variant of the “odd cover” problem of Babai and Frankl which asks for the minimum number of complete bipartite graphs whose symmetric difference gives the complete graph. We relate this “path odd-cover” number of a graph to other known graph parameters and prove some bounds. Joint work with Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Frederickson, and Puck Rombach.
The celebrated Hajnal-Szemerédi theorem gives best possible minimum degree conditions for clique-factors in graphs. There have been some recent variants of this result into several settings, each of which has some sort of randomness come into play. We will give a survey on these problems and the recent developments.
We study the locations of complex zeroes of independence polynomials of bounded degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer's result on the optimal zero-free disk, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree $\Delta$ have a zero-free disk almost as large as the optimal disk for graphs of maximum degree $\Delta$ established by Shearer (of radius $\sim1/(e\Delta)$). Up to logarithmic factors in $\Delta$ this is optimal, even for hypergraphs with all edge-sizes strictly greater than $2$. We conjecture that for $k\geq 3$, there exist families of $k$-uniform linear hypergraphs that have a much larger zero-free disk of radius $\Omega(\Delta^{-1/(k-1)})$. We establish this in the case of linear hypertrees. Joint work with David Galvin, Gwen McKinley, Will Perkins and Prasad Tetali.
We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth. Our proof builds on the method of iterative absorption for the existence of designs by Glock, Kühn, Lo, and Osthus while incorporating a "high girth triangle removal process". In particular, we develop techniques to handle triangle-decompositions of polynomially sparse graphs, construct efficient high girth absorbers for Steiner triple systems, and introduce a moments technique to understand the probability our random process includes certain configurations of triples.
(Joint with Matthew Kwan, Mehtaab Sawhney, and Michael Simkin)
With applications in the analysis of political districtings, Markov chains have become and essential tool for studying contiguous partitions of geometric regions. Nevertheless, there remains a dearth of rigorous results on the mixing times of the chains employed for this purpose. In this talk we'll discuss a sub-exponential bound on the mixing time of the Glauber dynamics chain for the case of bounded-size contiguous partition classes on certain grid-like classes of graphs.
