Linear inequalities for flags in graded partially ordered sets (Q1971014): Difference between revisions

The paper contains the characterization of all linear inequalities holding for the flag \(f\)-vectors of all graded posets of rank \(n+1.\) Every such linear inequality may be written as \(F(P):=\sum_{S\subseteq\{1, \dots,n\}}a_S\cdot f_S^{n+1}(P)\geqslant 0,\) where the coefficients \(a_S\) are real numbers. The chain-operators \(f_S^{n+1}(P)\) generate a vector space \(A_{n+1}\) of dimension \(2^n\) over \(\mathbb R.\) The authors are interested in determining the subset \(K_{n+1}:= \{F=\sum_{S\subseteq\{1, \dots,n\}}a_S\cdot f_S^{n+1}\in A_{n+1}:\forall P\) \((F(P)) \geqslant 0\}\) of \(A_{n+1}.\) It is shown that \(K_{n+1}\) is a polyhedral cone, that is, the intersection of finitely many half spaces given in terms of interval systems on the linearly ordered set \(\{1,\dots,n\}\subseteq\mathbb N.\) The main result of the paper is the list of inequalities that determine \(K_{n+1}.\) For posets of rank \(n+1,\) these inequalities are in one-to-one correspondence with antichains of intervals in the linearly ordered set \(\{1,\dots,n\},\) and so are counted by a Catalan number. Thus while the space of flag \(f\)-vectors has dimension \(2^n,\) the cone they generate has on the order of \((2n)^n\) generators. It is proven that the convolution operation introduced by Kalai assigns extreme rays to pairs of extreme rays in most cases. The strongest possible inequalities for graded partially ordered sets of rank at most 5 are described.