Call a set $H$ of vertices of a graph $G$ homogeneous if it is either independent or complete. Every perfect graph of size $n$ has a homogeneous subset of size $\sqrt n$.

Noga Alon has shown that for every finite graph $G$ there is a finite graph $F$ of some size $n$ such that every induced subgraph of $F$ of size at least $\sqrt n$ contains an induced copy of $G$.

This implies the following: Let $G$ be any finite graph. Then there is a graph $F=(V,E)$ such that whenever $E'$ is another set of edges on the vertex set $V$ such that $(V,E')$ is perfect, then there is a set $H\subseteq V$ that is homogeneous with respect to $(V,E')$ such that the induced subgraph of $F$ on $H$ is isomorphic to $G$.

Let $C$ and $D$ be classes of finite graphs (closed under isomorphism). We say that $(C,D)$ is a Ramsey pair if the following holds: For every $G\in C$ there is $F\in C$ such that whenever $E'$ is another set of edges on the vertex set $V$ of $F$ such that $(V,E')\in D$, then there is a set $H\subseteq F$ that is homogeneous wrt $(V,E')$ such that the induced subgraph of $F$ on $H$ is isomorphic to $G$.

By the remark above, if $C$ is the class of all graphs and $D$ is the class of perfect graphs, then $(C,D)$ is a Ramsey pair. I know that the notion of a Ramsey triple, where $G$ and $F$ come from different classes, is probably more natural, but the Ramsey pairs did come up in some combinatorics related to set-theoretic forcing.
In some sense, $(C,D)$ being a Ramsey pair says that $C$ is substantially more complicated than $D$. In particular, if $C$ and $D$ are the same and nontrivial in the sense that they don't just consist of complete and empty graphs, then $(C,D)$ is not a Ramsey pair.

Here is the question

Can anyone come up with another nontrivial Ramsey pair?

  • 1
    $\begingroup$ Hi Stefan! (Nothing to say about your question yet. It is nice to see you here.) $\endgroup$ Jul 22, 2010 at 19:36

1 Answer 1


A semi-trivial pair: let $C$ be any class of graphs, and let $D$ contain the complete graphs on the vertex set of every graph in $C$.

Less trivial: for $C$, start with any set of finite graphs, and when $G$ is a graph in the set, then require the disjoint union of $G$ with itself to also be in the set. Let $C$ be the class formed by closing this set under isomorphism, and let $D$ contain the disjoint union of every graph in $C$ with a complete graph with the same number of vertices.

(Edit: an additional condition is needed to ensure that the choice of graph from $D$ has the required properties. One way is to start with a set of graphs where the sizes of the starting graphs are all relatively prime.)

To make your definition more interesting, such examples perhaps need to be ruled out? (The second one has $D$ as complicated as $C$.)

  • $\begingroup$ I am not sure I understand your answer. In your less trivial example, take a graph $(V,E)\in C$. Take another edge set $E'$ on $V$ such that $(V,E')\in D$. Now "half" of $(V,E')$ is homogeneous, but if $(V,E)$ is the disjoint union of $G$ with itself, how do you know that the large homogeneous set in $(V,E')$ is the set of vertices of of one copy of $G$? Otoh, if you start with the collection of all finite graphs for $C$ and let $D$ be the collection of all unions of a finite graph with a complete graph of the same size, then this is again a Ramsey pair, by the Alon result. $\endgroup$ Jul 23, 2010 at 18:58
  • $\begingroup$ To further clarify my comment: Since $D$ is closed under isomorphism, the second graph structure on the set $V$ (the one from $D$) can be "orthogonal" to the first (the one from $C$). $\endgroup$ Jul 23, 2010 at 19:20
  • $\begingroup$ I was thinking of the following reasoning. Start with G, choose F to be the graph consisting of two disjoint copies of G. Then G disjoint union with a G-sized complete graph will be in D. However, your conditions allow any choice of element from D, as long as the number of vertices is the same. So my example needs some additional conditions: for instance, the initial graphs could be of relatively prime sizes. $\endgroup$ Jul 23, 2010 at 20:29

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.