[This is a slightly corrected resetting, 4-VI-96, of the published article.]

Published in: Optimization, Design of Experiments and Graph Theory (Proc. Symp., Bombay, 1986), ed. M.N. Gopalan and G.A. Patwardhan, pp. 314-334. Indian Institute of Technology, Bombay, 1988. MR 90h:05112.

Proceedings of the Symposium on Optimization, Design of Experiments and Graph Theory. Indian Institute of Technology, Bombay. Dec. 15-17, 1986.

TOGS (GENERALIZATIONS OF TWO-GRAPHS)

Thomas Zaslavsky, Department of Mathematical Sciences, State University of New York, University Center at Binghamton, Binghamton, New York 13901, U.S.A.

May, 1984. Revised July, 1986.

Abstract

We generalize two-graphs (“unitogs”) to “togs”, structures consisting of sets of polygons or cycles in a graph that satisfy specified relations. Togs are equivalent to switching classes of signings of a particular base graph. We develop a mechanism for generating and proving examples and apply it to unitogs (based on complete graphs), bipartite, tripartite, and multipartite togs (based on complete multipartite graphs), circular togs (based on complete circular multipartite graphs), Hamming togs (based on Hamming graphs), and Johnson togs (based on Johnson graphs, whose nodes are the r -subsets of a set, with adjacency corresponding to (r − 1)-element overlap).

We also explore the possibility of generalizing unitogs to set families which are determined by the sets on any one point. In some examples such a “residually determined” family must be a tog or one of a few exceptional families.

1. Introduction

A two-graph (in our terminology a unitog) is a class of (unordered) triples of elements of a given point set, such that each quadruple of points contains an even number of triples in the class. Unitogs have found application to strongly regular graphs, equiangular line sets, and permutation groups (see the survey [6]). In this article we explore the combinatorics of generalizing unitogs, concentrating on a generalization based on signed graphs which we call a tog (a rough acronym for “generalized Two-Graph” which we like because it is short and distinctive^{1}) and which is due more or less independently to Cameron (see [10, Section 2.1] and [2]) and myself [13]. We give a general definition and a technique for verifying examples (Section 3), a collection of examples illustrating the technique (Section 4), and a discussion of the connection between togs and another possible generalization related to extension of designs (Section 5). Our hope is that some of the interesting properties and applications of unitogs will have analogs for other examples, but we do not treat such questions here.

Unitogs were first defined explicitly by G. Higman (see [6, 8]). But they had earlier shown up implicitly in the work of Seidel and others ([4], [5], and see [6], [7]) on sets of equiangular lines and switching equivalence classes of adjacency matrices of signed complete graphs. Since the latter standpoint was the inspiration for our work, we describe it here.

A signed graph is a graph with signed edges. A cycle is called positive or negative depending on the product of its edge signs. Let T (Σ) be the class of negative triangles in a signed complete graph Σ. Then T (Σ) is a unitog. (Strictly speaking, the unitog consists of the node triples which support negative triangles.) Furthermore, every unitog arises in this way, and uniquely so in the following sense. Let Σ_{1} and Σ_{2} be switching equivalent, Σ_{1} ∼ Σ_{2} , if one is obtained from the other by (signed) switching: reversing the signs of the edges between a node set and its complement. Then T (Σ_{1}) = T (Σ_{2}) if and only if Σ_{1} ∼ Σ_{2} . Thus unitogs correspond to switching equivalence classes of signed complete graphs. The adjacency matrix of Σ is A = (a_{ij}) where a_{ii} = 0 and a_{ij} = ±1 for i ≠ j, a_{ij} taking the sign of the edge joining the i-th and j -th nodes. Switching Σ corresponds to conjugating A by a diagonal matrix whose diagonal elements are ±1. We call A a matrix of T (Σ). (In work on unitogs [4-8] it is customary to suppress the positive edges, leaving a graph G. Then A is called the (0, −1, +1)-adjacency matrix of G.)

In a tog we replace the complete graph by an arbitrary graph Γ and the triangles by a class D of distinguished cycles that spans the binary vector space of all cycles. A tog is then a subclass of distinguished cycles which is the class of negative distinguished cycles in some signing of Γ. The heart and the hard part of the generalization is to find analogs of the quadruple constraints: that is, to find combinatorial properties of a subclass of D which are valid if and only if the subclass is a tog. This is what makes a true generalization of unitogs. The tog itself is an epiphenomenon upon the “foundation” consisting of Γ, D, and the combinatorial constraints. Our theory is intended to help find and establish the validity of such constraints, in other words to treat foundations. The togs themselves are not directly our concern.

One can take quite a different approach, as Cameron did in [1]. Suppose we want a class T of (unordered) triples in an n-element point set such that the triples on any one point v determine the rest. The motivation comes from the fact that, if T were a design, it would be determined by the residual design T /v = ({x, y} : {v, x, y} ∈ T }. The simplest rule is that the number of triples of T in any set of four points should belong to a fixed set S of permitted numbers. Evidently, if S ⊆ {0, 2, 4} then T is a unitog. One can show that, for arbitrary S, there are only two kinds of possible classes T that are not unitogs. Thus we are led to the same evenness condition as was suggested by the signed-graph approach. In Section 5 we show that this near agreement of definitions holds true for several other examples of togs, although not for all.

Having now outlined the entire article, we present some of the examples to be treated in detail in Section 4.

Unitogs have already been defined. A set N of n lines in ℝ^{d} is equiangular if any two lines make the same angle. Such a set gives rise to a signed complete graph Σ on N.

1The term “2-graph” has several unrelated senses in the literature. Besides a unitog it can mean a 2-regular graph or a 2-uniform hypergraph, for instance.

Choosing a unit vector u_{i} parallel to each line l_{i}, give the edge e_{ij} the sign of u_{i} · u_{j} for i ≠ j. Reversing some of the unit vectors has the effect of switching Σ. Hence, an equiangular line set determines a unitog; the converse is also true (see [6, Theorem 5.4]).

The most important unitogs are regular: each pair of points lies in the same number λ of triples of the unitog T . That is, T is a 2 − (n, 3, λ) design. (See [6] and [8] for regular unitogs.) There are close connections with other combinatorial objects, for instance strongly regular graphs. If Σ is a signed complete graph for which T (Σ) is a regular unitog, and if in the negative-edge subgraph G a node w is isolated, then G\w is strongly regular. Seidel showed that regular unitogs are characterized by having a matrix A with exactly two eigenvalues, whose product is 1−n, where the point set has n elements. One aim of the theory of togs is to find definitions of regularity in other examples that have characterizations and connections to other areas as interesting and fruitful as those of unitogs.

Bipartite togs, briefly bitogs, are based on complete bipartite graphs. A bitog can be defined as a class T of (unordered) quadruples of points, half of each quadruple drawn from each of two disjoint sets X and Y with cardinalities l and m, such that any quintuple contains an even number of quadruples in T . The matrix of a bitog corresponding to the matrix A of a unitog is an l by m matrix B consisting of −1’s and +1’s, such that

[ \begin{matrix}0 & B \\ B^{T} & 0 \end{matrix} ]

is the adjacency matrix of a signing corresponding to T of the underlying graph.

One can define various kinds of regularity. (For regular bitogs see [13, Section 4].) Let (i, j)-regularity mean that any set of i points in X and j points in Y is contained in the same number of bitog quadruples. Bitogs that are both (2, 0)- and (0, 2)-regular arise from 2−(v, k, λ) designs. Hadamard designs yield bitogs that are also (1, 1)-regular. Some matrix characterizations of regularity are: T is (2, 0)-regular if and only if BB^{T} −lI = pA where p ≥ 0 and A is a matrix of a unitog. (The unitog is uniquely determined by T if p ≠ 0.) T is (1, 1)-regular if and only if BB^{T} has at most one non-zero eigenvalue.

In the next three examples we let N = X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{r} be a partition of the point set N, that is, the X_{i} are nonempty and pairwise disjoint. A set of points is transverse if it meets no X_{i} in more than one point; it is a complete transversal if it meets every X_{i} in exactly one point.

A tripartite tog has r = 3; it consists of transverse triples and has an even number of members contained in each set W ⊆ N consisting of exactly two points from each X_{i}.

A multipartite tog has r ≥ 4; it consists of transverse triples and has an even number of members in each transverse quadruple.

A circular tog has r ≥ 4; it consists of complete transversals subject to the condition that there is an even number of tog elements in any set of the form T ∪ {x_{i}, x_{j}} where T is a complete transversal, x_{i} ∈ X_{i}\T, x_{j} ∈ X_{j}\T, and i − j ≢ 0, ±1 (mod r).

A Hamming tog has point set N = {0, 1, ⋯, q − 1}^{d}, where q, d ≥ 2. A Johnson tog has for points all the r-element subsets of an m-element set, where 0 < r < m. These togs are hard to describe briefly, except for Johnson togs with r = 2. The latter can be regarded as having for points the edges of the complete graph K_{m}. A tog consists of triples of edges which either form a triangle or are concurrent at a node of K_{m}, subject to the two conditions that in any concurrent foursome of edges, an even number of triples belong to the tog, and any K_{4} subgraph of K_{m} contains an even number of tog triples.

