Locally linear graph
[2] Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.
The question of how many edges locally linear graphs can have is one of the formulations of the Ruzsa–Szemerédi problem.
They are the only finite graphs having the stronger property that every pair of vertices (adjacent or not) share exactly one common neighbor.
[3] More generally every triangular cactus graph, a graph formed by gluing triangles at shared vertices without forming any additional cycles, is locally linear.
[8] A more complicated expansion process applies to planar graphs.
The numbers of edges and vertices of the result can be calculated from Euler's polyhedral formula: if
[5] For instance, the cuboctahedron can again be produced in this way, from the two faces (the interior and exterior) of a 4-cycle.
The removed 4-cycle of this construction can be seen on the cuboctahedron as a cycle of four diagonals of its square faces, bisecting the polyhedron.
In this graph, two vertices are adjacent when the corresponding subsets are disjoint sets, having no elements in common.
[2] Locally linear graphs can also be constructed from progression-free sets of numbers.
To construct this graph, make three sets of vertices, each numbered from
The triangles in a locally linear graph can be equivalently thought of as forming a 3-uniform hypergraph.
Such a hypergraph must be linear, meaning that no two of its hyperedges (the triangles) can share more than one vertex.
In this view it makes sense to talk about the girth of the hypergraph.
More algebraically, the vertices of the same graph can be represented by homogeneous coordinates: these are triples of values
from a finite field, not all zero, where two triples define the same point in the plane whenever they are scalar multiples of each other.
The polarity graph for a finite field of odd order
[10] A graph is regular when all of its vertices have the same degree, the number of incident edges.
The Cartesian product of two locally linear regular graphs is again locally linear and regular, with degree equal to the sum of the degrees of the factors.
(No two vertices of the triangle can share a neighbor without violating local linearity.)
The four regular graphs meeting this bound on the number of vertices are the 3-vertex 2-regular triangle
[2] A strongly regular graph can be characterized by a quadruple of parameters
include (99,14,1,2) and (115,18,1,3) but it is unknown whether strongly regular graphs with those parameters exist.
[16] There are finitely many distance-regular graphs of degree 4 or 6 that are locally linear.
[17] One formulation of the Ruzsa–Szemerédi problem asks for the maximum number of edges in an
As Imre Z. Ruzsa and Endre Szemerédi proved, this maximum number is
[5] Every locally linear graph has the property that it remains connected after any matching is removed from it, because in any path through the graph, each matched edge can be replaced by the other two edges of its triangle.
[4] One application of locally linear graphs occurs in the formulation of Greechie diagrams, which are used in quantum logic to help determine whether certain Hilbert space equations can be inferred from each other.
[10] A combination of random sampling and a graph removal lemma can be used to find large high-girth 3-uniform hypergraphs within arbitrary 3-uniform linear hypergraphs or partial Steiner triple systems.
This method can then be used to prove asymptotically tight lower bounds on the independence number of 3-uniform linear hypergraphs and partial Steiner triple systems.
