Graphs defined by systems of equations

This module implements a class of bipartite graphs defined by triangular systems of equations, popularized by Lazebnik, Ustimenko, and Woldar. More precisely, let \(R\) be a finite commutative ring. The graph has point part \(P = R^n\) and line part \(L = R^n\). For \(2 \leq i \leq n\), let \(f_i\) be a polynomial function in \(2i - 2\) variables. A point \((p_1, p_2, \ldots, p_n)\) is adjacent to a line \((l_1, l_2, \ldots, l_n)\) if

\[p_i + l_i = f_i(p_1, l_1, \ldots, p_{i-1}, l_{i-1}), \qquad 2 \leq i \leq n.\]

The class LUWGraphDescriptor stores a validated set of equations which define the graph. This lets users experiment with large examples without paying the cost of building the full graph. Currently, the descriptor-returning constructors are define_luw_graph(), define_Akq(), define_Dkq(), and define_WengerGraph(). The graph-returning constructors Akq(), Dkq(), LUWGraph(), and WengerGraph() are exposed through sage.graphs.graph_generators, and so are available as graphs.LUWGraph(...), graphs.WengerGraph(...), and so on.

The general construction and the graph families implemented here are surveyed in [LW2026].

EXAMPLES:

The graph constructor is available directly from graphs:

sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
sage: p1, l1, p2, l2 = R.gens()
sage: G = graphs.LUWGraph(F, [p1*l1, p1*l2])
sage: G.order(), G.size(), G.girth()
(54, 81, 8)

>>> from sage.all import *
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
>>> p1, l1, p2, l2 = R.gens()
>>> G = graphs.LUWGraph(F, [p1*l1, p1*l2])
>>> G.order(), G.size(), G.girth()
(54, 81, 8)

Use define_luw_graph() when the algebraic description should be kept as a LUWGraphDescriptor without immediately constructing the full graph.

AUTHORS:

  • Vladislav Taranchuk (2026-04): initial version

sage.graphs.generators.luw_graphs.Akq(k, q, A=None, B=None, immutable=False)[source]

Return the graph \(A(k, q)\) described in [LW2026].

The point set and line set are \(\GF{q}^k\). A point \((p_1, \ldots, p_k)\) is adjacent to a line \((l_1, \ldots, l_k)\) if

\[\begin{split}p_i + l_i = \begin{cases} p_{i-1} l_1, & i \text{ even},\\ p_1 l_{i-1}, & i \text{ odd}, \end{cases} \qquad 2 \leq i \leq k.\end{split}\]

INPUT:

  • k – integer at least \(2\)

  • q – prime power

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph

OUTPUT:

A Sage Graph.

EXAMPLES:

sage: G = graphs.Akq(5, 3)
sage: G.order(), G.size(), G.girth()
(486, 729, 12)

>>> from sage.all import *
>>> G = graphs.Akq(Integer(5), Integer(3))
>>> G.order(), G.size(), G.girth()
(486, 729, 12)

REFERENCES:

sage.graphs.generators.luw_graphs.Dkq(k, q, A=None, B=None, immutable=False)[source]

Return the graph \(D(k, q)\) described in [LW2026].

The point set and line set are \(\GF{q}^k\). A point \((p_1, \ldots, p_k)\) is adjacent to a line \((l_1, \ldots, l_k)\) if

\[p_2 + l_2 = p_1 l_1,\]

and, when \(k \geq 3\),

\[p_3 + l_3 = p_1 l_2.\]

For \(4 \leq i \leq k\), the remaining equations are

\[\begin{split}p_i + l_i = \begin{cases} p_{i-2} l_1, & i \equiv 0, 1 \pmod 4,\\ p_1 l_{i-2}, & i \equiv 2, 3 \pmod 4. \end{cases}\end{split}\]

INPUT:

  • k – integer at least \(2\)

  • q – prime power

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph

OUTPUT:

A Sage Graph.

EXAMPLES:

sage: G = graphs.Dkq(5, 3)
sage: G.order(), G.size(), G.girth()
(486, 729, 12)

