solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2274次
A counterexample regarding labelled well-quasi-ordering. (arXiv:1709.10042v1 [math.CO])
来源于:arXiv
Korpelainen, Lozin, and Razgon conjectured that a hereditary property of
graphs which is well-quasi-ordered by the induced subgraph order and defined by
only finitely many minimal forbidden induced subgraphs is labelled
well-quasi-ordered, a notion stronger than that of $n$-well-quasi-order
introduced by Pouzet in the 1970s. We present a counterexample to this
conjecture. In fact, we exhibit a hereditary property of graphs which is
well-quasi-ordered by the induced subgraph order and defined by finitely many
minimal forbidden induced subgraphs yet is not $2$-well-quasi-ordered. This
counterexample is based on the widdershins spiral, which has received some
study in the area of permutation patterns. 查看全文>>