Обобщение теоремы Дилворта для помеченных DAG

Антицепь в DAG представляет собой подмножество ⊆ V вершин, попарно недостижим, а именно, нет v ≠ v ' ∈ таким образом, что v достижима из V ' в Е . Из теоремы Дилворта в теории частичного порядка известно, что если DAG не имеет антицепи размера k ∈ N , то она может быть разложена в объединение не более чем k - 1 непересекающихся цепочек, т. Е. Направленных путей.$(V, E)$$A \subseteq V$$v \neq v' \in A$$v$$v'$$E$$k \in \mathbb{N}$$k-1$

$v$$\lambda(v)$$\Sigma$$A \subseteq V$$\Sigma$$A$$\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$ $k \in \mathbb{N}$Что я могу предположить о его структуре? Могу ли я разложить его каким-то особым образом? Я уже озадачен случаем , но также заинтересован в случае общего конечного множества меток.$\Sigma = \{a, b\}$

Чтобы визуализировать это для , сказать, что не имеет антицепи с помеченным размером означает, что нет антицепи, содержащей по крайней мере вершин, помеченных и вершин, помеченных ; может быть сколь угодно большим антицепи , но они должны содержать только элементы или только элементов, вплоть до исключений в большинстве. Кажется, что запрещение больших антицепей должно обеспечить, что DAG по существу «чередуется» между частями большой ширины для вершин меткой и большой шириной для$\Sigma = \{a, b\}$$G$$k$$k$$a$$k$$b$$a$$b$$k-1$$a$$b$вершины, но я не смог формализовать эту интуицию. (Конечно, подходящая структурная характеристика должна говорить о метках вершин в дополнение к форме DAG, потому что уже для и на условие удовлетворяется совершенно произвольными DAG, когда все вершины имеют одинаковую метку.)$k \geq 1$$\{a, b\}$

С Чарльзом Паперменом мы смогли получить такой результат для ГПДР, помеченных алфавитом . По сути, мы можем показать, что с учетом DAG который имеет большие антицепи из меченых элементов, большие антицепи из меченых элементов, но нет больших антицепей, содержащих как много элементов с меченым, так и меченым, то происходит разложение как раздел , где:$\{a, b\}$$G$$a$$b$$a$$b$$G$$L_1, \ldots, L_n$

• раздел - это то, что мы называем «наслоением», то есть: $L_1, ..., L_n$
  • каждый является выпуклым множеством, т. е. если и то$L_i$$x, y \in L_i$$x \leq z \leq y$$z \in L_i$
  • для всех нет и таких что$i < j$$x \in L_i$$y \in L_j$$y \leq x$
• для любой антицепи группы существует такое , что «почти содержится» в , т. е.меньше константы$A$$G$$i$$A$$L_i$$|A \setminus L_i|$
• для каждого верно одно из следующего: $L_i$
  • $L_i$ содержит большое антицепь меченные элементы и не содержит большую антицепи меченных элементов$a$$b$
  • $L_i$ содержит большую антицепь из меченых элементов, но не содержит большую антицепь из меченых элементов$b$$a$

Кроме того, такой раздел может быть вычислен в PTIME.

Я разместил наше текущее доказательство онлайн . Это очень грубо и, по сути, не корректируется, потому что мы пока не используем результат, но я все же подумал, что было бы уместнее добавить ответ на этот вопрос теории CS с нашим текущим прогрессом. Не стесняйтесь связаться со мной, если вы заинтересованы в результате, но не можете понять доказательства.