Algebraic and Analytic Methods in Combinatorics: Discrepancy of graphs and hypergraphs
Presenter
March 20, 2025
Keywords:
- extremal combinatorics
- extremal graph theory
- probabilistic combinatorics
- discrete geometry
- additive combinatorics
- combinatorial geometry
- incidence geometry
- arithmetic progressions
- Discrete analysis
MSC:
- 05C25 - Graphs and abstract algebra (groups rings fields
- etc.) [See also 20F65]
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C50 - Graphs and linear algebra (matrices eigenvalues etc.)
- 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
- 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
The discrepancy of a graph (or a hypergraph) measures the maximum deviation of the sizes of its induced subgraphs from their expected size. This notion is closely related to many other extensively studied functions of graphs, such as maximum cut, minimum bisection, and spectral gap. I will talk about how to attack several problems in this area with the help of linear algebraic techniques. Based on joint works with Eero Räty and Benny Sudakov.