Locally linear graph: Difference between revisions

Revision as of 05:55, 6 September 2020

Latest revision as of 10:33, 14 July 2025

(45 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Graph where every edge is in one triangle}}

[[File:Paley933-unique-triangleduoprism graph.svg|thumb|The nine-vertex [[Paley graph]] is locally linear. One of itsIts six triangles isare highlightedvisible as equilateral triangles in greenthis layout.]]

In [[graph theory]], a '''locally linear graph''' is an [[undirected graph]] in which the [[neighborhood (graph theory)|neighborhood]] of every [[vertex (graph theory)|vertex]] is an [[induced matching]]. That is, for every vertex <math>v</math>, every neighbor of <math>v</math> should be adjacent to exactly one other neighbor of <math>v</math>. Equivalently, every edge <math>uv</math> of such a graph belongs to a unique triangle <math>uvw</math>.{{r|f}} Locally linear graphs have also been called locally matched graphs.{{r|lpv}}

In [[graph theory]], a '''locally linear graph''' is an [[undirected graph]] in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its [[neighborhood (graph theory)|neighbors]] are each adjacent to exactly one other neighbor. That is, locally (from the point of view of any one vertex) the rest of the graph looks like a [[perfect matching]].{{r|f}} Locally linear graphs have also been called locally matched graphs.{{r|lpv}} More technically, the triangles of any locally linear graph form the [[hyperedge]]s of a triangle-free 3-uniform linear [[hypergraph]], and they form the blocks of certain [[Steiner system|partial Steiner triple systems]]; and the locally linear graphs are exactly the [[Gaifman graph]]s of these hypergraphs or partial Steiner systems.

Many constructions for locally linear graphs are known. Examples of locally linear graphs include the [[triangular cactus graph]]s, the [[line graph]]s of 3-regular [[triangle-free graph]]s, and the [[Cartesian product of graphs|Cartesian products]] of smaller locally linear graphs. Certain [[Kneser graph]]s, and certain [[strongly regular graph]]s, are also locally linear.

SomeThe question of how many edges locally linear graphs can have is one of the formulations of the [[Ruzsa–Szemerédi problem]]. Although [[dense graph]]s can have a number of edges thatproportional isto near-quadratic.the Thesquare questionof the number of howvertices, denselocally theselinear graphs canhave bea issmaller onenumber of theedges, formulationsfalling short of the [[Ruzsa–Szemerédisquare problem]]by at least a small non-constant factor. The densest [[planar graph]]s that can be locally linear are also known. The least dense locally linear graphs are the triangular cactus graphs.

==Constructions and examples==

[[File:Cuboctahedron.jpg|thumb|The [[cuboctahedron]], a planar locally linear graph that can be formed as the line graph of a cube or by gluing antiprisms onto the inside and outside faces of a 4-cycle]]

Several constructions for locally linear graphs are known.

==Constructions and examples==

===Gluing and products===

[[File:Friendship graphs.svg|thumb|[[Friendship graph]]s]]

