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

Series: Combinatorics Seminar

This is Lecture 3 of a series of 3 lectures. See the abstract on Tuesday's ACO colloquium of this week.(Please note that this lecture will be 80 minutes' long.)

Series: Combinatorics Seminar

I will describe two new local limit theorems on the
Heisenberg group, and on an arbitrary connected, simply connected
nilpotent Lie group. The limit theorems admit general driving measures
and permit testing against test functions with an arbitrary
translation on the left and the right. The techniques introduced include
a rearrangement group action, the Gowers-Cauchy-Schwarz inequality, and
a Lindeberg replacement scheme which approximates the driving measure
with the corresponding heat kernel. These
results generalize earlier local limit theorems of Alexopoulos and
Breuillard, answering several open questions. The work on the
Heisenberg group is joint with Persi Diaconis.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

A tight k-uniform \ell-cycle, denoted by TC_\ell^k, is a k-uniform hypergraph whose vertex set is v_0, ..., v_{\ell-1}, and the edges are all the k-tuples {v_i, v_{i+1}, \cdots, v_{i+k-1}}, with subscripts modulo \ell. Motivated by a classic result in graph theory that every n-vertex cycle-free graph has at most n-1 edges, Sos and, independently, Verstraete asked whether for every integer k, a k-uniform n-vertex hypergraph without any tight k-uniform cycles has at most \binom{n-1}{k-1} edges. In this talk I will present a construction giving negative answer to this question, and discuss some related problems. Joint work with Jie Ma.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

We study the number of random permutations needed to invariably generate the symmetric group, S_n, when the distribution of cycle counts has the strong \alpha-logarithmic property. The canonical example is the Ewens sampling formula, for which the number of k-cycles relates to a conditioned Poisson random variable with mean \alpha/k. The special case \alpha=1 corresponds to uniformly random permutations, for which it was recently shown that exactly four are needed.For strong \alpha-logarithmic measures, and almost every \alpha, we show that precisely $\lceil( 1- \alpha \log 2 )^{-1} \rceil$ permutations are needed to invariably generate S_n. A corollary is that for many other probability measures on S_n no bounded number of permutations will invariably generate S_n with positive probability. Along the way we generalize classic theorems of Erdos, Tehran, Pyber, Luczak and Bovey to permutations obtained from the Ewens sampling formula.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

For a fixed graph $G$, let $\mathcal{L}_G$ denote the family of Lipschitz functions $f:V(G) \rightarrow \mathbb{R}$ such that $0 = \sum_u f(u)$.
The \emph{spread} of $G$ is denoted $c(G) := \frac{1}{|V(G)|} \max_{f \in \mathcal{L}_G} \sum_u f(u)^2$ and the subgaussian constant is $e^{\sigma_G^2} := \sup_{t > 0} \max_{f \in \mathcal{L}_G} \left( \frac{1}{|V(G)|} \sum_u e^{t f(u)} \right)^{2/t^2}$.
Motivation of these parameters comes from their relationship with the isoperimetric number of a graph (given a number $t$, find a set $W \subset V(G)$ such that $2|W| \geq |V(G)|$ that minimizes $i(G,t) := |\{u : d(u, W) \leq t \}|$).
While the connection to the isoperimetric number is interesting, the spread and subgaussian constant have not been any easier to understand.
In this talk, we will present results that describe the functions $f$ achieving the optimal values.
As a corollary to these results, we will resolve two conjectures (one false, one true) about these parameters.
The conjectures that we resolve are the following.
We denote the Cartesian product of $G$ with itself $d$ times as $G^d$.
Alon, Boppana, and Spencer proved that the set $\{u: f(u) < k\}$ for extremal function $f$ for the spread of $G^d$ gives a value that is asymptotically close to the isoperimetric number when $d, t$ grow at specific rates and $k=0$; and they conjectured that the value is exactly correct for large $d$ and $k,t$ in ``appropriate ranges.''
The conjecture was proven true for hypercubes by Harper and the discrete torus of even order by Bollob\'{a}s and Leader.
Bobkov, Houdr\'{e}, and Tetali constructed a function over a cycle that they conjectured to be optimal for the subgaussian constant, and it was proven correct for cycles of even length by Sammer and Tetali.
This work appears in the manuscript https://arxiv.org/abs/1705.09725 .

Series: Combinatorics Seminar

Suppose we want to find the largest independent set or maximal cut in a sparse Erdos-Renyi graph, where the average degree is constant. Many algorithms proceed by way of local decision rules, for instance, the "nibbling" procedure. I will explain a form of local algorithms that captures many of these. I will then explain how these fail to find optimal independent sets or cuts once the average degree of the graph gets large. There are some nice connections to entropy and spin glasses.

Series: Combinatorics Seminar

Official School Holiday: Thanksgiving Break