Finite graphs that realize all types over $n$-element sets - MathOverflow

Finite graphs that realize all types over $n$-element sets

2011-05-11T17:12:26Z

Call a graph $G$ $n$-saturated if for every set $A$ of size $n$ of vertices and all $B\subseteq A$ there is a vertex $v\not\in A$ that forms an edge with all $w\in B$ and does not form an edge with any $w\in A\setminus B$.

A countably infinite graph is isomorphic to the random graph iff it is $n$-saturated for all $n$.
Here are the questions:

Is it true that for all $n$ there is a finite graph (of size at least $n$) that is $n$-saturated? If yes, are there reasonable upper and lower bounds on the size of such a graph?
(An $n$-saturated graph of size $\geq n$ has at least $n+2^n$ vertices, but this is probably far from optimal.)
Is every finite graph an induced subgraph of a finite $n$-saturated graph? (Edit: As Ori Gurel-Gurevich pointed out, the second question is silly. Clearly, if $G$ is $n$-saturated (and of size at least $n$), then it has every graph with $n$-vertices as an induced subgraph.)

Example: There is a $2$-saturated graph: Let the vertices of $G$ be the $2$-element subsets of a set with $6$ elements. Two of those vertices form an edge if they (as sets) have a non-empty intersection. It is easily checked that this graph is $2$-saturated. But it also has 30 vertices. That seems a lot.

Answer by Ori Gurel-Gurevich for Finite graphs that realize all types over $n$-element sets

2011-05-11T17:31:31Z

If $G=G(m,\frac12$) then for any fixed set $A$ and subset $B$ and $v$ we have the probability that $v$ is connected to $B$ but not to $A\setminus B$ is $2^{-n}$. The probability that all $v$ fail to do so is $(1-2^{-n})^{m-n} \approx e^{m 2^-n}$. There are less than $(2m)^n$ such subsets $A$ and $B$, so union bound gives that when $m=C 2^n n^2 $ (for some large $C$) the probability that for some $A$ and $B$ there will be no witness $v$ is negligible.
I'm not sure I understood the question. If $G$ is $n$-saturated, then any graph of size $\le n$ is an induced subgraph.

Answer by Stefan Geschke for Finite graphs that realize all types over $n$-element sets

2011-05-11T17:53:37Z

I have just remembered that Ori's computation shows up in the argument for showing that the countably infinite random graph satisfies exactly those first order statements that are true for almost all finite graphs.

Looking at this from the other direction: Being $n$-saturated is expressible by a first order sentence and is true for the random graph. Hence it is true for almost all finite graphs. In particular, there is a finite graph that is $n$-saturated.

Here "almost all finite graphs have property $P$" means the limit as $n$ goes to $\infty$ of the quotients of the number of all graphs on ${1,\dots,n}$ with the property $P$ and the number of all graphs on ${1,\dots,n}$ is 1.

Answer by David Harris for Finite graphs that realize all types over $n$-element sets

2011-05-11T19:01:58Z

I would like to add to Stefan's statement. The sentence $\Theta$ which expresses "G is $n$-saturated" is true of almost all finite graphs. The interpretation of this limit is that, as the size $|G| = k \rightarrow \infty$, the probability that a size $k$ graph is $n$-saturated goes to 1. In particular, there can be only finitely many $k$ for which this probability is 0, otherwise the limit as $k \rightarrow \infty$ would not converge.

Answer by Andreas Blass for Finite graphs that realize all types over $n$-element sets

2011-05-11T20:06:02Z

Ben Rossman found a nice construction of $n$-saturated graphs; I adjusted it a bit and wrote it up. See http://www.mit.edu/~brossman/k-ec.pdf . Set theorists like Stefan might enjoy the fact that it's reminiscent of Hausdorff's construction of independent families of (infinite) sets.