Locally linear graph: Difference between revisions

Revision as of 02:07, 18 May 2023

Latest revision as of 10:33, 14 July 2025

(12 intermediate revisions by 4 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 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, solocally (from the neighborspoint canof beview pairedof upany intoone anvertex) the rest of the graph looks like a [[inducedperfect matching]].{{r|f}} Locally linear graphs have also been called locally matched graphs.{{r|lpv}} TheyMore aretechnically, exactlythe triangles of any locally linear graph form the [[Gaifman graphhyperedge]]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.

Line 20:

Some graphs that are not themselves locally linear can be used as a framework to construct larger locally linear graphs. One such construction involves [[line graph]]s. For any graph <math>G</math>, the line graph <math>L(G)</math> is a graph that has a vertex for every edge of <math>G</math>. Two vertices in <math>L(G)</math> are adjacent when the two edges that they represent in <math>G</math> have a common endpoint. If <math>G</math> is 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]] is the line graph of a cube, so it is locally linear. The locally linear nine-vertex Paley graph, constructed 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}}

[[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. 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. 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. The 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===

Certain [[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. In this graph, two vertices are adjacent when the corresponding subsets are [[disjoint set]]s, having no elements in common. In 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 disjoint from both of them, consisting of all the elements that are neither in <math>X</math> nor in <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.

Line 65:

==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 79 ⟶ 81:

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

| volume = 106/107

| year = 1992| doi-access = free

}}</ref>

Line 195 ⟶ 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 242 ⟶ 258:

| title = Algorithms for Greechie diagrams

| volume = 39

| year = 2000}}<| arxiv = quant-ph/ref>0009039

}}</ref>

<ref name=mun>{{citation