The idea of generalizing unitogs by means of signed graphs occurred to Cameron (see [10, Section 2.1]) and me and possibly several others. The theory of togs presented in this paper is a generalization of the technique of [13, Sections 1 and 2] (which was perhaps too unsystematic to be called a “theory”), based on the cohomological theory of “exact” triples developed by Cameron and Wells in [10] and [2]. Our theory is substantially equivalent to theirs but we have chosen to employ the graph-theoretic language of [13] rather than the language of exact sequences. There is some cost in the amount of preparatory work required (in Section 2), but perhaps a gain in accessibility of the statements and proofs of examples. Another difference should be mentioned: our Theorem 10, upon which we rely heavily in attacking the examples. It is based on the more special technique discussed at the end of [13, Section 2]. Despite the number of lemmas we need to prove it, it is really quite elementary; but it is useful.

Some of the examples were independently discovered both by Cameron-Wells and me: bitogs and multipartite togs. Tripartite and circular togs were introduced in [13], the latter with an incomplete proof. Hamming and Johnson togs are new, but the former are generalized from the cases where q or d = 2, which are due to Cameron and Wells. These authors have several other interesting examples, such as folded-cube togs [2, (7.9)], togs of polygons ([2, (6.2)], based on [11, Theorem 6]), and togs of induced polygons ([2, (6.4)], based on [9]). For these and more we refer the reader to [2].

The work in Section 5 on residual determinacy is, as far as I know, new except for uniform strong numerical determinacy in the unitog case, which is discussed in [1].

2. Graphs, sets, and signed graphs

A graph Γ = (N, E) may have multiple edges and loops. We write n = |N| for the order of the node set N. A cycle is an edge set which has even degree at every vertex. A polygon is the edge set of a simple, closed path; the class of polygons [of length k] in Γ is denoted by C(Γ) [resp., C^{(k)}(Γ)].

The class P (S) of subsets of a set S forms a binary vector space under the operation of symmetric difference, which we call “sum” and write +. The span of a subset W ⊆ P (S) is denoted by ⟨W ⟩. In particular the polygons of Γ span the subspace of P (E) consisting of all cycles (including the empty set); we call ⟨C(Γ)⟩ the cycle space of Γ. A basis of the cycle space is called a cycle basis. Any subset D of the cycle space spans a subspace ⟨D⟩ of P (E); we speak of independent, spanning, and basic subsets of D meaning, e.g., basic in ⟨D⟩.

A relator in D is a subset R ⊆ D whose sum is 0 (that is, the empty set). The class R(D) of all relators in D forms a subspace of P (D) and hence of P (P (E)). The significance of relators is that they correspond to the linear relations in D; one may think of R(D) as being the class of all linear relations in D. Let B ⊆ D and R ⊆ R(D); we say B respects R if |R\B| is even for every R ∈ R. (In [11] we used the term additive for a subset B that respects R(D).) The meaning of “respect” may be suggested by Lemma 1. For S ⊆ D let 1_{S} be the characteristic function of S, that is 1_{S} : D → ℤ_{2} defined by 1_{S}(C) = 1 if C ∈ S, = 0 if C ∉ S. For S ⊆ P (D), let S^{∗} = {1_{S} : S ∈ S}. Then P (D)^{∗} is the dual vector space of P (D); and every element of P (D)^{∗} has the form 1_{S} for some S ⊆ D. In P (D)^{∗} we have the inner product

1_{S} · 1_{T} = ∑_{C∈D} 1_{S}(C)1_{T} (C) ≡ |S ∩ T | (mod 2).

We write S^{∗⊥} for the orthogonal dual space of S^{∗} in P (D)^{∗}.

Lemma 1. Let B ⊆ D and R ⊆ R(D). The following are equivalent:

(i) B respects R.

(ii) ∑_{D∈R}1_{D\B}(D) = 0 for every R ∈ R.

(iii) 1_{D\B} ∈ R^{∗⊥}.

Proof. Let R ∈ R. Then ∑1_{D\B}(D) = 1_{D\B} · 1_{R} = |R\B| (mod 2). The lemma follows. ■ Lemma 2. Let R_{1} ⊆ R_{2} ⊆ R(D). Then (i) R_{1} spans ⟨R_{2}⟩ if and only if (ii) every B ⊆ D that respects R_{1} also respects R_{2} .

Proof. By Lemma 1, (ii) can be stated: R_{1}^{∗⊥} ⊆ R_{2}^{∗⊥}. Since R^{∗⊥} = ⟨R^{∗}⟩^{⊥} and ⟨R^{∗}⟩ = ⟨R⟩^{∗}, this is equivalent to (ii′) ⟨R_{1}⟩^{∗⊥} ⊆ ⟨R_{2}⟩^{∗⊥}. Since R_{1} ⊆ R_{2} , we have ⟨R_{1}⟩^{∗⊥} ⊇ ⟨R_{2}⟩^{∗⊥} in any case. So (ii′) is equivalent to ⟨R_{1}⟩^{∗⊥} = ⟨R_{2}⟩^{∗⊥}, which is equivalent to ⟨R_{1}⟩ = ⟨R_{2}⟩. ■

The cases R_{2} = ⟨R_{1}⟩ and R_{2} = R(D) will be most useful for us.

The next result is not required for our work; we include it because it throws more light on the significance of “respect”. Proposition 3. If B ⊆ D respects R(D), then ⟨B⟩ ∩ D = B.

Proof. Let B ∈ ⟨B⟩ ∩ D, so B = B_{1} + ⋯ + B_{k} where B_{1}, ⋯, B_{k} ∈ B. Then R = {B, B_{1}, ⋯, B_{k}} ∈ R(D). Since all B_{i} ∈ B and evenly many elements of R are not in B, B must lie in B. ■

Let R be any set of relators in D, and let D′ ⊆ D. The R-closure of D′ is

D′ ∪ {D ∈ D\D′ : ∃ R ∈ R such that D ∈ R ⊆ D′ ∪ {D}}.

We call R a generating relator for D over D′ because it corresponds to the linear relation D = ∑{D′ ∈ R : D′ ≠ D} which expresses D as a linear combination of elements of D′.

Lemma 4. Let B′ ⊆ D′ ⊆ D ⊆ ⟨C(Γ)⟩ where D′ spans D and B′ respects R(D′). Let R ⊆ R(D) be such that D lies in the R-closure of D′. Choose a fixed generating relator (in R) over D′ for each D ∈ D\D′. Define B ⊆ D by B ∩ D′ = B′ and D ∈ D\D′ is in B if and only if an even number of members of its chosen generating relator are contained in D′\B′. Then B respects R(D) and is independent of the choices of generating relators.

Proof. The lemma is an extension of [11, Lemma 3], which concerns the case where D ⊆ C(Γ) and R = R(D), and whose proof is adapted here (with a missing step supplied).

First we show that B is independent of the choice of generating relators. Let C ∈ D\D′ have two generating relators (in R) over D′, {C, C_{1}, ⋯, C_{q}} and {C, D_{1}, ⋯, D_{r}}. Then C_{1} + ⋯ + C_{q} = C = D_{1} + ⋯ + D_{r}, whence {C_{1}, ⋯, C_{q}, D_{1}, ⋯, D_{r}} ∈ R(D′). By the hypothesis that B′ respects R(D′), the numbers of C_{i} and D_{j} not in B′ have the same parity. Consequently, the two generating relators for C agree on whether or not it lies in B.

Now we prove B respects R(D). Suppose R = {D_{1}, ⋯, D_{p}} ∈ R(D). Let the chosen generating relator for D_{i} be {D_{i}, D_{i1}, ⋯, D_{ir_{i}}}, where all D_{ij} ∈ D′. (If D_{i} ∈ D′ we let r_{i} = 1 and D_{i1} = D_{i}.) By hypothesis,

1_{D\B}(D_{i}) = ∑_{j} 1_{D′\B′}(D_{ij}).

Thus we have

∑_{i,j} D_{ij} = ∑_{i} D_{i} = 0

and

∑_{i} 1_{D\B}(D_{i}) = ∑_{i,j} 1_{D′\B′}(D_{ij}).

Let R′ = {D_{ij} : D_{ij} appears oddly often in the p generating relations}. Then R′ ∈ R(D′); so B′ respects it. Therefore, ∑1_{D′\B′}(D_{ij}) = 0. It follows that B respects R. ■

A signed graph Σ = (Γ, σ) consists of an underlying graph Γ and a signing σ : E → {+, −}. For S ⊆ E we define σ(S) = product of the edge signs of S. A polygon C is balanced or unbalanced according as σ(C) = + or −. An edge set (or subgraph) is balanced when every polygon in it is; otherwise it is unbalanced. (Signed graphs and balance were introduced by Harary [3].) The class of balanced polygons of Σ is denoted by B(Σ). We define σ̂ to be σ regarded as a function from the cycle space to ℤ_{2} . Then σ̂ is obviously linear, B(Σ) = C(Γ) ∩ Ker σ̂ by definition, and by standard linear algebra Ker σ̂ is either the whole space or a hyperplane (subspace of codimension 1).

