Tag - Graph regularity

David Conlon: The regularity method for graphs with few 4-cycles

12th October, 2020

We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include:

   •  Every n-vertex graph with no 5-cycle can be made triangle-free by deleting o(n3/2) edges.
   •  For r ≥ 3, every n-vertex r-graph with girth greater than 5 has o(n3/2) edges.
   •  Every subset of [n] without a non-trivial solution to the equation x1 + x2 + 2x3 = x4 + 3x5 has size o(√n).

Nati Linial: What are High-Dimensional Expanders?

2nd February, 2017

Quite a few people are trying to answer the question in the title. Various interesting approaches are being proposed based on algebraic, geometric and topological notions. In this talk I will advocate a combinatorial approach that is based on sparsity and regularity and focuses on notions of low discrepancy. This approach makes it particularly desirable to investigate random high-dimensional combinatorial objects.