{"id":605,"date":"2014-02-10T11:50:16","date_gmt":"2014-02-10T16:50:16","guid":{"rendered":"http:\/\/matroidunion.org\/?p=605"},"modified":"2014-02-10T11:50:16","modified_gmt":"2014-02-10T16:50:16","slug":"the-geometric-erds-stone-theorem","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=605","title":{"rendered":"The Geometric Erdös-Stone Theorem"},"content":{"rendered":"

Guest post by Jim Geelen.<\/em>
\n$\\newcommand{\\del}{\\,\\backslash\\,}$ $\\newcommand{\\con}{\/}$ $\\newcommand{\\bF}{\\mathbb{F}}$ $\\newcommand{\\cL}{\\mathcal{L}}$ $\\newcommand{\\lt}{<}$ $\\newcommand{\\gt}{>}$ $\\DeclareMathOperator{\\ex}{ex}$ $\\DeclareMathOperator{\\rank}{rank}$ $\\DeclareMathOperator{\\PG}{PG}$ $\\DeclareMathOperator{\\AG}{AG}$ $\\DeclareMathOperator{\\BB}{BB}$<\/p>\n

In my last two posts I discussed the Turán problems for the binary projective geometry<\/a> and for the binary affine geometry.<\/a> This time I will consider the Turán problem for an arbitrary binary geometry. An extraordinary connection between Turán densities and critical exponents emerges.<\/p>\n

Graphs <\/h1>\n

Recall that a graph is called $H$-free <\/em> if it has no subgraph isomorphic to $H$. The Turán problem <\/em> for a given graph $H$ is to determine, for each integer $n$, the maximum number, $\\ex(H,n)$, of edges among all $n$-vertex $H$-free graphs.<\/p>\n

The following result, due to Erdös and Stone [ES46], is among my favourite theorems in extremal graph theory. It reveals an unexpected connection between the chromatic number of a graph and the asymptotic behaviour of its Turán numbers.<\/p>\n

Erdös-Stone Theorem: <\/strong> Let $H$ be a graph with chromatic number $\\chi\\ge 2$. Then $$ \\lim_{n\\rightarrow\\infty} \\frac{\\ex(H,n)}{|E(K_n)|} = \\frac{\\chi-2}{\\chi-1}.$$
\n<\/i><\/p>\n

Note that the Turán graphs $T(n,\\chi)$ are $H$-free and have densities approaching $\\frac{\\chi-2}{\\chi-1}.$<\/p>\n

The Erdös-Stone Theorem shows that $\\ex(H,n) = \\frac{\\chi-2}{\\chi-1}{n\\choose 2} + o(n^2)$, which gives the asymptotic behaviour of $\\ex(H,n)$ except when $\\chi=2$. Determining the asymptotic behaviour of the Turán numbers of bipartite graphs is a difficult open problem, which I discussed last time.<\/p>\n

Binary Geometries <\/h1>\n

Recall that a binary geometry is called $N$-free <\/em> if it has no restriction isomorphic to $N$. The Turán problem <\/em> for a given binary geometry $N$ is to determine, for each integer $r$, the maximum number, $\\ex(N,r)$, of points among all rank-$r$ $N$-free binary geometries. The Bose-Burton geometry <\/em> $\\BB(r,c)$ is the binary geometry obtained from $\\PG(r-1,2)$ by deleting all of the points in a flat of rank $r-c$.<\/p>\n

The following result relates the critical exponent of a binary geometry and the asymptotic behaviour of its Turán numbers; see [GN].<\/p>\n

Geometric Erdös-Stone Theorem: <\/strong> Let $N$ be a binary geometry with critical exponent $c\\ge 1$. Then $$ \\lim_{r\\rightarrow\\infty} \\frac{\\ex(N,r)}{|\\PG(r-1,2)|} = 1-2^{-(c-1)}.$$
\n<\/i><\/p>\n

Note that the Bose-Burton geometries $\\BB(r,c-1)$ are $N$-free and have densities approaching $1-2^{-(c-1)}.$<\/p>\n

The Geometric Erdös-Stone Theorem shows that $\\ex(N,r) = 2^r – 2^{r-c+1} + o(2^r)$, which gives the asymptotic behaviour of $\\ex(N,r)$ except when $c=1$. When $c=1$, the result is implied by the Binary Density Hales-Jewett Theorem which we proved last time.<\/p>\n

We reformulate the Geometric Erdös-Stone Theorem below to facilitate its proof. The proof is a bit on the heavy side for a blog post, but it is surprizingly short considering the result, and it is easier than the proof of the Erdös-Stone Theorem.<\/p>\n

Theorem: <\/strong> Let $c\\ge 1$ be an integer. Then, for each integer $m\\gt c$ and real number $\\epsilon>0$, $$\\ex( \\BB(m,c); r) \\lt (1- 2^{-(c-1)}+\\epsilon) |\\PG(r-1,2)|,$$ for all sufficiently large $r$.
\n<\/i><\/p>\n

Proof Sketch. <\/strong> The proof is by induction on $c$; the case that $c=1$ follows directly from the Binary Density Hales-Jewett Theorem. So we may assume that $c\\gt 1$ and that the result holds for $c-1$.<\/p>\n

Let $m\\gt c$ be an integer, let $\\epsilon\\gt 0$ be a real number, and let $r\\gg n$ be large integers. Now let $M$ be a rank-$r$ binary geometry with $|M| \\ge (1-2^{-(c-1)}+\\epsilon) |\\PG(r-1,2)|$. By the inductive assumption, $M$ has a $\\BB(n,c-1)$-restriction. Consider $M$ as a restriction of $\\PG(r-1,2)$. Thus there are flats $F_0\\subseteq F_1$ of $\\PG(r-1,2)$ such that $\\rank(F_1)=n$, $\\rank(F_0)=n-c+1$, and $F_1-F_0\\subseteq M$.<\/p>\n

So by an easy averaging argument, there exists a rank-$(n+1)$ flat $F_2$ containing $F_1$ such that $$|M\\cap(F_2-F_1)| \\ge \\left(1-2^{1-c} +\\frac{\\epsilon}{2}\\right)|F_2-F_1| = (1-2^{1-c})2^{n} +\\frac{\\epsilon}{2} 2^n .$$<\/p>\n

For a flat $F$ of $\\PG(r-1,2)$ and point $e\\not\\in F$, we let $F+e$ denote the flat spanned by $F\\cup\\{e\\}$. Let $e\\in F_2-F_1$ and let $Q_0 = (F_0+e)-F_0$. Now let $F_0^c\\subseteq F_1$ be a rank-$(c-1)$ flat that is disjoint from $F_0$. Now let $S= (F_2-F_1)\\cap E(M)$ and, for each $f\\in Q_0$, let $S_f = (F_0^c + f)\\cap S$. Note that $(S_f\\, : \\, f\\in Q_0)$ partitions $S$ and $|S_f|\\le 2^{c-1}$. By another easy averaging argument, there is a $\\frac{\\epsilon}{2} 2^n$-element subset $Q_1$ of $Q_0$ such that $|S_f|= 2^{c-1}$ for each $f\\in Q_1$. By the Binary Density Hales-Jewett Theorem, there is a subset $Q_2$ of $Q_1$ such that $M|Q_2 \\cong \\AG(m-c, 2)$. Let $F$ be the flat of $\\PG(n-1,2)$ spanned by $F_0^c$ and $Q_2$. Thus $F$ has rank $m$, $F_0^c\\subseteq F$, and, since $Q_2\\subseteq Q_1$, $F-F_1\\subseteq M$. So the restriction of $M$ to $F-F_0$ gives $\\BB(m,c)$, as required. $\\Box$<\/p>\n

Open problem <\/h1>\n

Bonin and Qin [BQ00] determine exact values for the Turán numbers for several classes of geometries. There are many other natural classes that are yet to be considered; this might be an interesting avenue for further research. I will conclude with one problem in that direction. We call a binary geometry $c$-critical <\/em> if it has critical exponent $c$ and each of its proper restrictions has critical exponent $\\lt c$.<\/p>\n

Conjecture: <\/strong> For any $c$-critical binary geometry $N$, $\\ex(N,r) = 2^r – 2^{r-c+1},$ for all sufficiently large $r$.
\n<\/i><\/p>\n

\nReferences
\n<\/h1>\n

[BQ00] <\/b> J.E. Bonin, H. Qin, Size functions of subgeometry-closed classes of representable combinatorial geometries, Discrete Math. 224 (2000).<\/p>\n

[ES46] <\/b> P. Erdös, A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946).<\/p>\n

[GN] <\/b> J. Geelen, P. Nelson, An analogue of the Erdös-Stone Theorem for finite geometries, arXiv:1203.1911<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Guest post by Jim Geelen. $\\newcommand{\\del}{\\,\\backslash\\,}$ $\\newcommand{\\con}{\/}$ $\\newcommand{\\bF}{\\mathbb{F}}$ $\\newcommand{\\cL}{\\mathcal{L}}$ $\\newcommand{\\lt}{<}$ $\\newcommand{\\gt}{>}$ $\\DeclareMathOperator{\\ex}{ex}$ $\\DeclareMathOperator{\\rank}{rank}$ $\\DeclareMathOperator{\\PG}{PG}$ $\\DeclareMathOperator{\\AG}{AG}$ $\\DeclareMathOperator{\\BB}{BB}$ In my last two posts I discussed the Turán problems for the binary projective geometry and for the binary affine geometry. This time I … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-605","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/605","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=605"}],"version-history":[{"count":4,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/605\/revisions"}],"predecessor-version":[{"id":609,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/605\/revisions\/609"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=605"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=605"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=605"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}