Lemma 5. Let δ : ⟨C(Γ)⟩ → ℤ_{2} be a linear functional. Then there is a signed graph Σ such that σ̂ = δ. Proof. Let F be a maximal forest in Γ and, for an edge e ∉ F, let C(e) be the unique polygon in F ∪{e}. Let σ(e) = + if e ∈ F and σ(e) = (−)^{δ(C(e))} if e ∉ F. This determines Σ. Because σ̂ is linear, the polygons C(e) are a cycle basis, and σ̂(C(e)) = δ(C(e)), we have σ̂ = δ. ■

Switching Σ by a function μ : N → {+, −} means forming Σ^{μ} = (Γ, σ^{μ}) where σ^{μ}(e) = μ(v)σ(e)μ(w) if e is an edge whose endpoints are v and w. We call Σ and Σ^{μ} switching equivalent; their equivalence class is the switching class [Σ] of Σ. Switching leaves σ̂ and B(Σ) unaltered. Fundamental to our generalization of two-graphs is the characterization of switching equivalence classes in Lemma 6. Lemma 6. Let Σ_{1} and Σ_{2} be signed graphs on the same underlying graph. The following are equivalent:

(i) Σ_{1} and Σ_{2} are switching equivalent.

(ii) σ̂_{1} = σ̂_{2} .

(iii) B(Σ_{1}) = B(Σ_{2}).

Proof. This is a well-known lemma; see for instance [12, Proposition 3.2]. We give a proof for the sake of completeness. The equivalence of (ii) and (iii) follows from the fact that B(Σ) = C(Γ) ∩ Ker σ̂. We know (i) implies (iii). Suppose (iii) holds true. Choose a root node w_{j} and a spanning tree F_{j} in each component Γ_{j} of Γ. For i = 1, 2 and v ∈ N(Γ_{j}), let P be the path in F_{j} from w_{j} to v and μ_{1}(v) = σ_{i}(P). Then Σ_{1}^{μ_{1}} = Σ_{2}^{μ_{2}} , so the signed graphs are switching equivalent. ■ Lemma 7. Let B′ ⊆ D′ ⊆ ⟨C(Γ)⟩. B′ respects R(D′) if and only if 1_{D′\B′} : D′ → ℤ_{2} extends to a linear functional ⟨C(Γ)⟩ → ℤ_{2} .

Proof. The “if” part is obvious. The “only if” is obvious if D′ is a subspace of the cycle space. Suppose D′ is arbitrary and B′ respects R(D′). In Lemma 4 let D = ⟨D′⟩ and R = R(D). By that lemma there exists B ⊆ D which respects R(D). Equivalently, 1_{D\B} is a linear functional on D. Therefore it extends to a functional on ⟨C(Γ)⟩. ■

Lemma 8. Let D be a subset of the cycle space ⟨C(Γ)⟩. If D spans ⟨C(Γ)⟩, then the mapping Σ → D ∩ Ker σ̂ induces a one-to-one correspondence between switching classes of signed graphs on Γ and subsets of D that respect R(D).

But if D does not span ⟨C(Γ)⟩, then the mapping is not injective.

Proof. This lemma is an extension of Theorem 2 and Corollary 8 of [11], which concern the case in which D ⊆ C(Γ). The proof here is analogous to that in [11] but is more complete.

First, let D be any subset of the cycle space.

Let Σ be a signed graph. Then D∩Ker σ̂ respects R(D) because σ̂ is linear. Switching Σ leaves σ̂ unaltered. Thus the mapping Σ → f(Σ) = D ∩ Ker σ̂ is a well-defined map from switching classes to subsets of D that respect R(D).

Suppose B ⊆ D respects R(D). By Lemma 7, 1_{D\B} extends to a functional δ on ⟨C(Γ)⟩. By Lemma 5, there is a signed graph Σ such that σ̂ = δ; thus D ∩ Ker σ̂ = B. This shows that f is surjective.

Now suppose D spans the cycle space and f(Σ_{1}) = f(Σ_{2}); that is, D ∩ Ker σ̂_{1} = D ∩ Ker σ̂_{2} . Then σ̂_{1} = σ̂_{2} . By Lemma 6, [Σ_{1}] = [Σ_{2}]. Thus f is injective.

On the other hand, suppose ⟨D⟩ is a proper subspace of the cycle space. Let δ_{1} and δ_{2} be different linear functionals on the cycle space that agree on ⟨D⟩. By Lemma 5, there exist signed graphs Σ_{1} and Σ_{2} for which σ̂_{1} = δ_{1} and σ̂_{2} = δ_{2} . By Lemma 6, [Σ_{1}] ≠ [Σ_{2}]. So f is not injective. ■

3. Theory of togs

Since we take the fundamental object of the general theory to be a switching class of signed graphs, the problems are then to describe the switching classes efficiently and to find simple criteria for recognizing them. A switching class can be described by its class of positive cycles and the latter by its restriction to a spanning class of polygons–the triangles, in the case of unitogs—or more generally to a spanning class D of cycles. Recognition depends (by Lemma 8) on verifying that a possible tog respects R(D); efficient recognition depends on finding a small but adequate set of test relations—for unitogs, the four triangles in each quadruple. We now present our general definition.

A tog consists of a foundation and the tog proper. The foundation F is composed of a graph Γ, a spanning subset D of the cycle space, and a set R of relators in D that spans the relator space R(D). A tog on F is then a subset T ⊆ D such that D\T respects R: each relator in R contains an even number of members of T .

Theorem 9. Given Γ, D ⊆ ⟨C(Γ)⟩, and R ⊆ R(D). If F = (Γ, D, R) is a tog foundation, then togs T on F are in one-to-one correspondence with the switching classes of signed graphs based on Γ, by the rule T = D\Ker σ̂. This correspondence holds only if D spans ⟨C(Γ)⟩ and R spans R(D).

Proof. First, suppose F is a tog foundation. By Lemma 8, switching classes correspond bijectively to subsets of D that respect R(D). Thus, what we have to prove is that a subset B of D respects R if and only if it respects R(D). Since R spans R(D), this follows from Lemma 2. That proves the first part of the theorem.

Suppose R does not span R(D). Then, by Lemma 2, there exists B which respects R but not R(D). Lemma 8 shows that B is certainly not of the form D ∩ Ker σ̂, regardless of whether or not D spans ⟨C(Γ)⟩.

Suppose R spans R(D) but D does not span ⟨C(Γ)⟩. Then B respects R precisely when it respects R(D), but as Lemma 8 indicates, B corresponds to more than one switching class. That concludes the proof. ■

As it stands, Theorem 9 is not that easy to apply. What kinds of relator sets R should one look for? Given D and R, how does one prove they form a tog foundation? We present a method that is effective in several examples, as the next section will show.

Theorem 10. Let Γ be a graph, D ⊆ ⟨C(Γ)⟩, and R ⊆ R(D). Suppose D_{0} ⊆ D_{1} ⊆ ⋯ ⊆ D_{k} = D where each D_{i} lies in the R-closure of D_{i−1} and D_{0} is a cycle basis of Γ. Then F = (Γ, D, R) is a tog foundation, and a tog on F is precisely a set T ⊆ D such that D\T respects R.

Remark. The hypothesis that D_{0} is a cycle basis may be replaced by the two assumptions that D spans the cycle space and that D_{0} is independent or has the same size as a cycle basis. The reason is that the R-closure of D_{i−1} is contained in ⟨D_{i−1}⟩; hence ⟨D_{0}⟩ = ⟨D_{k}⟩.

Proof. D spans the cycle space because D_{0} does so.

By Lemma 4, a subclass B of D respects R(D) precisely when it respects R(D_{0}) and R. Since D_{0} is a basis, R(D_{0}) is empty. Therefore, any subclass respects it. Hence, B respects R(D) if and only if it respects R. By Lemma 2, R spans R(D). ■

This theorem provides not just a mechanism for proving the validity of a tog foundation but also a means of discovery. Suppose Γ and a spanning cycle set D have been chosen; the task is to find R. One way to do so is by picking a basis D_{0} and looking for a set R_{1} of relators such that the R_{1} -closure of D_{0} contains a larger set D_{1} , then a relator set R_{2} (perhaps the same as R_{1} ) so the R_{2} -closure of D_{1} contains a larger set D_{2} , and so on until D_{k} = D is obtained. Then R = R_{1} ∪ ⋯ ∪ R_{k} is a relator set which, with Γ and D, forms a tog foundation. Another way to proceed is to guess R first, then find a basis D_{0} that generates D through one or more intermediate stages D_{i} as in Theorem 10. We used both approaches to find the examples of the next section.

4. Examples

Here we treat in detail several examples of tog foundations. Most of them were already described in the introduction in the form of constraints on sets of points. Here we describe the foundations in terms of cycles of the underlying graph; it should be apparent how the two descriptions are equivalent.

Consider the triple (K_{n}, C^{(3)}(K_{n}), R^{(4)}), where

R^{(4)} = {C^{(3)}(G) : G is an induced subgraph of K_{n} of order 4}.

We prove that this is a tog foundation. Plainly a tog on it is the same as a unitog (a two-graph), defined as a set of triangles having an even number in each set of four vertices.

Theorem 11. (K_{n}, C^{(3)}(K_{n}), R^{(4)}) is a tog foundation. Its togs are precisely the unitogs.