>>> from sage.all import *
>>> G = graphs.Dkq(Integer(5), Integer(3))
>>> G.order(), G.size(), G.girth()
(486, 729, 12)

REFERENCES:

sage.graphs.generators.luw_graphs.LUWGraph(ring, equations, name=None, A=None, B=None, point_coordinate_sets=None, line_coordinate_sets=None, immutable=False)[source]

Build a graph directly from a given set of equations.

This is the graph-returning constructor used by graphs.LUWGraph. The construction is surveyed in [LW2026].

INPUT:

  • ring – finite commutative ring

  • equations – nonempty iterable of Sage polynomials

  • name – string (default: None); graph name

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

  • point_coordinate_sets – iterable of coordinate sets or None (default: None)

  • line_coordinate_sets – iterable of coordinate sets or None (default: None)

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph

OUTPUT:

A Sage Graph.

EXAMPLES:

sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1", "p2", "l2", "p3", "l3"))
sage: p1, l1, p2, l2, p3, l3 = R.gens()
sage: G = graphs.LUWGraph(F, [p1*l1, p1*l2, p3*l1])
sage: G.order(), G.size()
(162, 243)

>>> from sage.all import *
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1", "p2", "l2", "p3", "l3"))
>>> p1, l1, p2, l2, p3, l3 = R.gens()
>>> G = graphs.LUWGraph(F, [p1*l1, p1*l2, p3*l1])
>>> G.order(), G.size()
(162, 243)

REFERENCES:

class sage.graphs.generators.luw_graphs.LUWGraphDescriptor(ring, equations, name, point_coordinate_sets, line_coordinate_sets)[source]

Bases: object

A validated algebraic description of a bipartite graph.

The graph itself is built from the stored equations and coordinate sets. See [LW2026] for a survey of these graphs.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(5)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: D = define_luw_graph(F, [p1*l1])
sage: D.order()
50
sage: D.size()
125

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(5))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> D = define_luw_graph(F, [p1*l1])
>>> D.order()
50
>>> D.size()
125

REFERENCES:

adjacency_matrix(vertices=None)[source]

Return the adjacency matrix without first constructing the graph.

INPUT:

  • vertices – list, tuple, or None (default: None); vertex order

When vertices is None, the vertex order agrees with Sage’s default graph adjacency-matrix order, namely sorted vertex labels.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
sage: p1, l1, p2, l2 = R.gens()
sage: D = define_luw_graph(F, [p1*l1, p1*l2 + p2])
sage: D.adjacency_matrix().dimensions()
(54, 54)
sage: D.adjacency_matrix() == D.graph().adjacency_matrix()
True

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
>>> p1, l1, p2, l2 = R.gens()
>>> D = define_luw_graph(F, [p1*l1, p1*l2 + p2])
>>> D.adjacency_matrix().dimensions()
(54, 54)
>>> D.adjacency_matrix() == D.graph().adjacency_matrix()
True

A custom vertex order can also be supplied:

sage: vertices = list(D.graph().vertices(sort=False))
sage: D.adjacency_matrix(vertices=vertices) == \
....:     D.graph().adjacency_matrix(vertices=vertices)
True
[Python] 
>>> from sage.all import *
>>> vertices = list(D.graph().vertices(sort=False))
>>> D.adjacency_matrix(vertices=vertices) ==     D.graph().adjacency_matrix(vertices=vertices)
True
ball(start_vertex, depth, immutable=False)[source]

Build the ball of radius depth around start_vertex.

The construction stops early if a new layer adds no vertices.

