Videos

Introductory Workshop - Graph Theory: Extremal, Probabilistic and Structural: Forbidden acyclic patterns in 0-1 matrices

Presenter
February 10, 2025
Keywords:
  • extremal graph theory
  • random graphs
  • probabilistic methods
  • structural graph theory
  • Ramsey theory
MSC:
  • 05C35 - Extremal problems in graph theory [See also 90C35]
  • 05C55 - Generalized Ramsey theory [See also 05D10]
  • 05C75 - Structural characterization of families of graphs
  • 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
  • 05D40 - Probabilistic methods in extremal combinatorics
  • including polynomial methods (combinatorial Nullstellensatz
  • etc.)
Abstract
A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal function of A, denoted ex(n, A), is the maximum number of 1-entries that an n×n zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Füredi and Hajnal from 1992. The field has many connections to other areas such as classical Turán type extremal graph theory and Davenport-Schinzel theory and has many applications in mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices and this talk is a survey of these results. After several refuted conjectures the one still standing (and wide open) states that the extremal function of any acyclic pattern is $n^{1+o(1)}$.