Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If I'm giving a lecture on trivial definable closure (as a property of graphs), what is a good example of a graph that I can easily draw to depict the concept of trivial dcl?

share|improve this question
1  
Can you please tell me the definition of definable closure? I would be interested in knowing it, but I am not able to find it quickly. –  Valerio Capraro Oct 31 '11 at 16:37
add comment

1 Answer

The infinite edgeless graph has trivial definable closure, since for any finite tuple $\bar a$, there are automorphisms fixing $\bar a$ and swapping any two vertices outside of $\bar a$.

But of course, the infinite edgeless graph is so not interesting to have drawn on the chalkboard. (I suppose you could address this by drawing the complete graph on infinitely many vertices, which also has trivial definable closure for the same reason.) But I would recommend another example, the countable random graph. For any finite tuple $\bar a$ and any vertex $b$ outside $\bar a$, there is an automorphism fixing $\bar a$ and moving $b$, and so the definable closure of $\bar a$ is itself. This situation would be a good excuse to discuss the random graph, if you have not done so already.

share|improve this answer
1  
I really don't know the answer to this, but it seems that the Henson graphs, $H_n$ (Fraisse limits of the class of finite graphs with $K_n$, the complete graph on $n$ vertices banned) should have trivial dcl, but I don't know. On the other hand, in the case of the random graph, the complement is the random graph as well, but with these graphs, their complements are actually different, and they should also have the property, right? Can anyone think of any other examples (besides by doing things like taking disjoint unions of these graphs or finite empty or complete graphs)? –  James Freitag Oct 31 '11 at 22:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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