Proof. We have D = C^{(3)}(K_{n}). In Theorem 10 let D_{0} consist of all triangles at a fixed vertex v, let D_{1} = D, and let R = R^{(4)} . ■

Thus (by Theorem 9) unitogs correspond bijectively to switching classes of signed complete graphs. This, of course, is well known.

In our next example the base graph is the complete bipartite graph K_{lm} with left node set X, of size l, and right node set Y , of size m. Let

R^{(5)} = {C^{(4)}(G) : G is a subgraph of K_{lm} isomorphic to K_{2,3} or K_{3,2}}.

Theorem 12. (K_{lm}, C^{(4)}(K_{lm}), R^{(5)}) is a tog foundation. Its togs are the sets T ⊆ C^{(4)}(K_{lm}) having an even number of members in each K_{2,3} and each K_{3,2} subgraph of K_{lm}.

Proof. Fix a ∈ X and b ∈ Y . In Theorem 10 let D = C^{(4)}(K_{lm}) and R = R^{(5)} . Let D_{0} consist of all quadrilaterals meeting a and b; let D_{1} consist of all meeting a or b; and let D_{2} = D. ■

By Theorem 9 these bipartite togs (for short, bitogs) correspond one-for-one to switching classes of signed complete bipartite graphs.

Other complete multipartite graphs lead to togs consisting of triangles, thus resembling unitogs. Let K_{n_{1}n_{2}···n_{r}} be the complete r-partite graph on node sets N_{1}, N_{2}, ⋯, N_{r} of orders n_{1}, n_{2}, ⋯, n_{r}. For r ≥ 4, let

R^{(4)} = {C^{(3)}(G) : G is an induced subgraph isomorphic to K_{4}}.

For r = 3, let

R^{(6)} = {C^{(3)}(G) : G is an induced subgraph isomorphic to K_{2,2,2}}.

Theorem 13. (K_{n_{1}n_{2}n_{3}}, C^{(3)}(K_{n_{1}n_{2}n_{3}}), R^{(6)}) is a tog foundation.

Theorem 14. For r ≥ 4, (K_{n_{1}···n_{r}}, C^{(3)}(K_{n_{1}···n_{r}}), R^{(4)}) is a tog foundation.

Proofs. Let a_{i} ∈ N_{i} be fixed elements for i = 1, 2, 3. Let D_{0} consist of all triangles which contain a_{1} , or contain a_{2} and meet N_{1} , or contain a_{3} and meet N_{1} and N_{2} . It is easy to see that D_{0} is independent and has the cardinality of a basis for C(K_{n_{1}···n_{r}}); hence it is a basis.

Suppose r = 3. Then each triangle not meeting a_{1} , a_{2} , or a_{3} lies in the R^{(6)} -closure of D_{0} . So Theorem 10 applies with k = 1.

Suppose r ≥ 4. Each triangle not meeting N_{1} is in the R^{(4)} -closure of D_{0} . Let D_{1} consist of D_{0} with all such triangles adjoined. Each triangle meeting N_{1} but not N_{2} is in the R^{(4)} -closure of D_{1} . Let D_{2} be D_{1} with those triangles adjoined. Let D_{3} be D_{2} together with all triangles meeting N_{1} and N_{2} but not N_{3} . Finally, let D_{4} be D_{3} with all remaining triangles meeting N_{1} , N_{2} , and N_{3} added on. Since every D_{i} lies in the R^{(4)} -closure of D_{i−1} , Theorem 10 applies with k = 4. ■

The togs based on the foundations in Theorems 13 and 14 we call multipartite togs. Those with r ≥ 4 are quite similar to unitogs; in fact they are a direct generalization since setting all n_{i} = 1 gives unitogs. Tripartite togs, on the other hand, are unexpectedly different and complicated.

A tog can be based on a sparser graph than a complete multipartite one. The complete circular multipartite graph Γ = C_{r}[N_{1}, N_{2}, ⋯, N_{r}] has node set N = N_{1} ∪ ⋯ ∪ N_{r}, where the N_{i} are disjoint and nonempty, and edge set E = {x_{i−1}x_{i} : i = 1, 2, ⋯, r}, where by convention subscripts indicate part membership (e.g., x_{i} ∈ N_{i}) and are taken modulo r. We call a polygon of the form x_{1}x_{2} ⋯ x_{r} whole. Let C^{∗}(Γ) be the class of whole polygons and let R^{∗} consist of all C^{∗}(G) where G is a subgraph of Γ induced by a node set {x_{1}, ⋯, x_{r}, y_{i}, y_{j}} with y_{i} ≠ x_{i}, y_{j} ≠ x_{j}, and j ≢ i, i ± 1 (mod r).

Theorem 15. Let Γ = C_{r}[N_{1}, ⋯, N_{r}], where r ≥ 4. Then (Γ, C^{∗}(Γ), R^{∗}) is a tog foundation.

We call the togs on this foundation circular togs.

Proof. We identify whole polygons with elements of N_{1} ×⋯×N_{r}. Let a_{1}, ⋯, a_{r} be fixed elements and A = a_{1}a_{2} ⋯ a_{r}. For X ∈ N_{1} × ⋯ × N_{r} we define the deviation d(X) to be |X\A| if the A-elements in X appear in one consecutive string, |X\A| + 1 otherwise. The largest possible deviation is r; the only X with this deviation are those disjoint from A. Let

D_{k} = {X ∈ N_{1} × ⋯ × N_{r} : d(X) ≤ k + 2}.

We need to check that D_{0} is a cycle basis. Let n_{i} = |N_{i}|. D_{0} has the size of a cycle basis, namely |E| − (n − 1) = ∑n_{i}n_{i+1} − n + 1, because it has 1 element of the form a_{1} ⋯ a_{r},

∑(n_{i} − 1) of the form a_{1} ⋯ x_{i} ⋯ a_{r} (one x_{i} ∉ A), and ∑(n_{i} − 1)(n_{i+1} − 1) of the form a_{1} ⋯ x_{i}x_{i+1} ⋯ a_{r} (two adjacent nodes not in A). To see D_{0} is independent, suppose it had a linear relation. No a_{1} ⋯ x_{i}x_{i+1} ⋯ a_{r} can participate in the relation, for the edge x_{i}x_{i+1} belongs to no other element of D_{0} . Then no a_{1} ⋯ x_{i} ⋯ a_{r} can participate, for x_{i}a_{i+1} belongs to no other polygon in the relation. That leaves only A to participate, but A ≠ 0.

We show that D_{k} lies in the R^{∗} -closure of D_{k−1} when 1 ≤ k ≤ r − 3. Suppose d(X) = k + 2. If X contains a substring a_{i−1}y_{i}a_{i+1} (where y_{i} ∉ A), then it contains also a substring of the form x_{j−1}y_{j}a_{j+1} (where y_{j} ∉ A) such that j ≠ i, because |X\A| ≥ k + 1 ≥ 2. On the other hand if X contains a substring y_{i−1}y_{i}a_{i+1} (where y_{i−1}, y_{i} ∉ A), then it contains a substring a_{j−1}y_{j}x_{j+1} (where y_{j} ∉ A) such that j ≠ i − 1; for otherwise d(X) would be 2. In either case let

\begin{aligned}X′ & = X\\{y_{i}\} ∪ \{a_{i}\}, \\ X′′ & = X\\{y_{j}\} ∪ \{a_{j}\}, \\ X′′′ & = X\\{y_{i}, y_{j}\} ∪ \{a_{i}, a_{j}\}. \end{aligned}

Now X′, X′′, X′′′ ∈ D_{k−1} and {X, X′, X′′, X′′′} ∈ R^{∗}. And any X with d(X) = k + 2 falls into one or both cases, for k < r − 2. Consequently indeed the R^{∗} -closure of D_{i−1} contains D_{i}; moreover, in the generating relators we can take j ≢ i, i ± 1 (mod r).

We can obtain D_{r−2} similarly from D_{r−3} if we take i = 2 and j = r. Since r ≥ 4, we have j ≢ i, i − 1.

Now by Theorem 10 we have the result. ■

The Hamming graph (or lattice graph) H_{d}(q) of dimension d on q symbols has for its nodes the ordered d-tuples x = (x_{1}, x_{2}, ⋯, x_{d}) with x_{i} ∈ {0, 1, ⋯, q − 1}, two nodes being adjacent when they differ in precisely one coordinate. H_{d}(2), for instance, is the graph of the d-dimensional hypercube. A δ -flat f_{S} = f_{S}(y_{1}, ⋯, y_{d−δ}) in H_{d}(q), where S ⊆ {1, 2, ⋯, d} and |S| = δ, is the induced subgraph that has for its nodes those x whose coordinates x_{l} for l ∉ S, arranged in order of increasing subscript, are respectively y_{1}, ⋯, y_{d−δ}. In particular a 1-flat or line l_{i} = f_{{i}}(y_{1}, ⋯, y_{d−1}) is isomorphic to K_{q} and its nodes are naturally labelled 0, 1, ⋯, q − 1; a plane π_{ij} is a 2-flat f_{{i,j}}; a space s_{ijk} is a 3-flat f_{{i,j,k}}. Any triangle or K_{4} subgraph of H_{d}(q) is necessarily collinear. A square is an induced subgraph on the four coplanar points, say in a plane π_{ij}, given by x_{i} = a_{i} or b_{i} and x_{j} = a_{j} or b_{j}. A cube is an induced subgraph on eight cospatial points, say in a space s_{ijk}, given by x_{i} = a_{i} or b_{i}, x_{j} = a_{j} or b_{j}, and x_{k} = a_{k} or b_{k}; it is an H_{3}(2).

