|
===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_{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. WhenFor parameters that obey the equation <math>a=3b</math>, the resulting graph is locally linear, because for each two disjoint <math>b</math>-element subsets there is exactly one other <math>b</math>-element subset (the complement of their union) that is disjoint from both of them. 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>3|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>, and construct triangles using one vertex from each of the formthree sets that connect vertices numbered <math>(x,x+a,x+2a)</math> modulo <math>p</math>, for eachwhere <math>x</math> is any number in the range from <math>0</math> to <math>p-1</math> and each <math>a</math> inis any element of <math>A</math>. TheBy graphconstruction, formedevery fromedge of the unionresulting ofgraph thesebelongs trianglesto hasa thetriangle, desiredbut propertythere thatcan everybe edgeno belongsother totriangles athan uniquethe triangle.ones For,formed ifin not,this thereway. Any other triangle would behave avertices trianglenumbered <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.
===Regular and strongly regular graphs===
|
