Facets of the cone up to rank 7

Margaret M. Bayer^{∗} and Gábor Hetyei^{†} Department of Mathematics University of Kansas Lawrence KS 66045-2142

April 28, 2000

This note is available on the Worldwide Web at the address

              http://www.math.ku.edu/~bayer/euler/index.html

and it provides supplemental information to our paper “Flag vectors of Eulerian partially ordered sets”, to appear in the European Journal of Combinatorics.

1 Description of notation

Convolution of chain operators: f_{S}^{m}f_{T}^{n} =^{def} f_{S∪{m}∪(T +m)}^{m+n}.

See Appendix B of our paper.

Sparse f basis: A set S ⊆ {1, 2, …, n} is sparse if it does not contain two consecutive integers, and it does not contain n. For the vector space of chain operators ⟨f_{S}^{n+1} : S ⊆ {1, 2, …, n}⟩ acting on Eulerian posets of rank n + 1, the set {f_{S}^{n+1} : S ⊆ {1, 2, …, n}, S sparse} forms a basis. This was shown in: M. M. Bayer and L. J. Billera, Generalized Dehn–Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Invent. Math. 79 (1985), 143–157.

L-vector: L_{S}^{n+1} =^{def} (−1)^{n−|S|} ∑_{T ⊇[1,n]\S} (−\frac{1}{2})^{|T |} f_{T}^{n+1}. Equivalently f_{S}^{n+1} = 2^{|S|} ∑_{T ⊆[1,n]\S} L_{T}^{n+1}.

See Definition 2 of our paper.

∗This research was supported by University of Kansas General Research allocation #3552.

†On leave from the Alfréd Rényi Institute. Partially supported by Hungarian National Foundation for Scientific Research grant no. F 032325.

The cones: C_{E}^{n+1} is the smallest closed convex cone containing the flag vectors of all Eulerian posets. C_{D}^{n+1} is the smallest closed convex cone containing the flag vectors of the horizontal doubles of all half-Eulerian posets. (See Section 2 of our paper.)

2 From PORTA output to Eulerian cone

Let V be a set of vectors contained in the cone of half-Eulerian flag f-vectors, and let cone(V) be the smallest convex cone containing V. Consider the affine transformation ϕ that multiplies each f_{S}-entry of a vector by 2^{|S|}, and divides the coefficient of f_{S} in an inequality by 2^{|S|}. Let K^{n+1} be the image of cone(V) under ϕ. Then K^{n+1} is contained in the closed cone C_{D}^{n+1} of flag f-vectors of horizontal doubles of half-Eulerian posets, which is contained in the Eulerian cone C_{E}^{n+1}.

For each rank n+1 ≤ 7 we created a finite set V in the cone of half-Eulerian flag f-vectors, and used PORTA to generate cone(V). In this note we list the facet inequalities for the corresponding cone K^{n+1} (n ≤ 6). We check that these inequalities are valid for all Eulerian posets (not just for doubled half-Eulerian posets), and this tells us that C_{E}^{n+1} ⊆ K^{n+1} for rank at most 7. Thus K^{n+1} = C_{D}^{n+1} = C_{E}^{n+1}, so we have in fact determined the closed cone of Eulerian flag f-vectors for rank n + 1 ≤ 7.

3 Inequalities in the sparse f basis

The inequalities listed are equivalent up to a constant factor to the inequalities encoded in the corresponding PORTA output files. The second number in brackets corresponds to the number of the equivalent inequality in the L-basis. Boldfaced inequalities cannot be written as convolutions of lowerrank inequalities.

Rank 1:

(F 1) f_{∅}^{1} ≥ 0 (L1)

Rank 2:

(F 1) f_{∅}^{2} ≥ 0 (L1)
(F1) is equivalent to \frac{1}{2}f_{1}^{2} = \frac{1}{2}f_{∅}^{1}f_{∅}^{1} ≥ 0.

Rank 3:

\begin{matrix}(F 1) & f_{∅}^{3} ≥ 0 & (L2) \\ (F 2) & −2f_{∅}^{3} + f_{1}^{3} ≥ 0 & (L1) \end{matrix}

