Graphs, flags and partitions

1998/09/17 by Jonathan Fine, Fine, Jonathan
Computer Science · Mathematics · #05C #52B05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C #msc:52B05

paper · pdf · doi:10.48550/arxiv.math/9809092

12 pages, LaTeX 2e, no figures

arxiv created 1998/09/17 · openalex publication_date 1998/09/17 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper defines, for each graph G, a flag vector fG. The flag vectors of the graphs on n vertices span a space whose dimension is p(n), the number of partitions on n. The analogy with convex polytopes indicates that the linear inequalities satisfied by fG may be both interesting and accessible. Such would provide inequalities both sharp and subtle on the combinatorial structure of G. These may be related to Ramsey theory.

Related

• Partitions and their lattices
• Equitable partition of graphs into induced linear forests
• Constructing subset partition graphs with strong adjacency and end-point count properties
• Calculating Ramsey numbers by partitioning coloured graphs
• The polytope of degree partitions