Two-graphs#

A two-graph on \(n\) points is a family \(T \subset \binom {[n]}{3}\) of \(3\)-sets, such that any \(4\)-set \(S\subset [n]\) of size four contains an even number of elements of \(T\). Any graph \(([n],E)\) gives rise to a two-graph \(T(E)=\{t \in \binom {[n]}{3} : \left| \binom {t}{2} \cap E \right|\ odd \}\), and any two graphs with the same two-graph can be obtained one from the other by Seidel switching. This defines an equivalence relation on the graphs on \([n]\), called Seidel switching equivalence. Conversely, given a two-graph \(T\), one can construct a graph \(\Gamma\) in the corresponding Seidel switching class with an isolated vertex \(w\). The graph \(\Gamma \setminus w\) is called the descendant of \(T\) w.r.t. \(v\).

\(T\) is called regular if each two-subset of \([n]\) is contained in the same number alpha of triples of \(T\).

This module implements a direct construction of a two-graph from a list of triples, construction of descendant graphs, regularity checking, and other things such as constructing the complement two-graph, cf. [BH2012].

AUTHORS:

Dima Pasechnik (Aug 2015)

Index#

This module’s methods are the following:

`is_regular_twograph()`	tests if `self` is a regular two-graph, i.e. a 2-design
`complement()`	returns the complement of `self`
`descendant()`	returns the descendant graph at \(w\)

This module’s functions are the following:

`taylor_twograph()`	constructs Taylor’s two-graph for \(U_3(q)\)
`is_twograph()`	checks that the incidence system is a two-graph
`twograph_descendant()`	returns the descendant graph w.r.t. a given vertex of the two-graph of a given graph

Methods#

class sage.combinat.designs.twographs.TwoGraph(points=None, blocks=None, incidence_matrix=None, name=None, check=False, copy=True)#

Bases: IncidenceStructure

Two-graphs class.

A two-graph on \(n\) points is a 3-uniform hypergraph, i.e. a family \(T \subset \binom {[n]}{3}\) of \(3\)-sets, such that any \(4\)-set \(S\subset [n]\) of size four contains an even number of elements of \(T\). For more information, see the documentation of the twographs module.

complement()#

The two-graph which is the complement of self

That is, the two-graph consisting exactly of triples not in self. Note that this is different from complement of the parent class.

EXAMPLES:

sage: p = graphs.CompleteGraph(8).line_graph().twograph()                   # needs sage.modules
sage: pc = p.complement(); pc                                               # needs sage.modules
Incidence structure with 28 points and 1260 blocks

descendant(v)#

The descendant graph at v

The switching class of graphs corresponding to self contains a graph D with v its own connected component; removing v from D, one obtains the descendant graph of self at v, which is constructed by this method.

INPUT:

v – an element of ground_set()

EXAMPLES:

sage: p = graphs.PetersenGraph().twograph().descendant(0)                   # needs sage.modules
sage: p.is_strongly_regular(parameters=True)                                # needs sage.modules
(9, 4, 1, 2)

is_regular_twograph(alpha=False)#

Test if the TwoGraph is regular, i.e. is a 2-design.

Namely, each pair of elements of ground_set() is contained in exactly alpha triples.

INPUT:

alpha – (optional, default is False) return the value of alpha, if possible.

EXAMPLES:

sage: # needs sage.modules
sage: p = graphs.PetersenGraph().twograph()
sage: p.is_regular_twograph(alpha=True)
4
sage: p.is_regular_twograph()
True
sage: p = graphs.PathGraph(5).twograph()
sage: p.is_regular_twograph(alpha=True)
False
sage: p.is_regular_twograph()
False

sage.combinat.designs.twographs.is_twograph(T)#

Checks that the incidence system \(T\) is a two-graph

INPUT:

T – an incidence structure

EXAMPLES:

a two-graph from a graph:

sage: from sage.combinat.designs.twographs import (is_twograph, TwoGraph)
sage: p = graphs.PetersenGraph().twograph()                                     # needs sage.modules
sage: is_twograph(p)                                                            # needs sage.modules
True

a non-regular 2-uniform hypergraph which is a two-graph:

sage: is_twograph(TwoGraph([[1,2,3],[1,2,4]]))
True

sage.combinat.designs.twographs.taylor_twograph(q)#

constructing Taylor’s two-graph for \(U_3(q)\), \(q\) odd prime power

The Taylor’s two-graph \(T\) has the \(q^3+1\) points of the projective plane over \(F_{q^2}\) singular w.r.t. the non-degenerate Hermitean form \(S\) preserved by \(U_3(q)\) as its ground set; the triples are \(\{x,y,z\}\) satisfying the condition that \(S(x,y)S(y,z)S(z,x)\) is square (respectively non-square) if \(q \cong 1 \mod 4\) (respectively if \(q \cong 3 \mod 4\)). See §7E of [BL1984].

There is also a \(2-(q^3+1,q+1,1)\)-design on these \(q^3+1\) points, known as the unital of order \(q\), also invariant under \(U_3(q)\).

INPUT:

q – a power of an odd prime

EXAMPLES:

sage: from sage.combinat.designs.twographs import taylor_twograph
sage: T = taylor_twograph(3); T                                                 # needs sage.rings.finite_rings
Incidence structure with 28 points and 1260 blocks

sage.combinat.designs.twographs.twograph_descendant(G, v, name=None)#

Return the descendant graph w.r.t. vertex \(v\) of the two-graph of \(G\)

In the switching class of \(G\), construct a graph \(\Delta\) with \(v\) an isolated vertex, and return the subgraph \(\Delta \setminus v\). It is equivalent to, although much faster than, computing the TwoGraph.descendant() of two-graph of G, as the intermediate two-graph is not constructed.

INPUT:

G – a graph
v – a vertex of G
name – (optional) None - no name, otherwise derive from the construction

EXAMPLES:

one of s.r.g.’s from the database:

sage: from sage.combinat.designs.twographs import twograph_descendant
sage: A = graphs.strongly_regular_graph(280,135,70)                   # optional - gap_package_design internet
sage: twograph_descendant(A, 0).is_strongly_regular(parameters=True)  # optional - gap_package_design internet
(279, 150, 85, 75)