solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看10970次
A New Characterization of $\mathcal{V}$-Posets. (arXiv:1810.07276v1 [math.CO])
来源于:arXiv
Recently, Misanantenaina and Wagner characterized the set of induced $N$-free
and bowtie-free posets as a certain class of recursively defined subposets
which they term "$\mathcal{V}$-posets". Here we offer a new characterization of
$\mathcal{V}$-posets by introducing a property we refer to as \emph{autonomy}.
A poset $\mathcal{P}$ is said to be \emph{autonomous} if there exists a
directed acyclic graph $D$ (with adjacency matrix $U$) whose transitive closure
is $\mathcal{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 $\mathcal{P}$. 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 查看全文>>