4
$\begingroup$

I am currently studying the theory behind Well-Quasi-Orders. However I am having some issues in understanding how an infinite anti-chain can be produced to disprove the claim that a partial order $P$ is a w.q.o.

In particular I am wondering whether it is logically sound to present as proof not the infinite anti-chain but rather an algorithm to produce it.

More specifically, I've been trying to solve an exercise from the following lecture which asks whether the class of $P_{3}\text{-free}$ graphs is a w.q.o or not on the induced subgraph operation $\leq_{i}$

I've proved that said class contains unions of cliques and defined an ordering of this set as follows $P=\lbrace G_{0},G_{1},G_{2},.... \rbrace$ with $G_{i}$ representing all $P_{3}\text{-free}$ graphs on $i$ vertices (and graphs in $G_{i}$ being represented in a touple-like alpharithmetic form $(a_{1},....,a_{i})$ such that $a_{1} \leq a_{2} \leq.... \leq a_{i}$ to avoid repetitions and $\sum_{j=1}^{i} a_{j}=i$ to define an order. For example $(0,0,2,2)$ $\in G_{4}$ encodes the graph with two disconnected $P_{2}$ components.

I have defined an algorithm $B$ that produces an anti-chain that grows bigger and bigger at each step

The algorithm uses gadgets defined as $B_{a,c}$ which represent the graph with $c+1$ connected components, the first $c$ of which are $K_{1}$(i.e a sole vertice) and the last component representing $K_{a}$

The steps of my algorithm are the following:

  1. Define $L$ as the sequence

  2. Add $B_{a,0}$ to $L$ ($a$ any number $>$ 0)

  3. repeat $\infty$ times:

    4.Replace each item $B_{a,c} \in L$ by $B_{a^{'}=a+1 + 10^{6},c}$ and produce $L^{'}$ this way.

    5.Let $X=B_{a^{'},c}$ be the graph with the maximum $c$ amongst those in $L^{'}$

    6.Add to $L=L^{'}$ the graph $B_{a^{'}-2,c+1}$

Certainly, this algorithm does create an anti-chain( in each step I create a graph with more connected components yet less vertices). However I am not sure that such a technique is valid for disproving w.q.o on the infinite anti-thesis claim because of the fact that it works on a step by step basis.

Any help is appreciated. Thank you very much!

$\endgroup$
1
  • 1
    $\begingroup$ I didn't check the specifics, however, if you can prove that an algorithm generates an infinite antichain, that is as good a way as any to show the existence of an infinite antichain. $\endgroup$ Sep 25, 2016 at 16:08

1 Answer 1

3
$\begingroup$

Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a single antichain of infinite size.

It is perfectly fine to specify an infinite chain by giving an algorithm that enumerates its members, and even more complicated constructions are possible (e.g. the priority method). However, the end result of the construction should be a single infinite chain rather than a sequence of antichains of unbounded size.

I suggest taking a look at Higman's lemma.

$\endgroup$
6
  • $\begingroup$ Thank you for the answer. I will look on the lemma as well but could you please elaborate more on this part: "Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a single antichain of infinite size." $\endgroup$
    – jjohn
    Sep 25, 2016 at 16:51
  • $\begingroup$ As far as I understand your algorithm, at every step you take your current antichain $L$, and then modify it to a larger antichain $L'$. If we denote by $L_n$ the value of $L$ after the $n$th step of the algorithm, then it is *not* the case that $L_n \subset L_{n+1}$, so it is not clear how one would construct an infinite antichain this way; the usual (though not only) way of doing that is by constructing an infinite chain $L_1 \subset L_2 \subset L_3 \subset \cdots$ and then taking the union of all $L_n$. $\endgroup$ Sep 25, 2016 at 16:54
  • $\begingroup$ Thank you. I see.$L^{'}$ was only added to make my algorithm simpler to describe. In each step I only work on $L$. Any changes occur to $L$ and the output of each step (and the algorithm itself) is $L$. So I only have one output/sequence in total but it gets modified in each step. This is why I am not so sure the approach is correct. $\endgroup$
    – jjohn
    Sep 25, 2016 at 17:02
  • $\begingroup$ Your algorithm doesn't "work on $L$". It modifies $L$ at every step. Here is an example of what your algorithm might produce, in a different context: after iteration 1: $a$; after iteration 2: $b,b$; after iteration 3: $c,c,c$; and so on. These sequences get longer and longer, but you cannot combine them to one infinite sequence. $\endgroup$ Sep 25, 2016 at 17:05
  • $\begingroup$ Your goal is to exhibit an infinite antichain. Giving an antichain of size $n$ for every $n$ is not enough. $\endgroup$ Sep 25, 2016 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.