PROBLEM
The counting method is the following: for a graph $G$, we count the number $n_{1,H}$ of subgraphs of $G$ that are isomorphic to $H$ and for every crossing of $G$ we are given a number $n_{2,H}$ such that in every drawing of $G$, every pair of crossing edges are contained in at most $n_{2,H}$ subgraphs isomorphic to $H$. It follows (by counting pairs of crossing edges and $H$-isomorphic subgraphs that contain this pair) that $n_{1,H}cr(H)\leq n_{2,H}cr(H)$. Use the counting method for $H=K_n$ and $G=K_{n+1}$ to show that $\displaystyle\frac{cr(K_n)}{{n\choose 4}}$ is an increasing sequence. Show that this sequence has a limit.
PROOF
Let $n>4$. We first note that $n_{1,{K_n}}={n+1 \choose n}$; this follows from the fact that there are $n$ subgraphs $K_n$ in $K_{n+1}$. Next, we argue that $n_{2,{K_n}}={n-3 \choose n-4}$. We first fix a crossing using 4 vertices. Thus there are $n+1-4$ vertices left to choose a complete subgraph on $n-4$ vertices in $G$. So the claim is true. Now:
\begin{eqnarray*}
n_{1,{K_n}}cr(K_n)&\leq& n_{2,{K_n}}cr(K_{n+1})\\
{{n+1}\choose n}cr(K_n) &\leq& {{n+1}\choose n}cr(K_{n+1})\\
\displaystyle\frac{(n+1)!}{n!}cr(K_n)&\leq& \frac{(n-3)!}{(n-4)!}cr(K_{n+1})\\
\displaystyle\frac{(n+1)!}{4!n!}cr(K_n)&\leq& \frac{(n-3)!}{4!(n-4)!}cr(K_{n+1})\\
\displaystyle\frac{cr(K_n)}{{n\choose 4}}&\leq& \frac{cr(K_{n+1})}{{{n+1}\choose 4}}
\end{eqnarray*}
Thus the sequence is increasing.
Moreover, note that the largest possible number of crossings is ${n \choose 4}$ so $\displaystyle\frac{cr(K_n)}{{n\choose 4}}\leq 1$. Thus the sequence is bounded and monotonic, thus convergent.
The counting method is the following: for a graph $G$, we count the number $n_{1,H}$ of subgraphs of $G$ that are isomorphic to $H$ and for every crossing of $G$ we are given a number $n_{2,H}$ such that in every drawing of $G$, every pair of crossing edges are contained in at most $n_{2,H}$ subgraphs isomorphic to $H$. It follows (by counting pairs of crossing edges and $H$-isomorphic subgraphs that contain this pair) that $n_{1,H}cr(H)\leq n_{2,H}cr(H)$. Use the counting method for $H=K_n$ and $G=K_{n+1}$ to show that $\displaystyle\frac{cr(K_n)}{{n\choose 4}}$ is an increasing sequence. Show that this sequence has a limit.
PROOF
Let $n>4$. We first note that $n_{1,{K_n}}={n+1 \choose n}$; this follows from the fact that there are $n$ subgraphs $K_n$ in $K_{n+1}$. Next, we argue that $n_{2,{K_n}}={n-3 \choose n-4}$. We first fix a crossing using 4 vertices. Thus there are $n+1-4$ vertices left to choose a complete subgraph on $n-4$ vertices in $G$. So the claim is true. Now:
\begin{eqnarray*}
n_{1,{K_n}}cr(K_n)&\leq& n_{2,{K_n}}cr(K_{n+1})\\
{{n+1}\choose n}cr(K_n) &\leq& {{n+1}\choose n}cr(K_{n+1})\\
\displaystyle\frac{(n+1)!}{n!}cr(K_n)&\leq& \frac{(n-3)!}{(n-4)!}cr(K_{n+1})\\
\displaystyle\frac{(n+1)!}{4!n!}cr(K_n)&\leq& \frac{(n-3)!}{4!(n-4)!}cr(K_{n+1})\\
\displaystyle\frac{cr(K_n)}{{n\choose 4}}&\leq& \frac{cr(K_{n+1})}{{{n+1}\choose 4}}
\end{eqnarray*}
Thus the sequence is increasing.
Moreover, note that the largest possible number of crossings is ${n \choose 4}$ so $\displaystyle\frac{cr(K_n)}{{n\choose 4}}\leq 1$. Thus the sequence is bounded and monotonic, thus convergent.
No comments:
Post a Comment