## Seminars and Colloquia by Series

### Forbidding tight cycles in hypergraphs

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

### Ewens sampling and invariable generation

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

### TBA by P. Tetali

Series
Combinatorics Seminar
Time
Friday, January 12, 2018 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Samuel DittmerMath Department, UCLA

### Finding the Extremal Functions for the Spread and the Subgaussian Constant

Series
Combinatorics Seminar
Time
Friday, December 8, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Matthew YanceyInst. for Defense Analysis
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 .

### Sub-optimality of local algorithms for some problems on sparse random graphs

Series
Combinatorics Seminar
Time
Friday, December 1, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mustazee RahmanMIT
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.

### No Seminar: Thanksgiving Break

Series
Combinatorics Seminar
Time
Friday, November 24, 2017 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
noneGeorgia Tech
Official School Holiday: Thanksgiving Break

### Disproof of a packing conjecture of Alon and Spencer

Series
Combinatorics Seminar
Time
Friday, November 17, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Huseyin AcanRutgers University
A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph G_{n,1/2} typically admits a covering of a constant fraction of its edges by edge-disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for k ≪ \sqrt{n} and A_1, ..., A_t chosen uniformly and independently from the k-subsets of {1…n}, what can one say about P(|A_i ∩ A_j|≤1 ∀ i≠j)? Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently. Joint work with Jeff Kahn.

### Choices and Intervals (joint with Stochastics Seminar: note unusual date+time)

Series
Combinatorics Seminar
Time
Thursday, November 9, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Elliot PaquetteThe Ohio State University
We study an online algorithm for making a well—equidistributed random set of points in an interval, in the spirit of "power of choice" methods. Suppose finitely many distinct points are placed on an interval in any arbitrary configuration. This configuration of points subdivides the circle into a finite number of intervals. At each time step, two points are sampled uniformly from the interval. Each of these points lands within some pair of intervals formed by the previous configuration. Add the point that falls in the larger interval to the existing configuration of points, discard the other, and then repeat this process. We then study this point configuration in the sense of its largest interval, and discuss other "power of choice" type modifications. Joint work with Pascal Maillard.

### 86 Years of Ramsey R(3,k). (and counting!)

Series
Combinatorics Seminar
Time
Friday, November 3, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Joel SpencerCourant Institute, New York University
The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe, America, Korea and Rio de Janiero. We explore it through a CS lens, giving algorithms that provide the various upper and lower bounds. The arguments are various more or less sophisticated uses of Erdos Magic and, indeed, many of the most important advances in the Probabilistic Method have come from these investigations.

### Progress in showing cutoff for random walks on the symmetric group

Series
Combinatorics Seminar
Time
Friday, October 27, 2017 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Megan BernsteinGeorgia Tech
Cutoff is a remarkable property of many Markov chains in which they rapidly transition from an unmixed to a mixed distribution. Most random walks on the symmetric group, also known as card shuffles, are believed to mix with cutoff, but we are far from being able to proof this. We will survey existing cutoff results and techniques for random walks on the symmetric group, and present three recent results: cutoff for a biased transposition walk, cutoff for the random-to-random card shuffle (answering a 2001 conjecture of Diaconis), and pre-cutoff for the involution walk, generated by permutations with a binomially distributed number of two-cycles. The results use either probabilistic techniques such as strong stationary times or diagonalization through algebraic combinatorics and representation theory of the symmetric group. Includes joint work with Nayantara Bhatnagar, Evita Nestoridi, and Igor Pak.