7
$\begingroup$

Sorry if this is trivial but can someone construct for me any proper class of (not necessarily finite) undirected graphs $C$ for which no graph in $C$ is isomorphic to an induced subgraph of a different graph in $C$?

Or if not then prove that there exists no such class with this property.

It is relatively easy to think of proper classes of graphs, for example the class of complete graphs, since for any set $S$ there exists a unique complete graph $G$ with $V(G)=S$.

However I can't seem to think of any that satisfy the second condition that no graph in the proper class can be isomorphic to an induced subgraph of a different graph in said class.

I have a feeling that it is either impossible to construct such a class or there are many simple examples of such classes which I am just failing to notice due to an error in my intuition, so sorry if it is trivial.


This came up because I was thinking about hereditary graph properties during a bus ride (graph properties closed under induced subgraphs) and I know its not hard to show that for every hereditary property there exists a class of forbiden induced subgraphs which characterise it e.g. trivially take those graphs without the property, though this doesn't seem to imply the existence of a set of forbiden induced subgraphs rather only the existence of a class of such graphs which may or may not be a set as a result if there existed no such class as I described then the existence of a set of forbidden induced subgraphs not just a class of them would in fact be guaranteed for any hereditary graph property.

$\endgroup$
0

2 Answers 2

9
$\begingroup$

Perhaps surprisingly, you can't do this without additional set-theoretic axioms (so far as we currently know): the statement that there is no such proper class, Vopenka's principle, is currently not known to be inconsistent with ZFC (in fact, it's generally believed that it is consistent - which is amusing, given that Vopenka didn't think so and introduced it somewhat sarcastically).

Actually, Vopenka's principle says something stronger: that we can always find an elementary embedding. The definition of elementary embedding is a bit technical, but for now it suffices to observe that every elementary embedding is in fact an induced subgraph embedding. (That said, it turns out that we can drop elementarity here and get an equivalent principle - Vopenka's principle is very robust.)


That said, Vopenka's principle is in a precise sense "less likely" than its negation: while we can prove (in a very weak theory - much weaker than ZFC) ZFC + "Vopenka's principle fails" is consistent if ZFC itself is, the theory ZFC + Vopenka proves the consistency of ZFC itself. The standard example of the former is if V=L.

Indeed, Vopenka is extremely strong in terms of consistency strength - it lies fairly high up the large cardinal hierarchy.

$\endgroup$
6
$\begingroup$

Not really.

Vopěnka's principle states that every class of graphs, one embeds elementarily into the other.

But what is an elementary embedding of $G$ into $G'$? Well, it means, in particular, that $G$ is an induced subgraph of $G'$, since having an edge or not having an edge must be preserved by an elementary embedding of graphs.

So what you're asking for is a counterexample to Vopěnka's principle. And if you can prove that there is one, then you give a new upper bound to the large cardinal hierarchy.

$\endgroup$
4
  • $\begingroup$ Dangit, you beat me to it! $\endgroup$ Jan 7, 2020 at 17:20
  • $\begingroup$ @Asaf, I'm not really sure how graphs are formalized in model theory, but what if we have multiple edges between our vertices? How does elementarity help there? $\endgroup$ Jan 8, 2020 at 9:19
  • $\begingroup$ @ShervinSorouri: Graphs are irreflexive and symmetric relations. You're thinking about multigraphs. In either case, elementarity tells you how many (in the case of finitely many). $\endgroup$
    – Asaf Karagila
    Jan 8, 2020 at 9:21
  • $\begingroup$ Oh, I see. Thanks for the explanation! $\endgroup$ Jan 8, 2020 at 9:24

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.