A new characterization of V -posets

DOI10.1007/S11083-019-09510-6MaRDI QIDQ781541zbMATH OpenOpenAlexFDO

Authors Joshua Cooper, Peter Gartland, Hays Whitlatch

Publication date 17 July 2020

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07276

zbMATH Keywords

\(N\)-freebowtie-freegraph theoryposetpressing sequencerecognition algorithm

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: In 2016, Hasebe and Tsujie gave a recursive characterization of the set of induced $N$-free and bowtie-free posets; Misanantenaina and Wagner studied these orders further, naming them "$mathcalV$-posets". Here we offer a new characterization of $mathcalV$-posets by introducing a property we refer to as autonomy. A poset $cP$ is said to be autonomous if there exists a directed acyclic graph $D$ (with adjacency matrix $U$) whose transitive closure is $cP$, with the property that any total ordering of the vertices of $D$ so that Gaussian elimination of $U^{T}U$ proceeds without row swaps is a linear extension of $cP$. Autonomous posets arise from the theory of pressing sequences in graphs, a problem with origins in phylogenetics. The pressing sequences of a graph can be partitioned into families corresponding to posets; because of the interest in enumerating pressing sequences, we investigate when this partition has only one block, that is, when the pressing sequences are all linear extensions of a single autonomous poset. We also provide an efficient algorithm for recognition of autonomy using structural information and the forbidden subposet characterization, and we discuss a few open questions that arise in connection with these posets.

Review text

The paper defines a finite poset \(P\) to be ``autonomous if there exists a directed acyclic graph \(D\) with adjacency matrix \(U\) whose transitive closure is \(P\), with the property that any total ordering of the vertices of \(D\) so that Gaussian elimination of \(U^tU\) proceeds without row swaps is a linear extension of \(P\). The main theorem of the paper is that a finite poset is autonomous if and only if it is induced \(N\)-free and induced bowtie-free. This class of posets has a ``series-parallel type of characterization: by a theorem of \textit{T. Hasebe} and \textit{S. Tsujie} [J. Algebr. Comb. 46, No. 3--4, 499--515 (2017; Zbl 1423.06011)] the class of finite induced \(N\)-free and induced bowtie-free posets is the smallest isomorphism-closed class of posets which (i) contains the \(1\)-element poset, (ii) is closed under the formation of disjoint union, and (iii) is closed under adjoining new least or largest elements.

Recommendations

• A characterization of (3+1)-free posets
• Prime orders all of whose prime suborders are selfdual
• N-free posets as generalizations of series-parallel posets
• Independence posets
• Automorphism groups of posets with forbidden subposets

Cites work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Counting linear extensions
• Faster integer multiplication using plain vanilla FFT primes
• scientific article; zbMATH DE number 1786450 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• Order quasisymmetric functions distinguish rooted trees
• Successful pressing sequences for a bicolored graph and binary matrices
• The Recognition of Series Parallel Digraphs
• Transforming cabbage into turnip
• Uniquely pressable graphs: characterization, enumeration, and recognition

Cited in

(6)

• scientific article; zbMATH DE number 7583268 (Why is no real title available?)
• Independence posets
• Independence posets
• A characterization of (3+1)-free posets
• On the transitivity coefficients for minimal posets with nonpositive quadratic Tits form
• Complexity and enumeration in models of genome rearrangement

This page was built for publication: A new characterization of \(\mathcal{V} \)-posets

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