The characterization of maximum complete and empty subgraphs in the quadrance graph

From papers

Let FqF_q be the finite field with qq elements, and let VqV_q be the graph on Fq×FqF_q\times F_q whose adjacency is determined by the quadrance relation used in the paper. For a subset UVqU\subseteq V_q, say that UU spans a complete subgraph or an empty subgraph according as every pair of vertices in UU is adjacent or no pair is adjacent.

Maximum subgraph conjecture. If UU spans a complete subgraph or an empty subgraph of order qq in VqV_q, then UU is a line in Fq×FqF_q\times F_q.

The preceding bound shows that a complete or empty subgraph of this type has at most qq vertices, and equality is attained by the qq points on a line. Computations for q=3q=3 and q=7q=7 support the conjectured converse.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Le Anh Vinh, “Quadrance polygons, association schemes and strongly regular graphs”, arXiv:math/0509598 (2005).

Solutions 0

No solutions have been posted yet.