Rank 4:

\begin{matrix}(F 1) & f_{∅}^{4} ≥ 0 & (L3) \\ (F 2) & −f_{1}^{4} + f_{2}^{4} ≥ 0 & (L2) \\ (F 3) & −2f_{∅}^{4} + f_{1}^{4} ≥ 0 & (L1) \end{matrix}

Equivalent forms of reducible or non-evident inequalities: (F 2) : \frac{1}{2}(f_{12}^{4} − 2f_{1}^{4}) = \frac{1}{2}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3}) ≥ 0. (F 3) : f_{2}^{4} − f_{3}^{4} = \frac{1}{2}(f_{13}^{4} − 2f_{3}^{4}) = \frac{1}{2}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1} ≥ 0.

Rank 5:

\begin{matrix}(F 1) & f_{∅}^{5} ≥ 0 & (L6) \\ (F 2) & −2f_{3}^{5} + f_{13}^{5} ≥ 0 & (L3) \\ (F 3) & −2f_{2}^{5} + f_{13}^{5} ≥ 0 & (L1) \\ (F 4) & −f_{1}^{5} + f_{2}^{5} ≥ 0 & (L2) \\ (F 5) & −2f_{∅}^{5} + f_{1}^{5} ≥ 0 & (L5) \\ (F 6) & −2f_{∅}^{5} + f_{1}^{5} − f_{2}^{5} + f_{3}^{5} ≥ 0 & (L4) \end{matrix}

Equivalent forms of reducible or non-evident inequalities: (F 2) : (f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{2} = \frac{1}{2}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1}f_{∅}^{1} ≥ 0. (F 3) : \frac{1}{2}(f_{123}^{5} − 4f_{2}^{5}) = \frac{1}{2}(f_{123}^{5} − 2f_{12}^{5}) = \frac{1}{2}f_{∅}^{1}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3}) ≥ 0. (F 4) : \frac{1}{2}(f_{12}^{5} − 2f_{1}^{5}) = \frac{1}{2}f_{∅}^{1}(f_{1}^{4} − 2f_{∅}^{4}) = \frac{1}{4}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1} ≥ 0. (F 6) : f_{4}^{5} − 2f_{∅}^{5} ≥ 0.

Rank 6:

\begin{matrix}(F 1) & f_{∅}^{6} ≥ 0 & (L10) \\ (F 2) & −f_{14}^{6} + f_{24}^{6} ≥ 0 & (L2) \\ (F 3) & −2f_{3}^{6} + f_{13}^{6} ≥ 0 & (L6) \\ (F 4) & −2f_{2}^{6} + f_{13}^{6} ≥ 0 & (L1) \\ (F 5) & −f_{1}^{6} + f_{2}^{6} ≥ 0 & (L5) \\ (F 6) & −2f_{∅}^{6} + f_{1}^{6} ≥ 0 & (L8) \\ (F 7) & 2f_{3}^{6} − f_{13}^{6} − 2f_{4}^{6} + f_{14}^{6} ≥ 0 & (L9) \\ (F 8) & −2f_{3}^{6} + 2f_{4}^{6} − f_{14}^{6} + f_{24}^{6} ≥ 0 & (L3) \\ (F 9) & −f_{1}^{6} + f_{2}^{6} − f_{3}^{6} + f_{4}^{6} ≥ 0 & (L7) \\ (F 10) & −2f_{∅}^{6} + f_{1}^{6} − f_{2}^{6} + f_{3}^{6} ≥ 0 & (L4) \end{matrix}

Equivalent forms of reducible or non-evident inequalities: (F 2) : (f_{1}^{4} − f_{2}^{4})f_{∅}^{2} = \frac{1}{4}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1}f_{∅}^{1} ≥ 0. (F 3) : (f_{1}^{3} − f_{∅}^{3})f_{∅}^{3} ≥ 0. (F 4) : \frac{1}{2}(−2f_{12}^{6} + f_{123}^{6}) = \frac{1}{2}f_{∅}^{1}f_{∅}^{1}(2f_{∅}^{4} − f_{1}^{4}) = \frac{1}{4}f_{∅}^{1}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1} ≥ 0. (F 5) : \frac{1}{2}(f_{12}^{6} − 2f_{1}^{6}) = \frac{1}{2}f_{∅}^{1}(f_{1}^{5} − 2f_{∅}^{5}).

