# Disproving well-quasi-order by providing an infinite anti-chain

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!

• 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. – Emil Jeřábek Sep 25 '16 at 16:08

• 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$. – Yuval Filmus Sep 25 '16 at 16:54
• 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. – jjohn Sep 25 '16 at 17:02
• 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. – Yuval Filmus Sep 25 '16 at 17:05
• Your goal is to exhibit an infinite antichain. Giving an antichain of size $n$ for every $n$ is not enough. – Yuval Filmus Sep 25 '16 at 17:05