Locally linear graph: Difference between revisions

Revision as of 19:24, 21 March 2021

Revision as of 19:25, 21 March 2021

Line 50:

[[File:Dense planar locally linear.svg|thumb|The densest possible locally linear planar graphs are formed by gluing an antiprism (red vertices and black edges) into each quadrilateral face of a planar graph (blue vertices and dashed yellow edges)]]

{{main|Ruzsa–Szemerédi problem}}

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 partexamples 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 this upper bound is tight.{{r|z}}