INPUT:

  • start_vertex – pair (side, coordinates) where side is either "P" or "L"

  • depth – nonnegative integer; radius of the ball

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: D = define_luw_graph(F, [p1*l1])
sage: B = D.ball(("P", (0, 0)), 1)
sage: B.order(), B.size()
(4, 3)
sage: D.ball(("P", (0, 0)), 1, immutable=True).is_immutable()
True
sage: D = define_luw_graph(F, [p1*l1], A=[0], B=[0])
sage: B = D.ball(("P", (0, 0)), 5)
sage: B.order(), B._luw_graph_ball_metadata["component_recovered"]
(2, True)

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> D = define_luw_graph(F, [p1*l1])
>>> B = D.ball(("P", (Integer(0), Integer(0))), Integer(1))
>>> B.order(), B.size()
(4, 3)
>>> D.ball(("P", (Integer(0), Integer(0))), Integer(1), immutable=True).is_immutable()
True
>>> D = define_luw_graph(F, [p1*l1], A=[Integer(0)], B=[Integer(0)])
>>> B = D.ball(("P", (Integer(0), Integer(0))), Integer(5))
>>> B.order(), B._luw_graph_ball_metadata["component_recovered"]
(2, True)
base_ring()[source]

Return the underlying finite ring.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: Z4 = Integers(4)
sage: R = PolynomialRing(Z4, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(Z4, [p1*l1]).base_ring()
Ring of integers modulo 4

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> Z4 = Integers(Integer(4))
>>> R = PolynomialRing(Z4, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(Z4, [p1*l1]).base_ring()
Ring of integers modulo 4
dimension()[source]

Return the number of point or line coordinates.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1]).dimension()
2

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1]).dimension()
2
equations()[source]

Return the validated defining polynomials.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_Akq
sage: define_Akq(3, 3).equations()
(p1*l1, p1*l2)

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_Akq
>>> define_Akq(Integer(3), Integer(3)).equations()
(p1*l1, p1*l2)
graph(immutable=False)[source]

Build the full graph corresponding to self.

INPUT:

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_WengerGraph
sage: G = define_WengerGraph(2, 3).graph()
sage: G.order(), G.size()
(54, 81)
sage: define_WengerGraph(2, 3).graph(immutable=True).is_immutable()
True

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_WengerGraph
>>> G = define_WengerGraph(Integer(2), Integer(3)).graph()
>>> G.order(), G.size()
(54, 81)
>>> define_WengerGraph(Integer(2), Integer(3)).graph(immutable=True).is_immutable()
True
lift(new_functions, name=None)[source]

Return the lifted algebraic definition obtained by appending equations.

INPUT:

  • new_functions – iterable of Sage polynomials to append

  • name – string (default: None); name of the new definition

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
sage: p1, l1, p2, l2 = R.gens()
sage: D = define_luw_graph(F, [p1*l1])
sage: D2 = D.lift([p1*l2])
sage: D2.equations()
(p1*l1, p1*l2)

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
>>> p1, l1, p2, l2 = R.gens()
>>> D = define_luw_graph(F, [p1*l1])
>>> D2 = D.lift([p1*l2])
>>> D2.equations()
(p1*l1, p1*l2)
line_count()[source]

Return the number of line vertices.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1], B=[1, 2]).line_count()
6

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1], B=[Integer(1), Integer(2)]).line_count()
6
line_first_coordinates()[source]

Return the allowed first coordinates on the line side.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1], B=[1, 2]).line_first_coordinates()
(1, 2)

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1], B=[Integer(1), Integer(2)]).line_first_coordinates()
(1, 2)
neighbors(vertex)[source]

Return the neighbors of vertex without building the full graph.

INPUT:

  • vertex – pair (side, coordinates) where side is either "P" or "L"

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: D = define_luw_graph(F, [p1*l1])
sage: v = ("P", (F(0), F(0)))
sage: D.neighbors(v)
(('L', (0, 0)), ('L', (1, 0)), ('L', (2, 0)))
sage: G = D.graph()
sage: set(D.neighbors(v)) == set(G.neighbors(v))
True

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> D = define_luw_graph(F, [p1*l1])
>>> v = ("P", (F(Integer(0)), F(Integer(0))))
>>> D.neighbors(v)
(('L', (0, 0)), ('L', (1, 0)), ('L', (2, 0)))
>>> G = D.graph()
>>> set(D.neighbors(v)) == set(G.neighbors(v))
True
order()[source]

