3
$\begingroup$

Fix logic $L$ with equality and a binary relation symbol $E$.

The class of graphs can be identified with the class of models of the universal first-order Horn $L$-sentences $\forall x,y\; E(x,y) \rightarrow E(y,x)$ and $\forall x\; \lnot E(x,x)$. Note that this class includes infinite graphs.

An odd hole is a cycle with an odd number of vertices, at least five. An odd antihole is the complement of an odd hole. A Berge graph contains no induced odd holes or antiholes. By the Strong Perfect Graph theorem, a graph is perfect iff it is Berge. It is therefore possible to define the class of perfect graphs as the finite models of an infinite set of universal first-order sentences, each expressing a property "this graph does not contain an odd (anti)hole of order $2k+3$", for $k=1,2,\dots$. Call the class of all models of this set of sentences the $\omega$-perfect graphs (to highlight the fact that it may include infinite structures).

My primary question:

Is the class of $\omega$-perfect graphs finitely axiomatizable?

One could conclude this if the class of all $L$-structures that are not $\omega$-perfect were axiomatizable, but if this is the case then it is not obvious to me.

Further, the direct product of two perfect graphs is again perfect (for instance, this is an immediate corollary of a theorem of Ravindra and Parthasarathy). Since the class of $\omega$-perfect graphs can be axiomatized by a set of universal sentences, it is closed under ultraproducts. Hence the class of $\omega$-perfect graphs is closed under isomorphism, substructures (induced subgraphs), direct products, and ultraproducts, and therefore is a quasivariety definable by a set of universal (first-order) Horn sentences of $L$. (Although their existence seems guaranteed, justifying the title of this question, I don't actually know an explicit set of universal Horn axioms for the $\omega$-perfect graphs.) If the answer to the main question is affirmative, then this leads to the follow-on question:

Is the class of $\omega$-perfect graphs finitely axiomatizable by universal Horn sentences?

Edit: Thanks to bof for pointing out that if $G$ is $C_5$ with an edge added, then $G \times G$ is not perfect! I misinterpreted the result, the correct one is (in modern notation):

(Ravindra and Parthasarathy 1977, Theorem 3.2) $G_1 \times G_2$ is perfect iff either
1. $G_1$ or $G_2$ is bipartite, or
2. $G_1$ and $G_2$ are both (odd-hole,paw)-free.

The quasivariety generated by the $\omega$-perfect graphs therefore includes many non-perfect finite graphs. To match the question title, my second question should therefore be:

Is the quasivariety generated by all perfect graphs finitely axiomatizable?

$\endgroup$
1
  • 1
    $\begingroup$ If the class is axiomatizable by universal Horn sentences, and if it's finitely axiomatizable, then it's finitely axiomatizable by Horn sentences; this follows from the compactness theorem. However, the class of perfect graphs is not closed under direct product. Let $G$ be the graph obtained by adding one more edge to the cycle $C_5$.Then $G$ is perfect, but the direct product $G\times G$ is easily seen to contain $C_5$ as an induced subgraph. so it's not perfect. Many different products of graphs are considered in graph theory; maybe the theorem you cited is about some other graph product? $\endgroup$
    – bof
    Jul 16, 2014 at 1:24

1 Answer 1

3
$\begingroup$

Let $\sigma_k$ be a first-order sentence expressing the property "this graph does not contain an odd hole or antihole of order $2k+3$". If the theory of "$\omega$-perfect" graphs (I'd just call them perfect graphs) were finitely axiomatizable, then finitely many of the sentences $\sigma_k$ would imply all the rest of them. This is not the case, because for each $n$ the graph $C_{2n+3}$ satisfies $\sigma_k$ for all $k\ne n$.

$\endgroup$
3
  • $\begingroup$ I don't follow your implication that the finite set of axioms could be chosen from among the $\sigma_k$'s. Could you provide a hint? $\endgroup$ Jul 16, 2014 at 9:41
  • 1
    $\begingroup$ @AndrásSalamon: Since the $\sigma_k$ are a complete axiomatization, they prove the purported finite axiomatization. Such a proof uses only finitely many of the $\sigma_k$, which together form a complete axiomatization. $\endgroup$ Jul 16, 2014 at 10:35
  • $\begingroup$ @François G. Dorais: thanks! Clearly my model theory is even rustier than I thought. $\endgroup$ Jul 16, 2014 at 10:42

Your Answer

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

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