Finite graphs that realize all types over $n$-element sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:37:04Z http://mathoverflow.net/feeds/question/64659 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64659/finite-graphs-that-realize-all-types-over-n-element-sets Finite graphs that realize all types over $n$-element sets Stefan Geschke 2011-05-11T17:12:26Z 2011-05-11T20:06:02Z <p>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$. </p> <p>A countably infinite graph is isomorphic to the random graph iff it is $n$-saturated for all $n$.<br> Here are the questions:</p> <ol> <li><p>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?<br> (An $n$-saturated graph of size $\geq n$ has at least $n+2^n$ vertices, but this is probably far from optimal.)</p></li> <li><p>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.)</p></li> </ol> <p>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.</p> http://mathoverflow.net/questions/64659/finite-graphs-that-realize-all-types-over-n-element-sets/64663#64663 Answer by Ori Gurel-Gurevich for Finite graphs that realize all types over $n$-element sets Ori Gurel-Gurevich 2011-05-11T17:31:31Z 2011-05-11T17:31:31Z <ol> <li><p>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.</p></li> <li><p>I'm not sure I understood the question. If $G$ is $n$-saturated, then any graph of size $\le n$ is an induced subgraph.</p></li> </ol> http://mathoverflow.net/questions/64659/finite-graphs-that-realize-all-types-over-n-element-sets/64668#64668 Answer by Stefan Geschke for Finite graphs that realize all types over $n$-element sets Stefan Geschke 2011-05-11T17:53:37Z 2011-05-11T17:53:37Z <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/64659/finite-graphs-that-realize-all-types-over-n-element-sets/64675#64675 Answer by David Harris for Finite graphs that realize all types over $n$-element sets David Harris 2011-05-11T19:01:58Z 2011-05-11T19:01:58Z <p>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.</p> http://mathoverflow.net/questions/64659/finite-graphs-that-realize-all-types-over-n-element-sets/64686#64686 Answer by Andreas Blass for Finite graphs that realize all types over $n$-element sets Andreas Blass 2011-05-11T20:06:02Z 2011-05-11T20:06:02Z <p>Ben Rossman found a nice construction of $n$-saturated graphs; I adjusted it a bit and wrote it up. See <a href="http://www.mit.edu/~brossman/k-ec.pdf" rel="nofollow">http://www.mit.edu/~brossman/k-ec.pdf</a> . Set theorists like Stefan might enjoy the fact that it's reminiscent of Hausdorff's construction of independent families of (infinite) sets.</p>