A prism is an induced subgraph on six coplanar points, say in π_{ij}, given by x_{i} = a_{1} or b_{1} and x_{j} = a_{2} or b_{2} or c_{2} , or vice versa (so there are two possible orientations for a prism, “horizontal” or “vertical”).

Let S(H_{d}(q)) be the class of squares of H_{d}(q) and let

R^{(4)} = {C^{(3)}(Γ) : Γ is a K_{4} subgraph of H_{d}(q)},
R^{(8)} = {S(Γ) : Γ is a cube in H_{d}(q)},
R^{(6)} = {C^{(3)}(Γ) ∪ C^{(4)}(Γ) : Γ is a prism in H_{d}(q)}.

Theorem 16. Let d ≥ 1, q ≥ 2, and let D = C^{(3)}(H_{d}(q)) ∪ S(H_{d}(q)) and R = R^{(4)} ∪ R^{(6)} ∪ R^{(8)} . Then (H_{d}(q), D, R) is a tog foundation.

We call the togs on this foundation Hamming togs. They generalize the togs on H_{d}(2) and H_{2}(q) found by Cameron and Wells (see [2, (7.7) and (7.8)]).

Proof. We apply Theorem 10 with k = 1 + d. If S is a square, its height is 2 less the number of a_{i}, b_{i}, a_{j}, b_{j} which equal zero. A plane π_{ij}(y_{1}, ⋯, y_{d−2}) is l-initially zero if y_{h} = 0 for h < min(i, l), where we assume i < j. Let S_{h,0} be the set of squares S of height h lying in d-initially zero planes. Let C_{0}^{(3)} = {C ∈ C^{(3)}(H_{d}(q)) : C contains the 0-labelled node in its line}. In Theorem 10 let

D_{0} = C_{0}^{(3)} ∪ S_{0,0},
D_{h+1} = C^{(3)}(H_{d}(q)) ∪ S_{h,0} for h = 0, 1, 2,
D_{3+m} = C^{(3)}(H_{d}(q)) ∪ {S ∈ S(H_{d}(q)) : S lies in a (d − 2 − m)-initially zero plane}

for m = 0, 1, ⋯, d − 2.

A cycle basis has cardinality \frac{1}{2}d(q−1)q^{d}−q^{d}+1, since H_{d}(q) is regular of degree d(q−1) and has q^{d} nodes. Because there are dq^{d−1} lines, |C_{0}^{(3)}| = dq^{d−1}\binom{q−1}{2}. The number of squares of height 0 in a particular plane is (q − 1)^{2} . The number in all d-initially zero planes π_{ij} with a fixed value of i (where we take i < j) is (d − i)q^{d−i−1} . Therefore,

|S_{0,0}| = (q − 1)^{2} ∑_{i=1}^{d−1}(d − i)q^{d−i−1} = (q − 1)^{2}f′(q),

where f(q) = ∑_{0}^{d−1}q^{h} = (q^{d} − 1)/(q − 1). Consequently,

|S_{0,0}| = (q − 1)dq^{d−1} − (q^{d} − 1),

so

|D_{0}| = |C_{0}^{(3)}| + |S_{0,0}|

= \frac{1}{2}dq^{d−1}(q − 1)(q − 2) + dq^{d−1}(q − 1) − q^{d} + 1

= \frac{1}{2}dq^{d−1}(q − 1)q − q^{d} + 1,

which is the cardinality of a cycle basis.

Because of the relators C^{(3)}(Γ) where Γ is a K_{4} subgraph of H_{d}(q), the R-closure of D_{0} includes every triangle. Hence it contains D_{1} .

For h = 1, 2, the R-closure of D_{h−1} contains D_{h}, by prism relators in each d-initially zero plane.

For m = 1, 2, ⋯, d − 2, the R-closure of D_{2+m} contains D_{3+m} because of the cube relators

{S_{h}(y_{h}), S_{h}(0), S_{i}(a_{i}), S_{i}(b_{i}), S_{j}(a_{j}), S_{j}(b_{j})},

where d − 2 − m = h < i < j, the plane π_{ij}(y_{1}, …, y_{d−2}) is h-initially zero, and S_{l}(α) for l ∈ {h, i, j} denotes the square given by x_{l} = α in the cube f_{{h,i,j}}(y_{1}, ⋯, y_{h−1}, y_{h+1}, ⋯, y_{d−2}).

Consequently, each D_{i} lies in the R-closure of D_{i−1} . It remains to show that D_{1+d} spans the cycle space.

Lemma 17. D spans the cycle space of H_{d}(q).

Proof of Lemma. If not, let C be a cycle of minimum length not in ⟨D⟩. Evidently C is a polygon. It cannot have three consecutive collinear nodes, because then summing it with a triangle would reduce its length. Suppose C had three consecutive nodes wxy, and let x′ be the fourth node of the square they determine. If x′ were a node of C, then summing the square wxyx′ into C would either shorten C (if x′wxy or wxyx′ were consecutive in C) or form a nonpolygonal cycle, which would contradict the minimality of C.

Let m(C) be the maximum number of nodes of C in a hyperplane x_{i} = α that does not contain C, and choose C (of minimum length not in ⟨D⟩) to maximize m(C). Letting x_{i} = α be a hyperplane containing m(C) nodes of C, suppose xyz are consecutive nodes with x_{i} = α and y_{i} ≠ α. If z_{i} = α, then x = z, an impossible case. Thus, z_{i} ≠ α. Let xyzy′ be the square containing x, y, z. (The square exists because C has no three consecutive collinear nodes.) Adding this square into C replaces y by y′ and consequently increases m(C) by one. But C already had the maximum value of m(C). This is a contradiction. It follows that D spans the cycle space. ■

Consequently, Theorem 10 applies to (H_{d}(q), D, R), proving Theorem 16. ■

The Hamming graph is the cross product of d copies of K_{q}. There is a notion of product of tog foundations under which the Hamming foundation is the product of unitog foundations. Since the definition and proof are best stated in terms of tensor products of associated exact sequences, we omit them here.

The Johnson graph J_{m}(r) has for node set the class P^{(r)}(V) of r-element subsets of an m-element set V . Two nodes X, Y are adjacent when their overlap has order r − 1, in other words when |X\Y | = 1. J_{m}(1) is K_{m}; J_{m}(2) is L(K_{m}), the line graph of K_{m} (also known as the triangular graph). We assume m > r > 0 for a Johnson graph.

A minor of J_{m}(r) is the induced subgraph on a node set of the form {X ∈ N(J_{m}(r)) : U ⊆ X ⊆ W } where U and W are fixed sets with U ⊆ W ⊆ V and |U| < r < |W |. We say the minor has type J_{|W \U|}(r − |U|).

For notational convenience we abbreviate A ∪ {b_{1}, b_{2}, ⋯, b_{k}}, where A ⊆ V and all b_{i} ∈ V \A, by the notation Ab_{1}b_{2} ⋯ b_{k}.

Theorem 18. Let m > r > 0. Then (J_{m}(r), C^{(3)}(J_{m}(r)), R) is a tog foundation, where R = {C^{(3)}(Γ) : Γ is a minor of J_{m}(r) of type J_{4}(1), J_{4}(2), or J_{4}(3)}.

We call the togs on this foundation Johnson togs. For r = 1 they are the unitogs, since J_{m}(1) has minors of type J_{4}(1) = K_{4} only. Consequently, we need to prove the theorem only for r ≥ 2. We do so by induction on r. But first, we establish that the triangles span the cycle space.

Lemma 19. C^{(3)}(J_{m}(r)) spans the cycle space of J_{m}(r).

Proof. Suppose it did not. Then there would be a polygon C of minimum length not spanned by the triangles. C has length l = 2k or 2k + 1 (where k ≥ 2), according as it is even or odd. Let its nodes, in order, be X_{0}X_{1}X_{2} ⋯ X_{l}. (We take subscripts modulo l, so X_{l} = X_{0} .) Minimality of C implies that

(∗)  d(X_{i}, X_{i+j}) = j for 1 ≤ j ≤ k,

where d(X, Y) = |X\Y | is the distance between X and Y in the graph. In particular, k ≤ r. Property (∗) implies that

