Connections Workshop: Extremal Combinatorics: De-clawing graph theory
Presenter
February 7, 2025
Keywords:
- extremal combinatorics
- extremal set theory
- extremal graph theory
- hypergraphs
- designs
- Ramsey theory
- positional games
- random graphs
- thresholds
- probabilistic combinatorics
- combinatorial probability
- statistical physics
- percolation
- structural graph theory
- graph minors
- chromatic number
- arithmetic combinatorics
- arithmetic progressions
- discrete geometry
- combinatorial geometry
- incidence theorems
MSC:
- 05B05 - Combinatorial aspects of block designs [See also 51E05
- 62K10]
- 05B07 - Triple systems
- 05C15 - Coloring of graphs and hypergraphs
- 05C20 - Directed graphs (digraphs)
- tournaments
- 05C22 - Signed and weighted graphs
- 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.)
- 05C51 - Graph designs and isomorphic decomposition [See also 05B30]
- 05C55 - Generalized Ramsey theory [See also 05D10]
- 05C57 - Games on graphs (graph-theoretic aspects) [See also 91A43
- 91A46]
- 05C65 - Hypergraphs
- 05C78 - Graph labelling (graceful graphs
- bandwidth
- 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
- 05C83 - Graph minors
- 05D05 - Extremal set theory
- 05D40 - Probabilistic methods in extremal combinatorics
- including polynomial methods (combinatorial Nullstellensatz
- 11B13 - Additive bases
- including sumsets [See also 05B10]
- 11B25 - Arithmetic progressions [See also 11N13]
- 11B30 - Arithmetic combinatorics
- higher degree uniformity
- 11P70 - Inverse problems of additive number theory
- including sumsets
- 52C10 - Erdős problems and related topics of discrete geometry [See also 11Hxx]
- 52C30 - Planar arrangements of lines and pseudolines (aspects of discrete geometry)
- 52C35 - Arrangements of points
- flats
- hyperplanes (aspects of discrete geometry) [See also 14N20
- 32S22]
- 60C05 - Combinatorial probability
Abstract
This talk requires no prior knowledge and will be suitable for a broad audience. We will meet the chromatic symmetric function, dating from 1995, which is a generalization of the chromatic polynomial. We will also hear about a famed problem regarding it, called the Stanley-Stembridge (3+1)-free problem. This has been the focus of much research lately including resolving another problem of Stanley of whether the (3+1)-free problem can be widened. The resulting paper on the latter problem was recently awarded the 2023 MAA David P. Robbins Prize, and we will hear this story too.