Twographs¶
A twograph 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 twograph
\(T(E)=\{t \in \binom {[n]}{3} : \left \binom {t}{2} \cap E \right\ odd \}\),
and any two graphs with the same twograph 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 twograph \(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 twosubset of \([n]\) is contained in the same number alpha of triples of \(T\).
This module implements a direct construction of a twograph from a list of triples, construction of descendant graphs, regularity checking, and other things such as constructing the complement twograph, cf. [BH2012].
AUTHORS:
Dima Pasechnik (Aug 2015)
Index¶
This module’s methods are the following:
tests if 

returns the complement of 

returns the descendant graph at \(w\) 
This module’s functions are the following:
constructs Taylor’s twograph for \(U_3(q)\) 

checks that the incidence system is a twograph 

returns the descendant graph w.r.t. a given vertex of the twograph 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:
sage.combinat.designs.incidence_structures.IncidenceStructure
Twographs class.
A twograph on \(n\) points is a 3uniform 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 twograph which is the complement of
self
That is, the twograph consisting exactly of triples not in
self
. Note that this is different fromcomplement
of theparent class
.EXAMPLES:
sage: p = graphs.CompleteGraph(8).line_graph().twograph() sage: pc = p.complement(); pc Incidence structure with 28 points and 1260 blocks

descendant
(v)¶ The descendant
graph
atv
The
switching class of graphs
corresponding toself
contains a graphD
withv
its own connected component; removingv
fromD
, one obtains the descendant graph ofself
atv
, which is constructed by this method.INPUT:
v
– an element ofground_set()
EXAMPLES:
sage: p = graphs.PetersenGraph().twograph().descendant(0) sage: p.is_strongly_regular(parameters=True) (9, 4, 1, 2)

is_regular_twograph
(alpha=False)¶ Test if the
TwoGraph
is regular, i.e. is a 2design.Namely, each pair of elements of
ground_set()
is contained in exactlyalpha
triples.INPUT:
alpha
– (optional, default isFalse
) return the value ofalpha
, if possible.
EXAMPLES:
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 twograph
INPUT:
T
– anincidence structure
EXAMPLES:
a twograph from a graph:
sage: from sage.combinat.designs.twographs import (is_twograph, TwoGraph) sage: p=graphs.PetersenGraph().twograph() sage: is_twograph(p) True
a nonregular 2uniform hypergraph which is a twograph:
sage: is_twograph(TwoGraph([[1,2,3],[1,2,4]])) True

sage.combinat.designs.twographs.
taylor_twograph
(q)¶ constructing Taylor’s twograph for \(U_3(q)\), \(q\) odd prime power
The Taylor’s twograph \(T\) has the \(q^3+1\) points of the projective plane over \(F_{q^2}\) singular w.r.t. the nondegenerate 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 nonsquare) 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 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 twograph 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 theTwoGraph.descendant()
oftwograph of G
, as the intermediate twograph is not constructed.INPUT:
G
– agraph
v
– a vertex ofG
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_packages internet sage: twograph_descendant(A, 0).is_strongly_regular(parameters=True) # optional  gap_packages internet (279, 150, 85, 75)