6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your example has only $15$ vertices, not $30$. $\endgroup$
    – bof
    Nov 29, 2014 at 8:29
  • $\begingroup$ Your are absolutely right. I somehow failed to compute correctly the binomial coefficient. 15 vertices doesn't sound so bad. $\endgroup$ Nov 30, 2014 at 9:39

4 Answers 4

5
$\begingroup$
  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.

$\endgroup$
4
  • $\begingroup$ You are right, the second question is silly (if the first has a positive answer for all $n$). $\endgroup$ May 11, 2011 at 17:40
  • $\begingroup$ $G(m,\frac12)$ is the graph on $m$ vertices where to distinct vertices form an edge with probability $\frac12$? $\endgroup$ May 11, 2011 at 17:42
  • $\begingroup$ Indeed. This is also a random graph chosen uniformly among all labeled graphs on $n$ vertices. $\endgroup$ May 11, 2011 at 18:14
  • $\begingroup$ Also, the computation remains valid for $G(n,p)$ (with a different constant $C$). $\endgroup$ May 11, 2011 at 18:15
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, Andreas. This was exactly the type of construction I was looking for. $\endgroup$ May 11, 2011 at 22:00
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.