Graphs, flags and partitions

arXivmath/9809092MaRDI QIDQ6501018FDOQ6501018

Authors: Jonathan Fine 

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.

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Graph theory (05Cxx)

This page was built for publication: Graphs, flags and partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6501018)