An Erdős–Diophantine graph is an object in the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
subject of
Diophantine equations
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates t ...
consisting of a set of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
points at integer distances in the plane that cannot be extended by any additional points. Equivalently, in
geometric graph theory
Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geome ...
, it can be described as a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
with
vertices located on the
integer square grid such that all mutual
distances
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
between the vertices are integers, while all other grid points have a non-integer distance to at least one vertex.
Erdős–Diophantine graphs are named after
Paul Erdős and
Diophantus of Alexandria
Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandrian mathematician, who was the aut ...
. They form a subset of the set of Diophantine figures, which are defined as complete graphs in the Diophantine plane for which the length of all edges are integers (
unit distance graph
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these gr ...
s). Thus, Erdős–Diophantine graphs are exactly the Diophantine figures that cannot be extended. The existence of Erdős–Diophantine graphs follows from the
Erdős–Anning theorem, according to which infinite Diophantine figures must be collinear in the Diophantine plane. Hence, any process of extending a non-collinear Diophantine figure by adding vertices must eventually reach a figure that can no longer be extended.
Examples
Any set of zero or one point can be trivially extended, and any Diophantine set of two points can be extended by more points on the same line. Therefore, all Diophantine sets with fewer than three nodes can be extended, so Erdős–Diophantine graphs on fewer than three nodes cannot exist.
By numerical search, have shown that three-node Erdős–Diophantine graphs do exist. The smallest Erdős–Diophantine triangle is characterised by edge lengths 2066, 1803, and 505. The next larger Erdős–Diophantine triangle has edges 2549, 2307 and 1492. In both cases, the sum of the three edge-lengths is even. Brancheva has proven that this property holds for all Erdős–Diophantine triangles. More generally, the total length of any closed path in an Erdős–Diophantine graph is always even.
An example of a 4-node Erdős–Diophantine graph is provided by the complete graph formed by the four nodes located on the vertices of a rectangle with sides 4 and 3.
References
*
*
{{DEFAULTSORT:Erdos-Diophantine graph
Diophantine graph
Diophantine equations
Algebraic geometry
Discrete geometry
Geometric graphs
Arithmetic problems of plane geometry