The [[friendship graph]]s, graphs formed by gluing together a collection of triangles at a single shared vertex, are locally linear. They are the only finite graphs having the stronger property that every pair of vertices (adjacent or not) share exactly one common neighbor.{{r|ers}} More generally every [[Cactus graph#Triangular cactus|triangular cactus graph]], a graph informed whichby allgluing simpletriangles cyclesat areshared trianglesvertices andwithout allforming pairsany of simpleadditional cycles have at most one vertex in common, is locally linear.{{r|fp}}

Let <math>G</math> and <math>H</math> be any two locallyLocally linear graphs, selectmay abe triangleformed from eachsmaller oflocally them, and glue the twolinear graphs together by identifyingthe correspondingfollowing pairs of vertices in these triangles (this isoperation, a form of the [[clique-sum]] operation on graphs). Then the resulting graph remains locally linear.{{r|z}}

Let <math>G</math> and <math>H</math> be any two locally linear graphs, select a triangle from each of them, and glue the two graphs by merging together corresponding pairs of vertices in the two selected triangles. Then the resulting graph remains locally linear.{{r|z}}

The [[Cartesian product of graphs|Cartesian product]] of any two locally linear graphs remains locally linear, because any triangles in the product come from triangles in one or the other factors. For instance, the nine-vertex [[Paley graph]] (the graph of the [[3-3 duoprism]]) is the Cartesian product of two triangles.{{r|f}} The [[Hamming graph]] <math>H(d,3)</math> is a Cartesian product of <math>d</math> triangles, and again is locally linear.{{r|djlp}}

The [[Hamming graph]]s <math>H(d,3)</math> are products of <math>d</math> triangles, and again are locally linear.{{r|djlp}}

===ExpansionFrom smaller graphs===

IfSome <math>G</math>graphs isthat are not themselves locally linear can be used as a framework to construct larger locally linear graphs. One such construction involves [[cubicline graph|3-regular]]s. [[triangle-freeFor any graph]], then<math>G</math>, the [[line graph]] <math>L(G)</math> is a graph formedthat byhas expandinga eachvertex for every edge of <math>G</math>. into a new vertex, and making twoTwo vertices adjacent in <math>L(G)</math> are adjacent when the correspondingtwo edges ofthat they represent in <math>G</math> sharehave a ancommon endpoint. TheseIf graphs<math>G</math> areis a [[cubic graph|3-regular]] [[triangle-free graph]], then its line graph <math>L(G)</math> is 4-regular and locally linear. It has a triangle for every vertex <math>v</math> of <math>G</math>, with the vertices of the triangle corresponding to the three edges incident to <math>v</math>. Every 4-regular locally linear graph can be constructed in this way.{{r|mun}} For instance, the graph of the [[cuboctahedron]] can be formed in this way asis the line graph of a cube, andso it is thelocally linear. The locally linear nine-vertex Paley graph, isconstructed above as a Cartesian product, may also be constructed in a different way as the line graph of the [[utility graph]] <math>K_{3,3}</math>. The line graph of the [[Petersen graph]] is also locally linear by this construction. It has a property analogous to the [[Cage (graph theory)|cages]]: it is the smallest possible graph in which the largest [[Clique (graph theory)|clique]] has three vertices, each vertex is in exactly two edge-disjoint cliques, and the shortest cycle with edges from distinct cliques has length five.{{r|fan}}

The line graph of the [[Petersen graph]], another graph of this type, has a property analogous to the [[Cage (graph theory)|cages]] in that it is the smallest possible graph in which the largest [[Clique (graph theory)|clique]] has three vertices, each vertex is in exactly two edge-disjoint cliques, and the shortest cycle with edges from distinct cliques has length five.{{r|fan}}

[[File:Cuboctahedron.jpgsvg|thumb|The [[cuboctahedron]], a planar locally linear graph that can be formed as the line graph of a cube or by gluing antiprisms onto the inside and outside faces of a 4-cycle]]

A more complicated expansion process applies to [[planar graph]]s.

A more complicated expansion process applies to [[planar graph]]s. Let <math>G</math> be a planar graph embedded in the plane in such a way that every face is a quadrilateral, such as the graph of a cube. Necessarily, if <math>G</math> has <math>n</math> vertices, it has <math>n-2</math> faces. Gluing a [[square antiprism]] onto each face of <math>G</math>, and then deleting the original edges of <math>G</math>, produces a new locally linear planar graph. withThe numbers of edges and vertices of the result can be calculated from [[Euler's polyhedral formula]]: if <math>G</math> has <math>n</math> vertices, it has exactly <math>n-2</math> faces, and the result of replacing the faces of <math>G</math> by antiprisms has <math>5(n-2)+2</math> vertices and <math>12(n-2)</math> edges.{{r|z}} 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.

===Algebraic constructions===

ACertain [[Kneser graph]]s, graphs constructed from the intersection patterns of equal-size sets, are locally linear. Kneser graphs are described by two parameters, the size of the sets they represent and the size of the universe from which these sets are drawn. The Kneser graph <math>KG_K G_{a,b}</math> has <math>\tbinom{a}{b}</math> vertices (in the standard notation for [[binomial coefficient]]s), representing the <math>b</math>-element subsets of an <math>a</math>-element set. TwoIn this graph, two vertices are adjacent when the corresponding subsets are [[disjoint set]]s, having no elements in common. WhenIn the special case when <math>a=3b</math>, the resulting graph is locally linear, because for each two disjoint <math>b</math>-element subsets <math>X</math> and <math>Y</math> there is exactly one other <math>b</math>-element subset (thedisjoint complementfrom both of theirthem, union)consisting of all the elements that isare disjointneither fromin both<math>X</math> ofnor themin <math>Y</math>. The resulting locally linear graph has <math>\tbinom{3b}{b}</math> vertices and <math>\tfrac{1}{2}\tbinom{3b}{b}\tbinom{2b}{b}</math> edges. For instance, for <math>b=2</math> the Kneser graph <math>KG_{6,2}</math> is locally linear with 15 vertices and 45 edges.{{r|lpv}}

Locally linear graphs can also be constructed from progression-free sets of numbers.

Let <math>p</math> be a prime number, and let <math>A</math> be a subset of the numbers modulo <math>p</math> such that no three members of <math>A</math> form an [[arithmetic progression]] modulo <math>p</math>. (That is, <math>A</math> is a [[Salem–Spencer set]] modulo <math>p</math>.) ThenThis thereset existscan abe tripartiteused graphto inconstruct whicha each[[tripartite sidegraph]] of the tripartition haswith <math>p3p</math> vertices, there areand <math>33p\cdot|A|p</math> edges, andthat eachis edgelocally belongs to a unique trianglelinear. To construct this graph, numbermake thethree sets of vertices on, each side of the tripartitionnumbered from <math>0</math> to <math>p-1</math>,. andFor constructeach trianglesnumber of<math>x</math> in the formrange from <math>(x,x+a,x+2a)0</math> moduloto <math>p-1</math> forand each element <math>xa</math> in the range fromof <math>0A</math>, toconstruct a triangle connecting the vertex with number <math>p-1x</math> and eachin the first set of vertices, the vertex with number <math>x+a</math> in the second set of vertices, and the vertex with number <math>Ax+2a</math> in the third set of vertices. TheForm a graph formed fromas the union of all of these triangles. hasBecause theit desiredis propertya thatunion of triangles, every edge of the resulting graph belongs to a unique triangle. For, if notHowever, there wouldcan be ano other triangles than the ones formed in this way. Any other triangle would have vertices numbered <math>(x,x+a,x+a+b)</math> where <math>a</math>, <math>b</math>, and <math>c=(a+b)/2</math> all belong to <math>A</math>, violating the assumption that there be no arithmetic progressions <math>(a,c,b)</math> in <math>A</math>.{{r|rs}} For example, with <math>p=3</math> and <math>A=\{\pm 1\}</math>, the result of this construction is the nine-vertex Paley graph.

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. The locally linear graph itself is the [[Gaifman graph]] of the hypergraph, the graph of pairs of vertices that belong to a common hyperedge. In this view it makes sense to talk about the [[girth (graph theory)|girth]] of the hypergraph. In graph terms, this is the length of the shortest cycle that is not one of the triangles of the graph. An algebraic construction based on [[polarity graph]]s (also called Brown graphs) has been used, in this context, to find dense locally linear graphs that have no 4-cycles; their hypergraph girth is five. A polarity graph is defined from a [[finite projective plane]], and a [[Correlation (projective geometry)|polarity]], an incidence-preserving bijection between its points and its lines. The vertices of the polarity graph are points, and an edge connects two points whenever one is polar to a line containing the other. More algebraically, the vertices of the same graph can be represented by [[homogeneous coordinate]]s: these are triples of values <math>(x,y,z)</math> 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. Two points, represented by triples in this way, are adjacent when their [[inner product]] is zero. The polarity graph for a finite field of odd order <math>q</math> has <math>q^2+q+1</math> vertices, of which <math>q+1</math> are self-adjacent and do not belong to any triangles. When these are removed, the result is a locally linear graph with <math>q^2</math> vertices, <math>\bigl(\tfrac12+o(1)\bigr)q^3</math> edges, and hypergraph girth five, giving the maximum possible number of edges for a locally linear graph of this girth up to lower-order terms.{{r|lv}}

==Regularity==

===Regular graphs with few vertices===

EveryA locallygraph linearis [[regular graph|regular]] mustwhen all of its vertices have eventhe same [[degree (graph theory)|degree]], the number of incident edges. Every locally linear graph must have even degree at each vertex, because the edges at each vertex can be paired up into triangles. 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. Therefore, thereone can take Cartesian products of locally linear graphs of degree two (triangles) to existproduce regular locally linear graphs of every even degree.{{r|f}}

===Regular and strongly regular graphs===

Every locally linear graph must have even [[degree (graph theory)|degree]] at each vertex, because the edges at each vertex can be paired up into triangles. 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. Therefore, there exist regular locally linear graphs of every even degree.{{r|f}}

The <math>2r</math>-regular locally linear graphs must have at least <math>6r-3</math> vertices, because there are this many vertices among any triangle and its neighbors alone. (No two vertices of the triangle can share a neighbor without violating local linearity.) Regular graphs with exactly this many vertices are possible only when <math>r</math> is 1, 2, 3, or 5, and are uniquely defined for each of these four cases. The four regular graphs meeting this bound on the number of vertices are the 3-vertex 2-regular triangle <math>K_3</math>, the 9-vertex 4-regular Paley graph, the 15-vertex 6-regular Kneser graph <math>KG_{6,2}</math>, and the 27-vertex 10-regular [[complement graph]] of the [[Schläfli graph]]. The final 27-vertex 10-regular graph also represents the [[intersection graph]] of the 27 lines on a [[cubic surface]].{{r|lpv}}

===Regular and stronglyStrongly regular graphs===

A [[strongly regular graph]] can be characterized by a quadruple of parameters <math>(n,k,\lambda,\mu)</math> where <math>n</math> is the number of vertices, <math>k</math> is the number of incident edges per vertex, <math>\lambda</math> is the number of shared neighbors for every adjacent pair of vertices, and <math>\mu</math> is the number of shared neighbors for every non-adjacent pair of vertices. When <math>\lambda=1</math> the graph is locally linear. The locally linear graphs already mentioned above that are strongly regular graphs and their parameters are{{r|mak}}

*the triangle (3,2,1,0),

*the nine-vertex Paley graph (9,4,1,2),

Line 47 ⟶ 51:

Other potentially-valid combinations with <math>\lambda=1</math> include (99,14,1,2) and (115,18,1,3) but it is unknown whether strongly regular graphs with those parameters exist.{{r|mak}} The question of the existence of a strongly regular graph with parameters (99,14,1,2) is known as [[Conway's 99-graph problem]], and [[John Horton Conway]] has offered a $1000 prize for its solution.{{r|zd}}

===Distance-regular graphs===

There are finitely many [[distance-regular graph]]s of degree 4 or 6 that are locally linear. Beyond the strongly regular graphs of the same degrees, they also include the line graph of the Petersen graph, the Hamming graph <math>H(3,3)</math>, and the [[Bipartite half|halved]] [[Foster graph]].{{r|hns}}

Line 52 ⟶ 57:

[[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 examples of [[little o notation]], [[big Omega notation]], and [[big O notation]], respectively.){{r|rs}}

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.{{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 thisthe <math>\tfrac{12}{5}(n-2)</math> upper bound iscan be tightattained.{{r|z}}

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. Among the graphs with this property, the least dense are the triangular cactus graphs, which are also the least dense locally linear graphs.{{r|fp}}

==Applications==

One application of locally linear graphs occurs in the formulation of [[Greechie diagram]]s, which are used in [[quantum logic]] to help determine whether certain [[Hilbert space]] equations can be inferred from each other. In this application, the triangles of locally linear graphs form the blocks of Greechie diagrams with block size three. The Greechie diagrams corresponding to lattices come from the locally linear graphs of hypergraph girth five or more,{{r|mmp}} as constructed for instance from polarity graphs.{{r|lv}}

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 [[asymptotic analysis|asymptotically tight]] lower bounds on the [[independence number]] of 3-uniform linear hypergraphs and partial Steiner triple systems.{{r|hy}}

==References==

Line 70 ⟶ 81:

| title = Structure and uniqueness of the (81,20,1,6) strongly regular graph

| volume = 106/107

| year = 1992}}</ref>| doi-access =

}}</ref>

<ref name=br>{{citation

Line 136 ⟶ 148:

| publisher = North-Holland | ___location = Amsterdam

| title = A strongly regular graph derived from the perfect ternary Golay code

| year = 1973| isbn = 9780720422627 | url = https://research.tue.nl/nl/publications/a-strongly-regular-graph-derived-from-the-perfect-ternary-golay-code(10db0cd0-72b4-4d07-bc44-83d07d86e7f0).html }}</ref>

<ref name=f>{{citation

Line 159 ⟶ 171:

| volume = 23

| year = 1996}}</ref>

<ref name=fp>{{citation

| last1 = Farley | first1 = Arthur M.

| last2 = Proskurowski | first2 = Andrzej

| doi = 10.1002/net.3230120404

| issue = 4

| journal = Networks

| mr = 686540

| pages = 393–403

| title = Networks immune to isolated line failures

| volume = 12

| year = 1982}}; see in particular p. 397: "We call the resultant network a triangle cactus; it is a cactus network in which every line belongs to exactly one triangle."</ref>

<ref name=hns>{{citation

Line 173 ⟶ 197:

| year = 2000| doi-access = free

}}</ref>

<ref name=hy>{{citation

| last1 = Henning | first1 = Michael A.

| last2 = Yeo | first2 = Anders

| contribution = Chapter 12: Partial Steiner triple systems

| doi = 10.1007/978-3-030-46559-9_12

| isbn = 978-3-030-46559-9

| mr = 4180641

| pages = 171–177

| publisher = Springer | ___location = Cham

| series = Developments in Mathematics

| title = Transversals in Linear Uniform Hypergraphs

| volume = 63

| year = 2020}}</ref>

<ref name=lpv>{{citation

Line 185 ⟶ 223:

| volume = 102

| year = 2011}}</ref>

<ref name=lv>{{citation

| last1 = Lazebnik | first1 = Felix

| last2 = Verstraëte | first2 = Jacques

| doi = 10.37236/1718 | doi-access = free

| journal = [[Electronic Journal of Combinatorics]]

| mr = 2014512

| page = R25:1–R25:15

| title = On hypergraphs of girth five

| volume = 10

| year = 2003}}</ref>

<ref name=mak>{{citation

Line 196 ⟶ 245:

| volume = 44

| year = 1988| s2cid = 120911900

}}</ref>

<ref name=mmp>{{citation

| last1 = McKay | first1 = Brendan D. | author1-link = Brendan McKay (mathematician)

| last2 = Megill | first2 = Norman D.

| last3 = Pavičić | first3 = Mladen

| doi = 10.1023/A:1026476701774

| issue = 10

| journal = International Journal of Theoretical Physics

| mr = 1803695

| pages = 2381–2406

| title = Algorithms for Greechie diagrams

| volume = 39

| year = 2000| arxiv = quant-ph/0009039

}}</ref>

Line 208 ⟶ 271:

| volume = 340

| year = 2017| url = https://pure.qub.ac.uk/en/publications/on-line-graphs-of-subcubic-trianglefree-graphs(aa6963d5-59e6-4d92-a9d6-d89d4374396c).html

| doi-access = free

}}</ref>

Line 235 ⟶ 299:

<ref name=zd>{{citation

| last1 = Zehavi | first1 = Sa'ar

| last2 = David de OliveraOliveira | first2 = Ivo Fagundes David

| arxiv = 1707.08047

| title = Not Conway's 99-graph problem