\begin{aligned}X_{i} & = W x_{i+1}x_{i+2} ⋯ x_{i+k} for i = 0, 1, 2, ⋯, k, \\ X_{k+1} & = \{ \begin{matrix}W x_{1}x_{k+2}x_{k+3} ⋯ x_{2k} & if l = 2k, \\ W x_{k+2}x_{k+3} ⋯ x_{2k}x_{2k+1} & if l = 2k + 1. \end{matrix} \end{aligned}

Let X′_{1} = W x_{2} ⋯ x_{k}x_{k+2} and let C′ be C with X_{1} replaced by X′_{1} . Then C′ is a polygon with length l, but d(X′_{1}, X_{k+1}) = k − 1. Therefore C′ is triangle-generated. Moreover, the quadrilateral Q = X_{0}X_{1}X_{2}X′_{1}X_{0} has X_{1}X′_{1} as a chord so it is the sum of triangles. It follows that C is a sum of triangles, since C = Q + C′ (as an edge set). This is a contradiction. ■

Proof of Theorem. First, some notation. We let H, I, J denote point sets of sizes r − 3, r − 2, r − 1 respectively. Any edge in the Johnson graph has the form {Ji, Jj}; we call this edge e_{J}^{ij}. There are two kinds of triangles in J_{m}(r), namely

Δ_{I}^{ijk} = {e_{Ii}^{jk}, e_{Ij}^{ik}, e_{Ik}^{ij}}

and

Δ_{J}^{ijk} = {e_{J}^{ij}, e_{J}^{ik}, e_{J}^{jk}}.

The latter are analogs of the vertex triangles in L(K_{m}); we call them verticial triangles. The former are analogous to the triangles in L(K_{m}) arising from triangles in K_{m}; we call them essential. When we name a triangle of either type, we imply that i < j < k and that i, j, k are not in I or J (as appropriate). The three kinds of relators in R are those of type J_{4}(1), namely

(1)  {Δ_{J}^{ijk}, Δ_{J}^{ijl}, Δ_{J}^{ikl}, Δ_{J}^{jkl}},

those of type J_{4}(2), namely

(2)  {Δ_{I}^{ijk}, Δ_{I}^{ijl}, Δ_{I}^{ikl}, Δ_{I}^{jkl}, Δ_{Ii}^{jkl}, Δ_{Ij}^{ikl}, Δ_{Ik}^{ijl}, Δ_{Il}^{ijk}},

and those of type J_{4}(3), namely

(3)  {Δ_{Hi}^{jkl}, Δ_{Hj}^{ikl}, Δ_{Hk}^{ijl}, Δ_{Hl}^{ijk}}.

We leave it to the reader to verify by taking the appropriate 4-point minor that each of these does indeed belong to R(C^{(3)}(J_{m}(r))). The third type appears only when r ≥ 3.

The size of a cycle basis in J_{m}(r) is

b_{m}(r) = \frac{r(m − r)}{2}\binom{m}{r} − \binom{m}{r} + 1

since there are \binom{m}{r} nodes and each one has degree r(m − r).

Proof of the case r = 2. Let D_{0}(2) consist of all verticial triangles Δ_{i+1}^{ijk} (where j, k ≠ i+1, of course) and all essential triangles Δ_{∅}^{1jk}. Then

|D_{0}(2)| = m\binom{m − 2}{2} + \binom{m − 1}{2} = b_{m}(2).

Let D_{1}(2) consist of D_{0}(2) and all verticial triangles. Then D_{1}(2) lies in the R-closure of D_{0}(2) because of (1). By (2) with i = 1, the R-closure of D_{1}(2) contains every essential triangle Δ_{∅}^{jkl}, in other words it contains D_{2}(2) = C^{(3)}(J_{m}(2)). Now we apply Theorem 10 with k = 2. Proof of the case r > 2. Let J_{m}(r)/1 be the minor induced by the nodes X that contain 1; it is of type J_{m−1}(r − 1). Let D_{0}(r) consist of the cycle basis D_{0}(r − 1) for J_{m}(r)/1 together with the essential triangles Δ_{I}^{jkl} where 1 ∉ I and j < k < l > max I and the verticial triangles Δ_{J}^{1kl} where 1 ∉ J and 1 < k < l > max J. The size of D_{0}(r) is therefore

b_{m−1}(r − 1) + ∑_{l=r+1}^{m} \binom{l − 2}{r − 2}\binom{l − r + 1}{2} + ∑_{l=r+2}^{m} \binom{l − 2}{r − 1}\binom{l − r − 1}{1} = b_{m}(r).

By the previous step of the induction we know that D_{p}(r − 1) = C^{(3)}(J_{m}(r)/1) for p = 3r − 7. Let D_{q}(r) = D_{0}(r) ∪ D_{q}(r − 1) for q ≤ p. Our proof starts with D_{p}(r).

Let Δ_{I}^{ijk} satisfy l = max I > k. Then, setting H = I\{l}, we see Δ_{I}^{ijk} ∈ R-closure of D_{p}(r) because of (3). Let D_{p+1}(r) = D_{p}(r) ∪ {essential triangles}.

Let Δ_{J}^{1jk} satisfy l = max J > k. Then, setting I = J\{l}, we see that Δ_{J}^{1jk} ∈ Rclosure of D_{p+1}(r) because of (2) with i = 1. Let D_{p+2}(r) = D_{p+1}(r)∪{verticial triangles Δ_{J}^{1jk}}.

Finally, D_{p+3}(r) = C^{(3)}(J_{m}(r)) lies in the R-closure of D_{p+2}(r), for Δ_{J}^{jkl} ∈ R-closure of D_{p+2}(r) by (1) with i = 1. Therefore Theorem 10 applies with k = p + 3 and D_{q} = D_{q}(r) for q ≤ k. ■

One can generalize Theorem 18 for r = 2 to a construction of a tog foundation on the line graph L(Γ) of a graph Γ supporting a given tog foundation. It would be desirable to extend this result to all r; probably that would depend on finding a suitable definition of togs on hypergraphs.

5. Residual determinacy

Cameron in [1] presents unitogs as classes T of triples in a set N such that the residuum T /p = {T ∈ T : p ∈ T } on any point p determines the whole class in a natural way. (If we regard T /p as a graph on vertex set N\{p}, then a unitog is an extension, in the sense of design theory, of a graph by a point such that the graph determines the whole extension.) Specifically, there is a set S of integers such that whether a triple T not on p is in T is determined by the requirement that |T (T ∪ {p})| ∈ S. (By T (U) we mean {T ∈ T : T ⊆ U}.) Evidently S must satisfy |i − j| ≠ 1 for i, j ∈ S. If S ⊆ {0, 2, 4}, T is a unitog. One can show, as Cameron remarks, that there are only two other examples: T = all triples on a certain point, and the complementary class T^{C}.

If one could generalize this observation to other situations, showing that a class obeying a rule of residual determinacy (such as the numerical rule above) is a tog or is one of a small list of exceptions, then choosing to base a generalization of unitogs on signed graphs would seem less arbitrary. We explore this idea here in two directions: we show that the weakest possible rule of global residual determination gives no new examples in the case of classes of triples, and we study other kinds of togs from the same point of view. Several kinds do have nice characterizations: bitogs, for example, are nearly characterized by residual determinacy. On the other hand, a rule of residual determination like Cameron’s rule for triples fails completely to characterize quadripartite togs. Thus one cannot expect a completely general characterization theorem. Unfortunately, we have not even a fairly general theorem. Here we present the evidence of examples and a few remarks on what one might hope to discover.

Let D be a fixed class of subsets of a set N. We wish to find subsets T ⊆ D such that, for each p ∈ N, the residuum T /p determines T in a natural way. The most natural way seems to be to let the residual structure in T determine whether or not T belongs to T . If this is the case we call T weakly residually determined. Formally the definition is that, for each p, there is a class Ŝ(p) such that a set T ∈ D(N\{p}) belongs to T if and only if (T /p)(T) is isomorphic to an element of Ŝ(p). Note that Ŝ(p) may vary with p; if it does not, we call the determinacy uniform.

A more restrictive notion is that, for each p, there is a class S(p) such that a set T ∈ D(N\{p}) is in T if and only if T (T ∪ {p}) is isomorphic to an element of S(p). Such a class T we call strongly residually determined. One result one might hope for is that weak determinacy implies strong determinacy. We shall see that this is true for systems D related to unitogs and bitogs.

These are the broadest versions of residual determinacy. In most of our examples we adopt a simpler rule. Call T weakly [or, strongly] numerically determined if for each p there is a set Ŝ(p) [or, S(p)] of integers such that a set T ∈ D(N\{p}) is in T if and only if |(T /p)(T)| ∈ Ŝ(p) [or respectively, |T (T ∪ {p})| ∈ S(p)]. For strong numerical determinacy to be well defined S(p) must not contain two consecutive integers. We call numerical determinacy uniform if Ŝ(p) [or, S(p)] is independent of p. Any tog is uniformly determined with S(p) ⊆ {0, 2, 4, ⋯ }. (This assumes the tog can be described as a class of sets. The definitions can be generalized to classes of cycles in a graph.)

In the first example we take D = P^{(3)}(N), the class of 3-element subsets of N. Then residual and numerical determinacy are the same. We strengthen the observation in [1] that a class with uniform, strong residual determinacy is a unitog or one of two exceptions.

Theorem 20. Let T be a class of (unordered) triples from a set N. If T is weakly residually determined, then it is a unitog or it is the class of triples on a fixed point of N or the complement of such a class.

Proof. We may assume, complementing T if necessary, that there is a quadruple W = pq_{1}q_{2}q_{3} in which T (W) = {q_{1}q_{2}q_{3}}. (Otherwise T is a unitog and we are done.)

There is only one way to extend to a fifth point r, namely with T (W ∪ {r}) = P^{(3)}(q_{1}q_{2}q_{3}r). To show this we examine the number k of triples on r in T (q_{1}q_{2}q_{3}r). From T (W) we know 0 ∈ Ŝ(p) and 1 ∉ Ŝ(q_{i}).

If k = 0, we may take prq_{1} and prq_{2} either both in T or both in T^{c}. The former contradicts 1 ∉ Ŝ(q_{1}), the latter contradicts 0 ∈ Ŝ(p).

If k = 1, say rq_{2}q_{3} ∈ T . This contradicts 1 ∉ Ŝ(q_{1}).

If k = 2, say q_{1}q_{2}r and q_{1}q_{3}r ∈ T . Then from T (q_{1}q_{2}q_{3}r) we have 2 ∈ Ŝ(q_{2}). From T (pq_{2}q_{3}r) we have pq_{2}r or pq_{3}r ∈ T , say the former. Then 2 ∈ Ŝ(q_{2}) applied to T (pq_{1}q_{2}r) shows pq_{1}r ∈ T . Since 2 ∈ Ŝ(r), T (pq_{2}q_{3}r) gives pq_{3}r ∉ T . Then T (pq_{1}q_{3}r) contradicts 1 ∉ Ŝ(q_{3}).

If k = 3, then P^{(3)}(q_{1}q_{2}q_{3}r) ⊆ T . We have to decide which triples pq_{i}r are in T . If (say) pq_{2}r ∈ T , then 3 ∈ Ŝ(r) applied to T (pq_{1}q_{2}r) implies pq_{1}r ∉ T . If pq_{1}r ∉ T , then 1 ∉ Ŝ(q_{1}) implies no pq_{i}r ∈ T . Thus T = P^{(3)}(q_{1}q_{2}q_{3}r).

The proof can be completed by induction on |N|. ■

In the second example we take disjoint sets X and Y and D = D(X, Y) = {T ⊆ X ∪Y : |T ∩ X| = |T ∩ Y | = 2}. Residual and numerical determinacy coincide.

Theorem 21. Let X and Y be disjoint, nonempty sets and let T ⊆ D(X, Y). If T is weakly residually determined, then it or its complement is a bitog or is constructed by partitioning X = X_{1} ∪ X_{2} (or, Y = Y_{1} ∪ Y_{2}) and choosing all T ∈ D(X, Y) which meet both X_{1} and X_{2} (or, Y_{1} and Y_{2} ).

The first step of the proof is conveniently stated as a lemma.

Lemma 22. If T is weakly residually determined, it is strongly numerically determined with S(x) = constant S(X) for x ∈ X and S(y) = constant S(Y) for y ∈ Y .

Proof. We write x for elements of X and y for elements of Y . We may assume |X| ≥ 3, |Y | ≥ 2. Let S^{1}(x) = {m : for some x_{1}x_{2}y_{1}y_{2} ∈ T , exactly m of xx_{1}y_{1}y_{2} and xx_{2}y_{1}y_{2} are in T }. Let S^{0}(x) = same but for x_{1}x_{2}y_{1}y_{2} ∉ T . These sets are disjoint because of weak residual determinacy. Let S^{∗}(x) = S^{0}(x)∪{m+1 : m ∈ S^{1}(x)}. Then S(x) ⊇ S^{∗}(x). Define S^{1}(y), etc., similarly.

We wish to prove that a set S(X) exists for which all S^{∗}(x) ⊆ S(X); then we may let S(x) = S(X). Also, that S(Y) exists for which all S^{∗}(y) ⊆ S(Y).

Case 1. Let |Y | = 2. Let T = {xx′ : xx′ ∪ Y ∈ T }. This defines a graph on X. Fix p ∈ X and let Q = {q ∈ X : pq ∈ T }, R = {r ∈ X : r ≠ p, pr ∉ T }. By weak numerical determinacy, Q is a clique or a coclique, so is R, and either all edges qr are in T or none is. Let us assume |Q| ≥ |R|, so |Q| ≥ 2.

Suppose Q is a clique and R is not empty. Then qr ∉ T because 2 ∈ S^{1}(q). Also, R is a clique, because 0 ∈ S^{1}(r) but if r_{1}r_{2} ∉ T then 0 ∈ S^{0}(r_{1}), a contradiction.

Suppose Q is a coclique and R is not empty. Then 1 ∈ S^{1}(q) so qr ∈ T. The triple pqr shows that 2 ∈ S^{0}(q). This implies r_{1}r_{2} ∉ T. So R is a coclique.

These arguments leave us with six possibilities for T.

(a1) T = K(X), the complete graph on X. In this case all S^{0}(x) = ∅, S^{1}(x) = {2}. (a2) T = K(X\{r}) ∪ K(r) for some r ∈ X. Here S^{0}(x) = {1} if x ≠ r and

S^{1}(x) = {0} if |X| = 3, {0, 2} if |X| ≥ 4.

(a3) T = K(P) ∪ K(R) for some partition X = P ∪ R with |P | ≥ |R| ≥ 2. Then

S^{0}(x) = {1}, S^{1}(x) = {0, 2}. (b1) T = K(X)^{c}, the edgeless graph. Here all S^{0}(X) = {0} and S^{1}(x) = ∅. (b2) T = K(X, r), the star centered at r, for some r ∈ X. In this case S^{0}(x) = {2} if

|X| = 3, {0, 2} if |X| ≥ 4, and S^{1}(x) = {1} if x ≠ r. (b3) T = K(Q, P), the complete bipartite graph, where Q, P partition X and |P | ≥

|Q| ≥ 2. Here S^{0}(x) = {0, 2} and S^{1}(x) = {1}. Evidently, in every case we can take S(x) = S(X) = {0, 2} or {1, 3}. We can take

S(y) = S(Y) to be any set.

Case 2. Let |Y | ≥ 3. For each pair y_{i}, y_{j} ∈ Y we get a graph T_{ij} on X and sets S_{ij}^{ϵ}(x), ϵ = 0, 1. We have S_{ij}(x) ⊆ {0, 2} for all i, j, x if every T_{ij} is of type (a), all S_{ij}(x) ⊆ {1, 3} if every T_{ij} is of type (b). The only case in which we cannot take all S(x) = {0, 2} or all equal to {1, 3} is that in which, say, T_{12} has type (a) and T_{ij} has type (b) for some ij ≠ 12.

Suppose that is the case. Since S^{ϵ}(x) is the union of S_{ij}^{ϵ}(x) for all ij, we must have S_{12}^{1}(x) ∩ S_{ij}^{0}(x) = ∅. Inspecting the list of possible T graphs shows that T_{12} = K(X)^{c} or T_{ij} = K(X). We must also have S_{12}^{0}(x) ∩ S_{ij}^{1}(x) = ∅. Thus if T_{12} = K(X)^{c}, T_{ij} must be K(X), while if T_{ij} = K(X), then T_{12} must be K(X)^{c}.

We see that if all T_{ij} are not of the same type, (a) or (b), then each is K(X) or its complement and we can take all S(x) = {0, 3}. That concludes Case 2.

We have shown that, if |X| ≥ 3, we can take all S(x) = S(X) = {0, 2}, {1, 3}, or {0, 3}. By the same argument, when |Y | ≥ 3 we can take all S(y) = S(Y).

That completes the proof of the lemma. ■

Proof of Theorem. We may assume |X|, |Y | ≥ 3. If S(X) = S(Y) = {0, 2} or {1, 3}, then T is a bitog or bitog complement.

Suppose S(X) = {0, 3}. Then for each y and y′, T_{yy′} = {T ∈ T : y, y′ ∈ T } is either ∅ or D_{yy′}. If S(Y) = {0, 3}, then T_{xx′} = ∅ or D_{xx′}; it follows that T = ∅ or D. If S(Y) = {1, 3}, then Y partitions into parts Y_{1} and Y_{2} so that T_{y_{1}y_{2}} = ∅ and T_{yy′} = D_{yy′} if y and y′ are in the same part. The case S(Y) = {0, 2} is complementary.

The last case, where S(X) = {1, 3} and S(Y) = {0, 2}, cannot occur. Let W = {x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, y_{3}} and let t_{i} = |T (W \{x_{i}})|, u_{j} = |T (W \{y_{j}})|. Then t_{1} + t_{2} + t_{3} = |T (W)| = u_{1} + u_{2} + u_{3} . But the former sum is even and the latter is odd.

This concludes the proof. ■

A third variety of tog that is nearly determined by a residual rule is the multipartite togs on five or more parts. If X_{1}, X_{2}, ⋯, X_{r} are disjoint sets, a subset of their union is transverse when it has no two elements in any one X_{i}.

Theorem 23. Let N = X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{r} be a partition with r ≥ 5. Let T be a class of transverse (unordered) triples which is weakly residually determined. Then T is a multipartite tog or else it or its complement consists of all transverse triples meeting some fixed set W_{1} ⊆ X_{1} .

Proof. This is a corollary of Theorem 20. ■

The next two examples are a new kind insofar as the residuum is taken over a set P which is a pair or triple of points. The rules we consider are uniform, strong, and numerical. Perhaps weaker rules could have been used. First we take up tripartite togs.

Theorem 24. Let X_{1} , X_{2} , X_{3} be disjoint sets with all |X_{i}| ≥ 3. Let T be a class of transverse triples such that, for some set S of integers, no two consecutive, |T (T ∪P)| ∈ S for every two disjoint transverse triples T and P. Then T is a tripartite tog.

Outline of Proof. We restrict so X_{1} = x_{11}x_{12}x_{13} , X_{2} = x_{21}x_{22}x_{23} , and X_{3} = x_{31}x_{32} . In T (x_{11}x_{12}x_{13}x_{21}x_{22}x_{31}x_{32}) let r_{i} = the number of transverse triples on x_{1i}. Thus r_{1} + r_{2} , r_{1} + r_{3} , r_{2} + r_{3} ∈ S. If all r_{i} have the same parity, we may take S = {evens}; then T is a tripartite tog. If they do not, then R = {r_{1}, r_{2}, r_{3}} = {0, 3} or {1, 4}. (The latter case is complementary to the former.) If, say, r_{1} = 0 and r_{2} = 3, then |T (x_{11}x_{12}y_{2}x_{23}x_{31}x_{32})|, for y_{2} = x_{21} and x_{22} , differ by one. This is absurd. The conclusion follows. ■

Now we look at circular togs. A complete transversal of X_{1}, ⋯, X_{r} is a set consisting of one element from each X_{i}. A nonconsecutive pair is a pair x_{i}x_{j} where j − i ≢ 0, ±1 (mod r). (We take x_{i}, y_{i} to be elements of X_{i}.)

Theorem 25. Let X_{1}, ⋯, X_{r} (where r ≥ 4) partition N, with |X_{i}| and |X_{j}| ≥ 3 for some two nonconsecutive integers i, j (mod r). Let T be a set of complete transversals such that, for some set S of integers, no two of which are consecutive, we have |T (T ∪ x_{k}x_{l})| ∈ S for every disjoint complete transversal T and nonconsecutive pair x_{k}x_{l}. Then T is a circular tog.

Outline of Proof. We can show that S ⊈ {1, 3} by counting elements of T (W) where W = T ∪ x_{i}y_{i}x_{j}y_{j} with T a complete transversal and x_{i}, y_{i}, x_{j}, y_{j} ∉ T.

The case S = {1, 4} is converted to S = {0, 3} by complementing T , so we may assume S = {0, 3}. Let Γ be the bipartite graph on X_{i} ∪ X_{j} defined by choosing a complete transversal A of all X_{k} except X_{i} and X_{j}, and letting x_{i}x_{j} ∈ Γ if Ax_{i}x_{j} ∈ T . Then Γ satisfies: in each quadruple x_{i}y_{i}x_{j}y_{j}, Γ has 0 or 3 edges. Fixing x_{i}, let Q be its neighborhood and R = X_{j}\Q. Each x′_{i} ≠ x_{i} is adjacent to all but one q ∈ Q; it follows that |Q| ≤ 2. From Γ restricted to a subset x_{i}x′_{i}rr′ we see that no x′_{i} is adjacent to any r if |R| ≥ 2. Thus if |R| ≥ 2 and |Q| ≥ 1 we have a contradiction. It follows that either Q = ∅, or |R| = 1 and |Q| = 2. In the latter case every x′_{i} ≠ x_{i} is adjacent to all x_{j}, which leads to a contradiction. In the former case T (A ∪ X_{i} ∪ X_{j}) = ∅ so we may take S = {0, 2, 4}. Thus we are done. ■

We have postponed considering quadripartite togs for a good reason: they do not behave nicely in regard to residual determination.

Example 26. Let X_{1} , X_{2} , X_{3} , X_{4} be disjoint, nonempty sets. Let T be a set of transverse triples such that for some set S of integers, no two consecutive, |T (U)| ∈ S for every transverse quadruple U. If S ⊆ {0, 2, 4}, T is a quadripartite tog. But there are many examples where S ⊈ {0, 2, 4} and they can be quite complicated.

To see this we reinterpret everything. Let X = X_{1}×X_{2}×X_{3}×X_{4} ; we identify transverse quadruples with points x = (x_{1}, ⋯, x_{4}) ∈ X and transverse triples with lines, that is sets of the form {x : three x_{i} are constant}. T becomes a set of lines; the degree of each point x, which we define as the number of lines of T on which it lies, must belong to S. There are many ways to choose T so the set of degrees is {1}, {1, 3}, or {1, 4}, or by complementing T , {3} or {0, 3}. Here are some examples:

(a) Any set of disjoint lines that cover X. The degrees are all 1.

(b) Let ∅ ⊂ Y ⊂ X_{4} . In each 3-flat {x : x_{4} = constant ∈ Y }, take a covering set of disjoint lines. In each other 3-flat take all lines. This example has degrees 1 and 3.

(c) If all |X_{i}| = q, choose a set of q points, no two in a line, and take all lines through these points. The degrees are 1 and 4.

(d) Various combinations of (a)-(c).

Thus in several cases, but not all, a form of residual determination characterizes togs with at most a few exceptions that can be classified easily.

Problem. Find a general theorem of this kind. This problem is admittedly vague. One reason is that I do not have a fully general

definition either of a class D of potential elements of T or of numerical (or residual) determinacy. Another reason is that it is unclear, in view of Example 26, how broad a theorem could be. But any such result not only would help to justify the generalization of two-graphs to togs but also might suggest other generalizations. For instance, if we take T to consist of r-element subsets of N where r ≥ 4, does numerical determinacy imply that T obeys a simple rule like that defining unitogs? If so, we might be able to interpret this rule in terms of signed hypergraphs and thereby deduce a definition of the latter which could be what we need to understand and generalize Johnson togs.

References

1. P.J. Cameron and J.H. van Lint, Graphs, Codes and Designs, London Math. Soc. Lecture Note Ser., Vol. 43, Cambridge Univ. Press, Cambridge, 1980. MR 82d:05002. Zbl. 427.05001. See Chapter 7, ‘Extension of graphs.’ Or see Chapter 6, ‘Extension of graphs,’ in the first edition, Graph Theory, Coding Theory and Block Designs, London Math. Soc. Lecture Note Ser., Vol. 19, Cambridge Univ. Press, Cambridge, 1975. MR 53 #10608. Zbl. 314.94008.

2. P.J. Cameron and A.L. Wells, Jr., ‘Signatures and signed switching classes,’ J. Combinatorial Theory Ser. B, 40 (1986), 344-361.

3. F. Harary, ‘On the notion of balance of a signed graph,’ Michigan Math. J., 2 (1953-1954), 143-146 and addendum preceding p. 1. MR 16, 733. Zbl. 56, 421.

4. P.W.H. Lemmens and J.J. Seidel, ‘Equiangular lines,’ J. Algebra, 24 (1973), 494-512. MR 46 #7084. Zbl. 255.50005.

5. J.H. van Lint and J.J. Seidel, ‘Equilateral point sets in elliptic geometry’, Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A, 69 (= Indag. Math., 28) (1966), 335-348. MR 34 #685. Zbl. 138, 417.

6. J.J. Seidel, ‘A survey of two-graphs,’ in Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Vol. I, pp. 481-511. Accad. Naz. Lincei, Rome, 1976. MR 58 #27659. Zbl. 352.05016.

7. J.J. Seidel and D.F. Taylor, ‘Two-graphs, a second survey,’ in Algebraic Methods in Graph Theory (Proc. Colloq., Szeged, 1978), L. Lovász and V.T. Sós, eds., Vol. II, pp. 689-711. Colloq. Math. Soc. J. Bolyai, 25. Janos Bolyai Math. Soc., Budapest, and North-Holland, Amsterdam, 1981. MR 83f:05070. Zbl. 475.05073.

8. D.E. Taylor, ‘Regular 2-graphs,’ Proc. London Math. Soc. (3), 35 (1977), 257-274. MR 57 #16147. Zbl. 362.05065.

9. K. Truemper, ‘Alpha-balanced graphs and matrices and GF (3)-representability of matroids,’ J. Combinatorial Theory Ser. B, 32 (1982), 112-139. MR 83i:05025. Zbl. 465.05022, 478.05026.

10. A.L. Wells, Jr., ‘Regular generalized switching classes and related topics,’ D. Phil. thesis, Univ. of Oxford, 1982.

11. T. Zaslavsky, ‘Characterizations of signed graphs,’ J. Graph Theory, 5 (1981), 401-406. MR 83a:05122. Zbl. 471.05035.

12. T. Zaslavsky, ‘Signed graphs,’ Discrete Appl. Math., 4 (1982), 47-74. Erratum, ibid., 5 (1983), 248. MR 84e:05095. Zbl. 476.05080, 503.05060.

13. T. Zaslavsky, ‘Multipartite togs (analogs of two-graphs) and regular bitogs,’ in Proc. Fifteenth Southeastern Conf. on Combinatorics, Graph Theory and Computing (Baton Rouge, 1984), Vol. 3, Congressus Numerantium, 45 (1984), 281-293. MR 86d:05109.