The property of the graph is the following: it's countable, undirected, simple, and for any infinite subset of vertices there are two vertices connected(by infinite Ramsey theorem this is in fact equivalent to that any infinite induced subgraph contains an infinite complete graph).

Is there a name for this kind of graphs? Moreover, do we have a structure theorem for them?


"Graphs with no infinite independent set" seems reasonably concise to me.

As a proof of concept, using that as a search term found me this paper, which proves a sort of structure theorem:

If a countable undirected graph has no infinite independent set, then it has a spanning subgraph which is the comparability graph of a poset with no infinite antichain.

The reverse implication also holds, since an independent set in a comparability graph is the same as an antichain in the poset, so this characterizes the minimal countable graphs with no infinite independent set.

Of course, you may then ask "Is there a structure theorem for posets with no infinite antichain?" Seaching for posets with no infinite antichain found me this result.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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