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. [BH12].

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: sage.combinat.designs.incidence_structures.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()
sage: pc = p.complement(); pc
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)
sage: p.is_strongly_regular(parameters=True)
(9, 4, 1, 2)
is_regular_twograph(alpha=False)

Tests 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: 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()
sage: is_twograph(p)
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 [BvL84].

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)

Returns 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_packages internet
sage: twograph_descendant(A, 0).is_strongly_regular(parameters=True) # optional - gap_packages internet
(279, 150, 85, 75)