Locally linear graph: Difference between revisions

Revision as of 02:06, 18 May 2023

Revision as of 02:07, 18 May 2023

Line 30:

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>.) This set can be used to construct a [[tripartite graph]] with <math>3p</math> vertices and <math>3p\cdot|A|</math> edges that is locally linear. To construct this graph, make three sets of vertices, each numbered from <math>0</math> to <math>p-1</math>. For each number <math>x</math> in the range from <math>0</math> to <math>p-1</math> and each element <math>a</math> of <math>A</math>, construct a triangle connecting the vertex with number <math>x</math> in 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>x+2a</math> in the third set of vertices. Form a graph as the union of all of these triangles. Because it is a union of triangles, every edge of the resulting graph belongs to a triangle. However, there can be no 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, andmeaning 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. inIn 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==