(F 7) : 2f_{3}^{6} − f_{23}^{6} + f_{24}^{6} − f_{34}^{6} = \frac{1}{2}(4f_{3}^{6} − 2f_{23}^{6} + f_{234}^{6} − 2f_{34}^{6}) = \frac{1}{2}(f_{2}^{3} − 2f_{∅}^{3})(f_{1}^{3} − 2f_{∅}^{3})

= \frac{1}{2}(f_{1}^{3} − 2f_{∅}^{3})(f_{1}^{3} − 2f_{∅}^{3}) ≥ 0. (F 8) : f_{34}^{6} − 2f_{3}^{6} = f_{∅}^{3}(f_{1}^{3} − 2f_{∅}^{3}) ≥ 0. (F 9) : f_{5}^{6} − 2f_{∅}^{6} ≥ 0. (F 10) : f_{4}^{6} − f_{5}^{6} = \frac{1}{2}(f_{45}^{6} − 2f_{5}^{6}) = \frac{1}{2}(f_{4}^{5} − 2f_{∅}^{5})f_{∅}^{1} ≥ 0.

Rank 7:

\begin{matrix}(F 1) & f_{∅}^{7} ≥ 0 & (L23) \\ (F 2) & −2f_{25}^{7} + f_{135}^{7} ≥ 0 & (L1) \\ (F 3) & −f_{14}^{7} + f_{24}^{7} ≥ 0 & (L5) \\ (F 4) & −2f_{3}^{7} + f_{13}^{7} ≥ 0 & (L10) \\ (F 5) & −2f_{2}^{7} + f_{13}^{7} ≥ 0 & (L3) \\ (F 6) & −f_{1}^{7} + f_{2}^{7} ≥ 0 & (L9) \\ (F 7) & −2f_{∅}^{7} + f_{1}^{7} ≥ 0 & (L13) \\ (F 8) & −2f_{∅}^{7} + f_{3}^{7} ≥ 0 & (L15) \\ (F 9) & −2f_{∅}^{7} + f_{4}^{7} ≥ 0 & (L14) \\ (F 10) & 2f_{3}^{7} − f_{13}^{7} − 2f_{4}^{7} + f_{14}^{7} ≥ 0 & (L16) \\ (F 11) & 4f_{4}^{7} − 2f_{14}^{7} − 2f_{35}^{7} + f_{135}^{7} ≥ 0 & (L17) \\ (F 12) & f_{14}^{7} − f_{24}^{7} − f_{15}^{7} + f_{25}^{7} ≥ 0 & (L18) \\ (F 13) & −2f_{5}^{7} + f_{15}^{7} − f_{25}^{7} + f_{35}^{7} ≥ 0 & (L4) \\ (F 14) & −2f_{4}^{7} + f_{15}^{7} − f_{25}^{7} + f_{35}^{7} ≥ 0 & (L7) \\ (F 15) & −2f_{3}^{7} + 2f_{4}^{7} − f_{14}^{7} + f_{24}^{7} ≥ 0 & (L2) \\ (F 16) & −2f_{2}^{7} + 2f_{3}^{7} − 2f_{5}^{7} + f_{25}^{7} ≥ 0 & (L22) \\ (F 17) & −2f_{2}^{7} + f_{13}^{7} − f_{14}^{7} + f_{15}^{7} ≥ 0 & (L6) \\ (F 18) & −2f_{2}^{7} + 2f_{4}^{7} − 2f_{5}^{7} + f_{25}^{7} ≥ 0 & (L21) \\ (F 19) & −f_{1}^{7} + f_{2}^{7} − f_{3}^{7} + f_{4}^{7} ≥ 0 & (L8) \\ (F 20) & −2f_{3}^{7} + f_{13}^{7} + 2f_{4}^{7} − f_{14}^{7} − 2f_{5}^{7} + f_{15}^{7} ≥ 0 & (L11) \\ (F 21) & −2f_{1}^{7} + f_{13}^{7} + 2f_{4}^{7} − f_{14}^{7} − 2f_{5}^{7} + f_{15}^{7} ≥ 0 & (L20) \\ (F 22) & −2f_{∅}^{7} + f_{1}^{7} − f_{2}^{7} + f_{3}^{7} − f_{4}^{7} + f_{5}^{7} ≥ 0 & (L12) \\ (F 23) & −2f_{1}^{7} − 2f_{3}^{7} + f_{13}^{7} + 4f_{4}^{7} − f_{14}^{7} − 2f_{5}^{7} + f_{15}^{7} ≤ 0 & (L19) \end{matrix}

