How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
A convex chain (in particular a covering pair) of a finite poset occurs consecutively in some linear extension
Statement
Let be a finite poset (Partial order and partially ordered set) and let be a nonempty convex chain, meaning that is a chain (Chain in a poset) and that and imply . Then there is a linear extension of (Linear extensions of a finite poset) in which the elements of occur consecutively. In particular, for every covering pair of (Graded poset, rank function, and rank levels) there is a linear extension of in which and are consecutive.
Facts & Assumptions
Given: A finite poset and a nonempty convex chain .
A partial order is reflexive, antisymmetric and transitive, and its strict order is defined by if and only if and (Partial order and partially ordered set).
A subset of a poset is a chain when any two of its elements are comparable (Chain in a poset).
An element covers when and there is no with (Graded poset, rank function, and rank levels).
Every finite poset has a linear extension (Linear extensions of a finite poset: existence, prescribed initial ideals, and adjacent-swap connectivity, clause (2)).
A linear extension of a finite poset is a tuple listing every element of exactly once in which implies that occurs before (Linear extensions of a finite poset).
Proof
Given: A finite poset and a nonempty convex chain .
Proof technique: direct.
Setup. Enumerate the nonempty chain in increasing order as , and set for a new element . Let be the relation on consisting of the pairs with and , the pairs with and for some , and the pairs with and for some . Let be the reflexive transitive closure of , so is reflexive and transitive by construction.
The relation is antisymmetric. A cycle of whose vertices lie in would produce in the poset , impossible by transitivity and antisymmetry; so every nontrivial cycle passes through , and between two consecutive occurrences of it consists of an edge , a path inside from to an element , and an edge . By the definition of there are then with and , and the path inside gives ; hence . Since and is convex, this forces , contradicting . Therefore has no nontrivial cycles, and is a partial order on the finite set .
By [F4] the finite poset has a linear extension ; let be the tuple obtained from by replacing the one occurrence of with the block . Then lists every element of exactly once. It is a linear extension of : if with then , so precedes in ; if and then , so precedes in and hence precedes the whole block; if with then , so the whole block precedes ; and the block itself lists in increasing order, so it respects the relations inside . Since exhausts the block, its elements occur consecutively in .
In particular, let be a covering pair and put . Then is a nonempty chain, and it is convex: if with , then either , or , or , which is excluded by [F3]; in all cases . So step 3.1 applies and yields a linear extension of in which and are consecutive.
Depends on
Used by
Dependency tree · two levels
7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- J. R. Stembridge, On the Fully Commutative Elements of Coxeter Groups, author manuscript (March 1995, minor revisions September 1995); published in J. Algebraic Combin. 5 (1996), 353-385 (standard reference, not scraped)
- P. Nadeau, On the length of fully commutative elements, arXiv:1511.08788 (standard reference, not scraped)
- C. Krattenthaler, The theory of heaps and the Cartier-Foata monoid, appendix to the electronic reedition of P. Cartier and D. Foata, Problemes combinatoires de commutation et rearrangements (2006) (standard reference, not scraped)