Return the number of vertices of the graph.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1]).order()
18

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1]).order()
18
point_count()[source]

Return the number of point vertices.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1], A=[0, 1]).point_count()
6

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1], A=[Integer(0), Integer(1)]).point_count()
6
point_first_coordinates()[source]

Return the allowed first coordinates on the point side.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1], A=[0, 1]).point_first_coordinates()
(0, 1)

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1], A=[Integer(0), Integer(1)]).point_first_coordinates()
(0, 1)
project_down(x, name=None)[source]

Return the projection down obtained by removing the last x equations.

INPUT:

  • x – positive integer; number of final equations to remove

  • name – string (default: None); name of the new definition

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
sage: p1, l1, p2, l2 = R.gens()
sage: D = define_luw_graph(F, [p1*l1, p1*l2])
sage: D.project_down(1).equations()
(p1*l1,)

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
>>> p1, l1, p2, l2 = R.gens()
>>> D = define_luw_graph(F, [p1*l1, p1*l2])
>>> D.project_down(Integer(1)).equations()
(p1*l1,)
size()[source]

Return the number of edges of the graph.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(F, [p1*l1]).size()
27

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(F, [p1*l1]).size()
27
sage.graphs.generators.luw_graphs.WengerGraph(m, q, A=None, B=None, immutable=False)[source]

Return the Wenger graph \(W_m(q)\) described in [LW2026].

The point set and line set are \(\GF{q}^{m+1}\). A point \((p_1, \ldots, p_{m+1})\) is adjacent to a line \((l_1, \ldots, l_{m+1})\) if

\[p_{i+1} + l_{i+1} = p_1 l_i, \qquad 1 \leq i \leq m.\]

INPUT:

  • m – positive integer

  • q – prime power

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph

OUTPUT:

A Sage Graph.

EXAMPLES:

sage: G = graphs.WengerGraph(2, 3)
sage: G.order(), G.size()
(54, 81)

>>> from sage.all import *
>>> G = graphs.WengerGraph(Integer(2), Integer(3))
>>> G.order(), G.size()
(54, 81)

REFERENCES:

sage.graphs.generators.luw_graphs.define_Akq(k, q, A=None, B=None)[source]

Return a descriptor for the graph \(A(k, q)\) described in [LW2026].

The point set and line set are \(\GF{q}^k\). A point \((p_1, \ldots, p_k)\) is adjacent to a line \((l_1, \ldots, l_k)\) if

\[\begin{split}p_i + l_i = \begin{cases} p_{i-1} l_1, & i \text{ even},\\ p_1 l_{i-1}, & i \text{ odd}, \end{cases} \qquad 2 \leq i \leq k.\end{split}\]

INPUT:

  • k – integer at least \(2\)

  • q – prime power

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

OUTPUT:

A LUWGraphDescriptor.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_Akq
sage: D = define_Akq(5, 3)
sage: D.dimension(), D.order(), D.size()
(5, 486, 729)
sage: D.graph().order()
486

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_Akq
>>> D = define_Akq(Integer(5), Integer(3))
>>> D.dimension(), D.order(), D.size()
(5, 486, 729)
>>> D.graph().order()
486

REFERENCES:

sage.graphs.generators.luw_graphs.define_Dkq(k, q, A=None, B=None)[source]

Return a descriptor for the graph \(D(k, q)\) described in [LW2026].

The point set and line set are \(\GF{q}^k\). A point \((p_1, \ldots, p_k)\) is adjacent to a line \((l_1, \ldots, l_k)\) if

\[p_2 + l_2 = p_1 l_1,\]

and, when \(k \geq 3\),

\[p_3 + l_3 = p_1 l_2.\]

For \(4 \leq i \leq k\), the remaining equations are

\[\begin{split}p_i + l_i = \begin{cases} p_{i-2} l_1, & i \equiv 0, 1 \pmod 4,\\ p_1 l_{i-2}, & i \equiv 2, 3 \pmod 4. \end{cases}\end{split}\]

