Shelah-Spencer VC (Anton, Oct 25 14h17).tex

\documentclass{amsart}

\usepackage{../AMC_style}	
\usepackage{../Research}

\usepackage{diagrams}

  \newcommand{\A}{\mathcal A}
  \newcommand{\B}{\mathcal B}
\renewcommand{\C}{\mathcal C}
  \newcommand{\D}{\mathcal D}
\renewcommand{\H}{\mathcal H}
  \newcommand{\G}{\mathcal G}
  \newcommand{\M}{\mathcal M}

  \newcommand{\K}{\boldface K_\alpha}
\renewcommand{\S}{S_\alpha}

\begin{document}

\title{Some vc-density computations in Shelah-Spencer graphs}
\author{Anton Bobkov}
\email{bobkov@math.ucla.edu}

\begin{abstract}
	We compute vc-densities of minimal extension formulas in Shelah-Spencer random graphs.
\end{abstract}

\maketitle

We fix the density of the graph $\alpha$.

\begin{Lemma}
	For any $\A \in \K$ and $\epsilon > 0$ there exists an $\B$ such that $(\A, \B)$ is minimal and $\delta(\B/\A) < \epsilon$.
\end{Lemma}

\begin{proof}
	Let $m$ be an integer such that $m\alpha < 1 < (m+1)\alpha$. Suppose $\A$ has less than $m+1$ vertices. Make a construction $\A_0 = \A$ and $\A_{i+1}$ is $\A_i$ with one extra vertex connected to every single vertex of $A_i$. Stop when the total number of vertices is $m+1$. Proceed as in \cite{Laskowski} 4.1. Resulting construction is still minimal.
\end{proof}

\begin{Lemma}
	Let $\A_1 \subset \B_1$ and $\A_2 \subset \B_2$ be $\K$ structures with $(\A_2, \B_2)$ a minimal pair with $\epsilon = \delta (\B_2/\A_2)$. Let $M$ be some ambient structure. Fix embeddings of $\A_1, \B_1, \A_2$ into $M$. Assume that it is not that case that $\A_2 \subset \B_2$ and $\A_1$ is disjoint from $\A_2$. Now consider all possible embeddings $f \colon \B_2 \to M$ over $\A_1$.  Let $\A = \A_1 \cup \A_2$ and $\B_f = \B_1 \cup f(\B_2)$ with $\delta_f = \delta(\B_f/\A)$. Then $\delta_f$ is at most $\delta(\B_1 \cup \A/\A) + \epsilon$
\end{Lemma}

Fix an embedding $f$. It induces the following substructure diagram in $M$. Denote 
\begin{align*}
	\A &= \A_1 \cup \A_2 \\
	\B_f^* &= \B_1 \cup f(\B_2) \\
	\B_1^* &= \B_1 \cup \A \\
	\B_2^* &= f(\B_2) \cup \A \\
	\B^* &= (\B_1 \cap f(\B_2)) \cup \A
\end{align*}

\begin{diagram}
								&							&\B_f		\\
								&\ruLine    	&										&\luLine	\\
	\B_1^*      	&           	&										&					&\B_2^* \\
								&\luLine			&										&\ruLine	\\
								&							&\B^* \\
								&							&\uLine \\
								&							&\A\\
\end{diagram}

From the diagram we see that
\begin{align*}
	\delta(\B_f/\A) \leq \delta(\B_1^*/\A) + \delta(\B_2^*/\B^*)
\end{align*}
Thus all we need to do is to verify that
\begin{align*}
	\delta(\B_2^*/\B^*) \leq \epsilon
\end{align*}
Let $\B'$ denote graph induced on all the vertices in $(f(B_2) / B_1) \cup A_2$.
Then $\B'$ is a substructure of $\B_2$ over $\A_2$. By minimality we get that $\delta(\B'/\A_2) \leq \epsilon$. Moreover $\delta(\B_2^*/\B^*) \leq \delta(\B'/\A_2)$ thus proving the claimed statement.
Then $\delta (\B^*/A_2)$ has to be less than $\delta (\B_2/\A_2)$ by minimality of $(\B_2, \A_2)$. Relative dimension of the whole construction has to be even smaller.
It is easy to show that this construction induces a proper subpair in $(\A_2, \B_2)$ which has to have smaller dimension.



Let $\phi(x,y)$ be a formula in a random graph with $|x|=|y|=1$ saying that there exists a minimal extension $M$ over $\{x,y\}$ of relative dimension $\epsilon$. Let $n$ be such that $n\epsilon < 1 < (n+1)\epsilon$. Then we argue that $vc(\phi) = n$.

Fix a $m$-strong (for any $m > |M|$) set of non-connected vertices $B$. Fix some $a$. We invesitgate the trace of $\phi(x, a)$ on $B$. Suppose we have $b_1, \ldots, b_k$ satisfying $\phi(b_i, a)$ as witnessed by $M_j$. Relative dimension of $M_1 \cup M_2 \cup \ldots \cup M_j \cup {a}$ is minimized when all $M_j$ are disjoint (by minimality). Thus for that dimension to be positive we can have at most $n$ extensions.

\begin{thebibliography}{9}

\bibitem{Laskowski}
	Michael C. Laskowski, \textsl{A simpler axiomatization of the Shelah-Spencer almost sure theories,}
	Israel J. Math. \textbf{161} (2007), 157-186. MR MR2350161

\end{thebibliography}

\end{document}