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

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:

  1. 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.)

  2. 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.

share|improve this question
    
Your example has only $15$ vertices, not $30$. –  bof Nov 29 at 8:29
    
Your are absolutely right. I somehow failed to compute correctly the binomial coefficient. 15 vertices doesn't sound so bad. –  Stefan Geschke Nov 30 at 9:39

4 Answers 4

up vote 5 down vote accepted
  1. 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.

  2. I'm not sure I understood the question. If $G$ is $n$-saturated, then any graph of size $\le n$ is an induced subgraph.

share|improve this answer
    
You are right, the second question is silly (if the first has a positive answer for all $n$). –  Stefan Geschke May 11 '11 at 17:40
    
$G(m,\frac12)$ is the graph on $m$ vertices where to distinct vertices form an edge with probability $\frac12$? –  Stefan Geschke May 11 '11 at 17:42
    
Indeed. This is also a random graph chosen uniformly among all labeled graphs on $n$ vertices. –  Ori Gurel-Gurevich May 11 '11 at 18:14
    
Also, the computation remains valid for $G(n,p)$ (with a different constant $C$). –  Ori Gurel-Gurevich May 11 '11 at 18:15

Ben Rossman found a nice construction of $n$-saturated graphs; I adjusted it a bit and wrote it up. See http://research.nii.ac.jp/~rossman/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.

share|improve this answer
    
Thank you, Andreas. This was exactly the type of construction I was looking for. –  Stefan Geschke May 11 '11 at 22:00

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.

share|improve this answer

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.

share|improve this answer

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.