INPUT:

  • k – integer at least \(2\)

  • q – prime power

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

OUTPUT:

A LUWGraphDescriptor.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_Dkq
sage: D = define_Dkq(5, 3)
sage: D.dimension(), D.order(), D.size()
(5, 486, 729)
sage: D.graph().size()
729

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_Dkq
>>> D = define_Dkq(Integer(5), Integer(3))
>>> D.dimension(), D.order(), D.size()
(5, 486, 729)
>>> D.graph().size()
729

REFERENCES:

sage.graphs.generators.luw_graphs.define_WengerGraph(m, q, A=None, B=None)[source]

Return a descriptor for the Wenger graph \(W_m(q)\) described in [LW2026].

The point set and line set are \(\GF{q}^{m+1}\). A point \((p_1, \ldots, p_{m+1})\) is adjacent to a line \((l_1, \ldots, l_{m+1})\) if

\[p_{i+1} + l_{i+1} = p_1 l_i, \qquad 1 \leq i \leq m.\]

INPUT:

  • m – positive integer

  • q – prime power

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

OUTPUT:

A LUWGraphDescriptor.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_WengerGraph
sage: D = define_WengerGraph(2, 3)
sage: D.dimension(), D.order(), D.size()
(3, 54, 81)
sage: D.graph().order()
54

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_WengerGraph
>>> D = define_WengerGraph(Integer(2), Integer(3))
>>> D.dimension(), D.order(), D.size()
(3, 54, 81)
>>> D.graph().order()
54

REFERENCES:

sage.graphs.generators.luw_graphs.define_luw_graph(ring, equations, name=None, A=None, B=None, point_coordinate_sets=None, line_coordinate_sets=None)[source]

Return a validated algebraic descriptor for an LUW graph.

The general construction is surveyed in [LW2026].

INPUT:

  • ring – finite commutative ring

  • equations – nonempty iterable of Sage polynomials

    The polynomial variables are interpreted by their Sage generator names. Users should label Python variables in the same order as the polynomial ring generators, or bind them by name, for example with R.gens_dict(). If p1 is accidentally bound to the generator named p2, the polynomial will be interpreted as using p2.

  • name – string (default: None); name for the resulting definition

  • A – iterable, single value, or None (default: None); allowed first coordinates on the point side

  • B – iterable, single value, or None (default: None); allowed first coordinates on the line side

  • point_coordinate_sets – iterable of coordinate sets or None (default: None)

  • line_coordinate_sets – iterable of coordinate sets or None (default: None)

OUTPUT:

A LUWGraphDescriptor.

EXAMPLES:

sage: from sage.graphs.generators.luw_graphs import define_luw_graph
sage: F = GF(3)
sage: R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
sage: p1, l1, p2, l2 = R.gens()
sage: D = define_luw_graph(F, [p1*l1, p1*l2], A=[0, 1], B=[1, 2])
sage: D.point_first_coordinates()
(0, 1)
sage: D.line_first_coordinates()
(1, 2)
sage: Z4 = Integers(4)
sage: R = PolynomialRing(Z4, names=("p1", "l1"))
sage: p1, l1 = R.gens()
sage: define_luw_graph(Z4, [p1*l1]).order()
32

>>> from sage.all import *
>>> from sage.graphs.generators.luw_graphs import define_luw_graph
>>> F = GF(Integer(3))
>>> R = PolynomialRing(F, names=("p1", "l1", "p2", "l2"))
>>> p1, l1, p2, l2 = R.gens()
>>> D = define_luw_graph(F, [p1*l1, p1*l2], A=[Integer(0), Integer(1)], B=[Integer(1), Integer(2)])
>>> D.point_first_coordinates()
(0, 1)
>>> D.line_first_coordinates()
(1, 2)
>>> Z4 = Integers(Integer(4))
>>> R = PolynomialRing(Z4, names=("p1", "l1"))
>>> p1, l1 = R.gens()
>>> define_luw_graph(Z4, [p1*l1]).order()
32

REFERENCES: