Let $LC_n$ be the length of the longest common subsequences of two independent random words whose letters are taken
in a finite alphabet and when the alphabet is totally ordered, let $LCI_n$ be the length of the longest common and increasing subsequences of the words. Results on the asymptotic means, variances and limiting laws of these well known random objects will be described and compared.
The permutation removal lemma was first proved by Klimosová and Král’, and later reproved by Fox and Wei in the context of permutation property testing. In this talk, we study a local version of the permutation removal problem. We show that for any permutation σ not equal to 12, 21, 132, 231, 213, or 312, there exists ε(σ) > 0 such that for any sufficiently large integer N, there is a permutation π of length N that is ε-far from being σ-free with respect to the ρ∞ distance, yet contains only a single copy of σ. Here, the ρ∞ distance is defined as an L∞-variant of the Earth Mover’s Distance between two permutations. We will also discuss our result on the local induced graph removal problem. This is joint work with Fan Wei.
A geometric graph consists of a set of points in the plane together with line
segments between some pairs of points. A convex geometric graph is a geometric graph whose
points are in convex position. We present some old and new extremal results and applications,
and their extension to geometric hypergraphs, together with a variety of open problems.
Partly joint work with Zoltan Furedi, Tao Jiang, Sasha Kostochka and Dhruv Mubayi
I’ll describe some recent work (joint with Jeff Kahn and Jinyoung Park) on the "Second" Kahn--Kalai Conjecture (KKC2), the original conjecture on graph containment in $G_{n,p}$ that motivated what is now the Park--Pham Theorem (PPT). KKC2 says that $p_c(H)$, the threshold for containing a graph $H$ in $G_{n,p}$, satisfies $p_c(H) < O(p_E(H) log n)$, where $p_E(H)$ is the smallest p such that the expected number of copies of any subgraph of $H$ is at least one. Thus, according to KKC2, the simplest expectation considerations predict $p_c(H)$ up to a log factor. This serves as a refinement of PPT in the restricted case of graph containment in $G_{n,p}$. Our main result is that $p_c(H) < O(p_E(H) log^3(n))$. This last statement follows (via PPT) from our results on a completely deterministic graph theory problem about maximizing subgraph counts under sparsity constraints.
Given a feasible degree sequence D, we consider the uniform distribution over all graphs with degree sequence D. In 1995, Molloy and Reed gave a criterion for determining the existence of a giant (i.e. linear in n) component for degree sequences satisfying certain technical conditions; in 2018, Joos, Perarnau, Rautenbach, and Reed gave a refined result that applies to essentially all feasible D. In this talk, we work in the "supercritical" regime and uncover the precise structure of the giant component when it exists, obtaining bounds on the diameter and mixing time of the random walk on the giant which are tight up to polylogarithmic factors. Our techniques involve a variation of core-kernel reduction and analysis of the switch Markov chain. Joint work with Louigi Addario-Berry and Bruce Reed.
The regularity method for graphs has been well studied for dense graphs, i.e., graphs on $n$ vertices with $\Omega(n^2)$ edges. However, applying it to sparse graphs, i.e., those with $o(n^2)$ edges seems to be a harder problem. In the mid 2010s, the regularity method was extended to dense subgraphs of random graphs thus resolving the KŁR conjecture. Later, in another direction, Conlon, Fox, Sudakov and Zhao proved a removal lemma for $C_5$ in graphs that do not contain any $C_4$ (such graphs on $n$ vertices can contain at most $n^{3/2}$ edges). In this talk, we will consider a similar problem for sparse $3$-uniform hypergraphs. In particular, we consider an application of the regularity method to $3$-uniform hypergraphs whose vertices do not contain $C_4$ in their links and satisfy an additional boundedness condition. This is joint work with Vojtěch Rödl and Mathias Schacht.
The rank-$n$ Dowling geometry $Q_n(\Gamma)$ is a matroid associated with a graph edge-labeled by elements of the finite group $\Gamma$. We determine the maximum size of an $N$-free submatroid of $Q_n(\Gamma)$ for various choices of $N$, including subgeometries $Q_m(\Gamma')$, lines $U_{2,\ell}$, and graphic matroids $M(H)$. When the group $\Gamma$ is trivial and $N=M(K_t)$, this problem reduces to Tur\'{a}n's classical result in extremal graph theory. We show that when $\Gamma$ is nontrivial, a complex dependence on $\Gamma$ emerges, even when $N=M(K_4)$.
This is joint work with Rutger Campbell and Jorn van der Pol.
Three fifteen-minute talks by local speakers.
Logan Post: Almost all even-parity binary words are shuffle squares
Jasper Seabold: Using Grid Graphs to Study Hypergraph Ramsey Questions
Adri Wessels:
Using the theory of total linear stability for Dynkin quivers and an interplay between the Bruhat order and the noncrossing partition lattice, we define a family of triangulations of the permutohedron indexed by Coxeter elements. Each triangulation is constructed to give an explicit homotopy between two complexes (the Salvetti complex and the Bessis--Brady--Watt complex) associated to two different presentations of the corresponding braid group (the standard Artin presentation and Bessis's dual presentation). Our triangulations have several notable combinatorial properties. In addition, they refine similar Bruhat interval polytope decompositions of Knutson, Sanchez, and Sherman-Bennett. This is based on joint work with Melissa Sherman-Bennett and Nathan Williams.
