Content deleted Content added
m →Density: better word |
→Density: ce |
||
Line 52:
One formulation of the [[Ruzsa–Szemerédi problem]] asks for the maximum number of edges in an <math>n</math>-vertex locally linear graph. As [[Imre Z. Ruzsa]] and [[Endre Szemerédi]] proved, this maximum number is <math>o(n^2)</math> but is <math>\Omega(n^{2-\varepsilon})</math> for every <math>\varepsilon>0</math>. The construction of locally linear graphs from progression-free sets leads to the densest known locally linear graphs, with <math>n^2/\exp O(\sqrt{\log n})</math> edges. (In these formulas, <math>o</math>, <math>\Omega</math>, and <math>O</math> are examples of [[little o notation]], [[big Omega notation]], and [[big O notation]], respectively.){{r|rs}}
Among [[planar graph]]s, the maximum number of edges in a locally linear graph with <math>n</math> vertices is <math>\tfrac{12}{5}(n-2)</math>. The graph of the [[cuboctahedron]] is the first in an infinite sequence of [[polyhedral graph]]s with <math>n=5k+2</math> vertices and <math>\tfrac{12}{5}(n-2)=12k</math> edges, for <math>k=2,3,\dots</math>, constructed by expanding the quadrilateral faces of <math>K_{2,k}</math> into antiprisms. These examples show that
==References==
| |||