# 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)#

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