Equivalent forms of reducible or non-evident inequalities: (F 2) : (−2f_{2}^{5} + f_{13}^{5})f_{∅}^{2} = \frac{1}{4}f_{∅}^{1}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1}f_{∅}^{1} ≥ 0. (F 3) : (f_{2}^{4} − f_{1}^{4})f_{∅}^{3} = \frac{1}{2}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{3} ≥ 0. (F 4) : (f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{4} ≥ 0. (F 5) : \frac{1}{2}(−2f_{12}^{7} + f_{123}^{7}) = \frac{1}{2}f_{∅}^{1}f_{∅}^{1}(f_{1}^{5} − 2f_{∅}^{5}) ≥ 0. (F 6) \frac{1}{2}(−2f_{1}^{7} + f_{12}^{7}) = \frac{1}{2}f_{∅}^{1}(f_{1}^{6} − 2f_{∅}^{6}) ≥ 0. (F 10) : 2f_{3}^{7} − f_{23}^{7} + f_{24}^{7} − f_{34}^{7} = \frac{1}{2}(4f_{3}^{7} − 2f_{23}^{7} + f_{234}^{7} − 2f_{34}^{7}) = \frac{1}{2}(f_{1}^{3} − 2f_{∅}^{3})(f_{1}^{4} − 2f_{∅}^{4})

= \frac{1}{4}(f_{1}^{3} − 2f_{∅}^{3})(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1} ≥ 0. (F 11) : −2f_{24}^{7}+2f_{34}^{7}−2f_{35}^{7}+f_{135}^{7} = \frac{1}{2}(−2f_{134}^{7}+4f_{34}^{7}−2f_{345}^{7}+f_{1345}^{7}) = \frac{1}{2}(f_{1}^{3}−2f_{∅}^{3})f_{∅}^{1}(f_{1}^{3}−2f_{∅}^{3}) ≥ 0. (F 12) : 2f_{4}^{7} − f_{34}^{7} + f_{35}^{7} − f_{45}^{7} = \frac{1}{2}(4f_{4}^{7} − 2f_{34}^{7} + f_{345}^{7} − 2f_{45}^{7}) = \frac{1}{2}(f_{3}^{4} − 2f_{∅}^{4})(f_{1}^{3} − 2f_{∅}^{3})

= \frac{1}{2}(f_{2}^{4} − f_{1}^{4})(f_{1}^{3} − 2f_{∅}^{3}) = \frac{1}{4}f_{∅}^{1}(f_{2}^{3} − 2f_{∅}^{3})(f_{1}^{3} − 2f_{∅}^{3}) = \frac{1}{4}f_{∅}^{1}(f_{1}^{3} − 2f_{∅}^{3})(f_{1}^{3} − 2f_{∅}^{3}) ≥ 0. (F 13) : f_{45}^{7} − 2f_{5}^{7} = \frac{1}{2}(f_{4}^{5} − 2f_{∅}^{5})f_{∅}^{1}f_{∅}^{1} ≥ 0. (F 14) : f_{45}^{7} − 2f_{4}^{7} = f_{∅}^{4}(f_{1}^{3} − 2f_{∅}^{3}) ≥ 0. (F 15) : f_{34}^{7} − 2f_{3}^{7} = f_{∅}^{3}(f_{1}^{4} − 2f_{∅}^{4}) = \frac{1}{2}f_{∅}^{3}(f_{1}^{3} − 2f_{∅}^{3})f_{∅}^{1} ≥ 0. (F 17) : f_{16}^{7} − 2f_{1}^{7} = f_{∅}^{1}(f_{5}^{6} − 2f_{∅}^{6}) ≥ 0. (F 19) : f_{5}^{7} − f_{6}^{7} = \frac{1}{2}(f_{56}^{7} − 2f_{6}^{7}) = \frac{1}{2}(f_{5}^{6} − 2f_{∅}^{6})f_{∅}^{1} ≥ 0. (F 20) : f_{16}^{7} − 2f_{6}^{7} = (f_{1}^{6} − 2f_{∅}^{6})f_{∅}^{1} ≥ 0. (F 21) : f_{16}^{7} − 2f_{1}^{7} − 2f_{6}^{7} + 2f_{3}^{7} ≥ 0. (F 22) : f_{6}^{7} − 2f_{∅}^{7} ≥ 0. (F 23) : f_{16}^{7} − 2f_{1}^{7} − 2f_{6}^{7} + 2f_{4}^{7} ≥ 0.

4 Inequalities in the L-basis

Note: Since f_{S}^{n+1} = 2^{|S|} ∑_{T ⊆[1,n]\S} L_{T}^{n+1}, and here we need to consider only the nonzero L_{T}^{n+1}’s, it is

easy to convert an f-formula into an L-formula. The other way may be more difficult. The labels (F i) refer to the numbering in the sparse f basis which is given in section 3. Boldfaced inequalities cannot be written as convolutions of lower-rank inequalities.

Rank 1:

(L1) −L_{∅}^{1} ≤ 0 (F 1)

Rank 2:

(L1) −L_{∅}^{2} ≤ 0 (F 1)

Rank 3:

\begin{matrix}(L1) & L_{12}^{3} ≤ 0 & (F 2) \\ (L2) & −L_{∅}^{3} − L_{12}^{3} ≤ 0 & (F 1) \end{matrix}

Rank 4:

\begin{matrix}(L1) & L_{12}^{4} = L_{12}^{3}L_{∅}^{1} ≤ 0 & (F 3) \\ (L2) & L_{23}^{4} = L_{∅}^{1}L_{12}^{3} ≤ 0 & (F 2) \\ (L3) & −L_{∅}^{4} − L_{12}^{4} − L_{23}^{4} ≤ 0 & (F 1) \end{matrix}

Rank 5:

\begin{matrix}(L1) & L_{34}^{5} ≤ 0 & (F 3) \\ (L2) & L_{23}^{5} ≤ 0 & (F 4) \\ (L3) & L_{12}^{5} ≤ 0 & (F 2) \\ (L4) & L_{34}^{5} + L_{1234}^{5} ≤ 0 & (F 6) \\ (L5) & L_{12}^{5} + L_{1234}^{5} ≤ 0 & (F 5) \\ (L6) & −L_{∅}^{5} − L_{12}^{5} − L_{23}^{5} − L_{34}^{5} − L_{1234}^{5} ≤ 0 & (F 1) \end{matrix}

Rank 6:

\begin{matrix}(L1) & L_{34}^{6} ≤ 0 & (F 4) \\ (L2) & L_{23}^{6} ≤ 0 & (F 2) \\ (L3) & L_{45}^{6} + L_{1245}^{6} ≤ 0 & (F 8) \\ (L4) & L_{34}^{6} + L_{1234}^{6} ≤ 0 & (F 10) \\ (L5) & L_{23}^{6} + L_{2345}^{6} ≤ 0 & (F 5) \\ (L6) & L_{12}^{6} + L_{1245}^{6} ≤ 0 & (F 3) \\ (L7) & L_{45}^{6} + L_{1245}^{6} + L_{2345}^{6} ≤ 0 & (F 9) \\ (L8) & L_{12}^{6} + L_{1234}^{6} + L_{1245}^{6} ≤ 0 & (F 6) \\ (L9) & −L_{1245}^{6} ≤ 0 & (F 7) \\ (L10) & −L_{∅}^{6} − L_{12}^{6} − L_{23}^{6} − L_{34}^{6} − L_{1234}^{6} − L_{45}^{6} − L_{1245}^{6} − L_{2345}^{6} ≤ 0 & (F 10) \end{matrix}

Rank 7: \begin{aligned}(L1) & L_{34}^{7} ≤ 0 & (F 2) \\ (L2) & L_{45}^{7} + L_{1245}^{7} ≤ 0 & (F 15) \\ (L3) & L_{34}^{7} + L_{3456}^{7} ≤ 0 & (F 5) \\ (L4) & L_{34}^{7} + L_{1234}^{7} ≤ 0 & (F 13) \\ (L5) & L_{23}^{7} + L_{2356}^{7} ≤ 0 & (F 3) \\ (L6) & L_{56}^{7} + L_{2356}^{7} + L_{3456}^{7} ≤ 0 & (F 17) \\ (L7) & L_{56}^{7} + L_{1256}^{7} + L_{2356}^{7} ≤ 0 & (F 14) \\ (L8) & L_{45}^{7} + L_{1245}^{7} + L_{2345}^{7} ≤ 0 & (F 19) \\ (L9) & L_{23}^{7} + L_{2345}^{7} + L_{2356}^{7} ≤ 0 & (F 6) \\ (L10) & L_{12}^{7} + L_{1245}^{7} + L_{1256}^{7} ≤ 0 & (F 4) \\ (L11) & L_{12}^{7} + L_{1234}^{7} + L_{1245}^{7} ≤ 0 & (F 20) \\ (L12) & L_{56}^{7} + L_{1256}^{7} + L_{2356}^{7} + L_{3456}^{7} + L_{123456}^{7} ≤ 0 & (F 22) \\ (L13) & L_{12}^{7} + L_{1234}^{7} + L_{1245}^{7} + L_{1256}^{7} + L_{123456}^{7} ≤ 0 & (F 7) \\ (L14) & L_{34}^{7} + L_{1234}^{7} + L_{45}^{7} + L_{1245}^{7} + L_{2345}^{7} + L_{3456}^{7} + L_{123456}^{7} ≤ 0 & (F 9) \\ (L15) & L_{23}^{7} + L_{34}^{7} + L_{1234}^{7} + L_{2345}^{7} + L_{2356}^{7} + L_{3456}^{7} + L_{123456}^{7} ≤ 0 & (F 8) \\ (L16) & −L_{1245}^{7} ≤ 0 & (F 10) \\ (L17) & −L_{1256}^{7} ≤ 0 & (F 11) \\ (L18) & −L_{2356}^{7} ≤ 0 & (F 12) \\ (L19) & L_{34}^{7} + L_{1234}^{7} + L_{45}^{7} + L_{1245}^{7} + L_{2345}^{7} − L_{1256}^{7} + L_{3456}^{7} ≤ 0 & (F 23) \\ (L20) & L_{23}^{7} + L_{34}^{7} + L_{1234}^{7} + L_{2345}^{7} − L_{1256}^{7} + L_{2356}^{7} + L_{3456}^{7} ≤ 0 & (F 21) \\ (L21) & L_{34}^{7} + L_{1234}^{7} + L_{45}^{7} − L_{1256}^{7} − L_{2356}^{7} + L_{3456}^{7} ≤ 0 & (F 18) \\ (L22) & L_{23}^{7} + L_{34}^{7} + L_{1234}^{7} − L_{1245}^{7} − L_{1256}^{7} + L_{3456}^{7} ≤ 0 & (F 16) \\ (L23) & −L_{∅}^{7} − L_{12}^{7} − L_{23}^{7} − L_{34}^{7} − L_{1234}^{7} − L_{45}^{7} & (F 1) \\ & −L_{1245}^{7} − L_{2345}^{7} − L_{56}^{7} − L_{1256}^{7} − L_{2356}^{7} − L_{3456}^{7} − L_{123456}^{7} ≤ 0 \end{aligned}

7