Content deleted Content added
m Open access bot: add arxiv identifier to citation with #oabot. |
→Algebraic constructions: fix link |
||
Line 29:
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>.) Then there exists a tripartite graph in which each side of the tripartition has <math>p</math> vertices, there are <math>3|A|p</math> edges, and each edge belongs to a unique triangle. Thus, with this construction, <math>n=3p</math> and the number of edges is <math>n^2/e^{O(\sqrt{\log n})}</math>. To construct this graph, number the vertices on each side of the tripartition from <math>0</math> to <math>p-1</math>, and construct triangles of the form <math>(x,x+a,x+2a)</math> modulo <math>p</math> for each <math>x</math> in the range from <math>0</math> to <math>p-1</math> and each <math>a</math> in <math>A</math>. The graph formed from the union of these triangles has the desired property that every edge belongs to a unique triangle. For, if not, there would be a triangle <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 is the nine-vertex Paley graph.
===Regular and strongly regular graphs===
| |||