Shelah-Spencer VC (Anton, Sep 24 18h21).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. Let $M$ be some ambient structure. Fix embeddings of $\A_1, \B_1, \A_2$ into $M$. 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) + \delta (\B_2/\A_2)$
\end{Lemma}

\begin{diagram}
								&							&\B_1 \cup \B_2 = \B		\\
								&\ruLine    	&										&\luLine	\\
	\B_1 \cup \A	&           	&										&					&\B_2 \cup \A \\
								&\luLine			&										&\ruLine	\\
								&							&(\B_1 \cap \B_2) \cup \A \\
								&							&\uLine \\
								&							&\A_1 \cup \A_2 = \A\\
\end{diagram}

From the diagram we see that $\delta(\B/\A) \leq \delta(\B_1 \cup \A/\A) + \delta\left((\B_2 \cup \A)/((\B_1 \cap \B_2) \cup \A)\right)$. Thus all we need to do is to verify that $\delta\left((\B_2 \cup \A)/((\B_1 \cap \B_2) \cup \A)\right) \leq \delta (\B_2/\A_2)$. Look at the structure $\B^*$ induced inside of $B_2$ by vertices of $(B_1 \cap B_2) \cup A$. It contains $\A$. Suppose it is not the whole $B_2$. Then we have by minimality that $\delta(\B^*/\A_2) > 0$ and thus $\delta(\B_2/\B^*) < \delta (\B_2/\A_2)$. Now $(\B_2 \cup \A)/((\B_1 \cap \B_2) \cup \A)$ has the same number of vertices as $\B_2/\B^*$ and at least as many edges. Claim follows.



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}