Videos

Connections Workshop: Extremal Combinatorics: Graph profiles and their tropicalizations

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
The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs. We will first discuss graph profiles, which are objects that essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and use those results to answer some questions in extremal graph theory.