Large simple cycles in dense simplicial complexes

Abstract: Simplicial complexes can be viewed as a higher dimensional generalization of graphs with a significantly richer structure than hypergraphs. For example, many graph theoretic notions such as cycles, cuts, eigenvalues, etc., have natural analogues in simplicial complexes, as opposed to hypergraphs. Moreover, in addition to Combinatorics, powerful methods from Linear Algebra, Matroid Theory, Algebraic Topology, etc., can be $-$ and are $-$ employed in their study.

In the recent decades there has been a significant progress in the study of random simplicial complexes, as well as in understanding their extremal properties. There are also some startling applications to Computer Science yet to be developed. That said, there remain many natural and seemingly simple open problems in the theory of simplicial complexes. Here we focus on one such problem, which on a closer inspection turns out to be interesting and nontrivial.

A classical theorem of Erdős and Gallai (1959), asserts that for an undirected graph $G=(V,E)$, if $|E| > 2k(|V|-1)$, then $G$ contains a cycle of length $> k$. In other words, the density of graph is a lower bound for the size of the largest cycle in it, up to a constant factor. We show that the size of the largest simple $d$-cycle in a simplicial $d$-complex is at least a square root of its density.

Based on a joint work with Roy Meshulam and Ilan Newman.

discrete mathematicscombinatorics

Audience: researchers in the discipline

( paper | slides | video )

---

LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

---