Abstract
An oriented 3-graph consists of a family of triples (3-sets), each of which is given one of its two possible cyclic orientations. A cycle in an oriented 3-graph is a positive sum of some of the triples that gives weight zero to each 2-set.
Abstract
Our aim in this paper is to consider the following question: how large can the girth of an oriented 3-graph (on n vertices) be? We show that there exist oriented 3-graphs whose shortest cycle has length n 2 2 (1 + o(1)): this is asymptotically best possible. We also show that there exist 3-tournaments whose shortest cycle has length n 2 3 (1 + o(1)), in complete contrast to the case of 2-tournaments.

question in oriented graphs on n vertices is trivial: the shortest cycle can have length n. In the case of a tournament (2-tournament), it is straightforward to see that if a tournament has a (directed) cycle, it must contain a directed triangle. See Moon [5] for background and many results on tournaments.

To be little more precise, an oriented 3-graph can be denoted by G = (V, E), where V is the vertex set (unless otherwise stated, V = [n] = {1, 2, . . . , n} with the natural ordering) and E is the set of oriented triples. Given a triple F = {a, b, c}, it can be oriented (in an oriented 3-graph) either as We write − → abc = − → bca or − → cab for the former and − → acb = − → bac or − → cba for the latter. Each oriented triple induces an orientation on each of its 2-sets. Namely, if F has the former orientation, we have the induced edges − → ab, − → bc, − → ca; and if F has the latter orientation, we have the induced edges − → ac, − → cb, − → ba. A cycle is a weighted sum (with positive weights) of triples that gives each directed edge a total weight of zero.

For an oriented 3-graph G that contains a cycle, we are interested in the shortest cycle in G, one with the smallest length. In particular, we want to know how large the girth (the length of the shortest cycle) of G can be.

The plan of the paper is as follows. We start by considering cycles in 3-tournaments. It is easy to see that if a 3-tournament contains a cycle, then its shortest cycle has length at most n−1 2 + 1. We do not know if the upper bound is best possible (or even asymptotically best possible), but we present a construction giving a lower bound of about 2 3 n 2 . This is in complete contrast to the case of 2-tournaments, where of course if there is a cycle, there is a cycle of length 3. Our construction is based on some embeddings of complete graphs into surfaces of high genus. This is the content of Section 2.

In Section 3 we turn our attention to general oriented 3-graphs. Here the same upper bound of n−1 2 + 1 applies. We show that there exists an oriented 3-graph on n vertices whose shortest cycle has length n 2 (1 + o(1)), which is asymptotically best possible.

For an oriented 3-graph G, we will usually write V (G) for its vertex set and E(G) for its oriented triples. A triple {a, b, c} in an oriented 3-graph is always oriented, and when its orientation is not important to us we will sometimes refer to it as abc.

Finally, we remark that one could view this notion of cycle as a 'homological' version. Of course, as we have 3-sets but no 4-sets there is no notion of 'boundary', so that there is no notion of equivalence of cycles. Our paper does not use any homological notions (but for an introduction to homology, see e.g. Armstrong [1] ).
Cycles in 3-tournaments
In this section, we consider f (n), the length of the shortest cycle in a 3-tournament, maximised over all 3-tournaments on n vertices that contain a cycle.
Cycles in 3-tournaments
It is often helpful to view cycles in matrix terms. Following [4] , the incidence matrix of an oriented 3-graph G is an n 2 × |E| matrix A whose rows and columns correspond to all 2-sets [n] (2) = {i < j : i, j ∈ [n]} and all oriented triples of E respectively. For E = {i < j}, the (E, F ) entry of A is
Cycles in 3-tournaments
So each column of A has exactly three non-zero entries.
Cycles in 3-tournaments
Given an oriented 3-graph G = (V, E) with its incidence matrix A, a non-empty subset C of E is called a cycle if there exists positive real number α F for every F ∈ C such that
Cycles in 3-tournaments
where x F is the column vector of A that corresponds to the oriented triple F . The length of the cycle C is the number of elements in C. For example, the 3-tournament [4] , −→ 123, −→ 142, −→ 134, −→ 243 is itself a cycle of length four. (Note that this is called a directed 4-set in [3] .)
Cycles in 3-tournaments
We first present an easy upper bound on f (n) using standard results from linear algebra. Recall that Carathéodory's theorem says that if a point x ∈ R d lies in the convex hull of a set of points P , there is a subset P ′ of P consisting of at most d + 1 points such that x lies in the convex hull of P ′ .
Cycles in 3-tournaments
For a 3-tournament on n vertices T , the column vectors of its incidence matrix span a subspace of R ( n 2 ) , and we denote this subspace by S T . Lemma 2.1. Let T be a 3-tournament that contains a cycle. Suppose that S T has rank d. Then the shortest cycle in T has length at most d + 1.
Cycles in 3-tournaments
Proof. S T is isomorphic to R d . A cycle in T corresponds to a set of points (column vectors) P , such that its convex hull contains the origin. So by Carathéodory's theorem, there is a subset P ′ of P consisting of at most d + 1 points such that the origin lies in the convex hull of P ′ , which in turn corresponds to a cycle in T whose length is
Cycles in 3-tournaments
Together with the fact that S T has rank at most n 2 for T a 3-tournament on n vertices, we can deduce that f (n) ≤ n 2 + 1 from the above lemma. The following easy result gives a better bound for the rank of S T and hence a better upper bound of f (n).
Cycles in 3-tournaments
Lemma 2.2. Let T be a 3-tournament on n vertices. Then S T has rank at most n 2 − n + 1.
Cycles in 3-tournaments
Proof. Let A be the incidence matrix of T . We show that there are n − 1 linearly independent vectors of R ( n 2 ) such that each one of them is orthogonal to every colomn vector of A. And the conclusion of the lemma follows easily from the rank-nullity theorem.
Cycles in 3-tournaments
For 1 ≤ i ≤ n − 1, let x i be vectors of length n 2 indexed by [n] (2) with the following jk-th entries (j < k).
Cycles in 3-tournaments
It is easy to see that x 1 , x 2 , . . . , x n−1 are linearly independent as x i is the only vector with non-zero in-th entry among them.
Cycles in 3-tournaments
Given a column vector v of A, it corresponds to the orientation of a 3-set in T , say the 3-set {a < b < c}. The only nonzero entries of v are v ab , v bc , and v ac . Either
Cycles in 3-tournaments
In both cases, it is straightforward to check that v is orthogonal to x i for every i. This completes the proof of the lemma.
Cycles in 3-tournaments
Combining Lemma 2.1 and Lemma 2.2, we have the following upper bound of f (n).
Cycles in 3-tournaments
Corollary 2.3. The shortest cycle in a 3-tournament on n vertices that contains a cycle has length at most
Cycles in 3-tournaments
We remark that the bound in Lemma 2.2 is asymptotically best possible. (See the remark at the end of Section 3.)
Cycles in 3-tournaments
We now turn our attention to the lower bound of f (n). We will give a construction of a 3-tournament on n vertices whose shortest cycle has length exactly 1 3 n(n − 1), for infinitely many n. Our proof is based on some embeddings of the complete graphs in high genus surfaces.
Cycles in 3-tournaments
We will also make use of the following lemma by Linial and Morgenstern [4] , which is particularly helpful in our construction. For the sake of completeness, we will include the proof here.
Lemma 2.4 ([4]
). Let C be an oriented 3-graph with the following properties.
Lemma 2.4 ([4]
(i) The only cycle in C consists of all of its triples.
Lemma 2.4 ([4]
(ii) No additional cycle can be created by addition of any single oriented 3-set.
Lemma 2.4 ([4]
Then we can orient the remaining 3-sets (namely, the 3-sets from V (C) (3) \ E(C)) to obtain a tournament T such that C remains as the only cycle in T .
Lemma 2.4 ([4]
Proof. We will show that such T can be constructed by orienting the remaining 3-sets one by one. Let F ′ be a 3-set which was not oriented yet. Suppose that both orientations of F ′ give rise to new cycles. That is,
Lemma 2.4 ([4]
, where x F ′ corresponds to F ′ oriented one of the two ways. Then (α F + α ′ F )x F = 0 is another cycle, which does not involve F ′ . Hence this must be the only cycle C, implying the new cycles created use only the 3-sets from C and F ′ , contradicting the properties of C in the lemma.
Lemma 2.4 ([4]
We are now ready to construct 3-tournaments whose shortest cycle has length 2 3 n 2 . Theorem 2.5. Let n ≥ 4 and n ≡ 0, 3, 4or 7 (mod 12). Then there is a 3-tournament on n vertices whose shortest cycle has length 1 3 n(n − 1).
Lemma 2.4 ([4]
Proof. It is well known that a complete graph K n can be embedded in an orientable surface of sufficiently large genus (see, for example, [6] ). In the cases where n ≡ 0, 3, 4or 7 (mod 12), the genus may be chosen such that the embeddings are triangulations. Given any such triangulation, we can induce an oriented 3-graph C, which is a cycle of length 1 3 n(n − 1), by orienting every face (a 3-set) on the surface in the same orientation: all oriented clockwise or all oriented anticlockwise, viewing from outside the surface.
Lemma 2.4 ([4]
We first claim that C does not contain a cycle of a shorter length. Suppose C ′ ⊂ C is a cycle. Pick any vertex v in C ′ and name the remaining vertices v 1 , v 2 , . . . , v n−1 such that the oriented 3-sets containing v in C are vv i v i+1 , i ∈ [n − 1]. (The subscripts are taken mod n − 1.) By the definition of C, it is not too hard to see that if any of these 3-sets is in C ′ , all of them must be in C ′ . Indeed, vv i−1 v i and vv i v i+1 are the only two oriented 3-sets in C containing the the 2-set vv i . This implies that C ′ contains all of the n vertices. Repeating the above arguments with v replaced by each of v i shows that all 3-sets of C are in C ′ , proving the claim.
Lemma 2.4 ([4]
Next, we claim that C has the property that no additional cycle can be created by the addition of any single oriented 3-set. Suppose C ′ ∪ ρ is a cycle, where C ′ ⊂ C and ρ is an oriented 3-set not in C. That is, there exist positive coefficients α F such that
Lemma 2.4 ([4]
As n ≥ 4, there is a vertex in C ′ but not in ρ. Pick any such vertex v, every 3-set containing v must also be in the new cycle (with the same coefficient). Since ρ / ∈ C, all 3-sets of C are in C ′ and α F is constant. This immediately implies that C ′ ∪ ρ = C ∪ ρ is not a cycle. Now C satisfies the properties in Lemma 2.4, and so there is a tournament such that C remains as the only cycle (hence the shortest cycle). This completes the proof of the theorem.
Lemma 2.4 ([4]
Combining Corollary 2.3 and Theorem 2.5 we have
Lemma 2.4 ([4]
+ 1 for n ≡ 0, 3, 4or 7 (mod 12). Observe that each 2-set is contained in exactly two 3-sets (each giving a different orientation to the 2-set) in the shortest cycle of the tournament in Theorem 2.5, and for the exact value f (n) to be closer to the upper bound, most 2-sets would have to be in three 3-sets of a shortest cycle, which we believe is unlikely. In fact, we believe that our construction is best possible. Conjecture 2.6. For n ≥ 4 and n ≡ 0, 3, 4or 7 (mod 12), we have f (n) = 1 3 n(n − 1).
Lemma 2.4 ([4]
For the case when n ≡ 0, 3, 4or 7 (mod 12), consider the cycle C (an oriented 3-graph spanning m vertices) induced by the triangulation of K m as before, where m is the largest integer smaller than n such that m ≡ 0, 3, 4or 7 (mod 12). Then by almost identical arguments in the proof of Theorem 2.5, there is a tournament on n vertices such that C is the shortest cycle. This, together with Corollary 2.3 and Theorem 2.5, we can bound f (n) for all n ≥ 4. Again, we believe that a construction attaining the upper bound is unlikely and that our construction is asymptotically best possible.
Cycles in oriented 3-graphs
Our main aim in this section is to show that there exists an oriented 3-graph G on n vertices such that the only cycle in G consists of all the triples of G, and has length n 2 (1 − o (1)), attaining the upper bound asymptotically. Our construction could be viewed as an attempt to "add as many projective planes as possible to a small starting configuration".
Cycles in oriented 3-graphs
By a single cycle, we shall mean an oriented 3-graph G where the only cycle in G consists of all its triples. (Note that it follows from this that all cycles in G are the same, up to multiplication by positive reals.) The basic idea is to start from a base single cycle P , then delete a triple from it, and attach P to another single cycle in which a triple is removed. This will result another single cycle, which we can again attach P onto.
Cycles in oriented 3-graphs
To give a better insight to how our final construction is obtained, we will first start with a simple and symmetric base single cycle, the projective plane. (We assume no knowledge of the projective plane; however, for background on surfaces and the projective plane, see e.g. Armstrong [1] or Hatcher [2] .) This will end up giving a single cycle G of length ( For convenience, we will refer a set of triples F as a star system if there is a vertex a such that F ∩ F ′ = {a} for every pair of distinct F, F ′ in F.
Attaching the projective plane
Consider the standard 6-point triangulation of the projective plane in Fig. 1 , where each of the 10 faces (triples) is oriented clockwise. Adding the triple {x, y, z} with anticlockwise orientation − − → xzy results in a single cycle (the triple xyz has coefficient 2, while the other triples each has coefficient 1). Now delete the triple − → acb and we will denote this oriented 3-graph on six vertices by P for the rest of the paper. That is, V (P ) = {x, y, z, a, b, c} and Given an oriented 3-graph G and an oriented triple F = − → ijk in G, we can form a new oriented 3-graph by attaching P on G via F . More precisely, we say G ′ is a (P, F )-attachment on G (or simply P -attachment on G when F is understood) where G ′ has vertex set V (G ′ ) = V (G)∪V (P ) with i, j, k identified with a, b, c respectively, and set of triples E(G ′ ) = E(G) ∪ E(P ) \ − → ijk . So if G is an oriented 3-graph on k vertices and has l triples, then the P -attachment on G is an oriented 3-graph on k + 3 vertices and has l + 9 triples. It is straightforward to check that if G is a single cycle, then G ′ is also a single cycle. (Or see the proof of Lemma 3.1.)
Attaching the projective plane
We can also attach P on an oriented 3-graph via a set of oriented triples, namely, a star system, as follows. Let G be an oriented 3-graph on k vertices and F = F i = −−→ ab i c i : i = 1, 2, . . . , d be a star system in G. We will attach P on G via F i one by one. Set G 1 to be the (P, F 1 )-attachment on G, where G 1 has vertex set V (G) ∪ {x 1 = x, y 1 = y, z 1 = z}. Now, suppose G i−1 is constructed, let G i be the modified (P, F i )-attachment of G i−1 : identify the three new vertices of (P, F i )-attachment of G i−1 with {x, y, z} and delete any repeated triples. That is, if x i , y i , z i are the three new vertices of (P, F i )-attachment of G i−1 , we identify x i with x, y i with y and z i with z. (Note that at each stage, we always attach P with the preserved orientations, for example, the triples {x i , y i , z i } has orientation − −− → x i z i y i . So G i is well defined for all i.) And finally, we say G ′ = G d is the (P, F)-attachment on G (or simply P -attachment on G when F is understood) on k + 3 vertices.
Attaching the projective plane
In other words, for i ≥ 2, G i is obtained from G i−1 by deleting the triple F i = −−→ ab i c i and adding the set of triples − − →
Attaching the projective plane
It is not too hard to see that if G is a cycle, then the P -attachment on G is also a cycle. In fact, if G is a single cycle with a star system F of l triples, the (P, F)-attachment on G is also a single cycle. Proof. Let G, F and G ′ be as in the lemma. We first show that E(G ′ ) is a cycle. Let A be the incidence matrix of G. Since G is a single cycle, there exists positive α F for every triple F in G such that
Attaching the projective plane
where x F is the column vector of A that corresponds to the oriented triple F .
Attaching the projective plane
With a slight abuse of notation, we now refer x F to be the column vector of the incidence matrix of G ′ that corresponds to the triple F in G ′ . It is then straightforward to see that
Attaching the projective plane
By construction, the P -attachment G ′ is a cycle on k+3 vertices and has l+6d+3 triples. Indeed, G 1 , the (P, T 1 )-attachment on G, has l + 9 triples, and G i , the modified (P, F i )-attachment on G i−1 , has six additional triples. Also, note that the set of triples
Attaching the projective plane
So we only need to show that G ′ is a single cycle, that is, the only cycle in G ′ consists of all the triples in G ′ . We will do this by showing that G i is a single cycle for each i ∈ {1, 2, . . . , d}. Let G 0 = G and we note that for i ≥ 1, G i is obtained from G i−1 by deleting the triple F i = −−→ ab i c i and adding the set of triples S. Here,
Attaching the projective plane
Now, for i ≥ 1, suppose that G i−1 is a single cycle and C is a cycle in
Attaching the projective plane
is a cycle of length strictly shorter than |E(G i−1 )| as F i / ∈ C, contradicting G i−1 is a single cycle. So we may assume C contains at least one triple in S, and this will imply that C ⊃ S. This is because the only two triples that contain the 2-set b i x (also the two sets b i z, b i y, c i y, c i x, c i z) are both in S, inducing opposite directions of b i x. And if b i x is contained in a triple in C, both these triples must be in C. Using similar arguments (by considering the 2-sets ax, ay and az), we can further claim that the triples − − → xya, − − → ayz and − − → xzy are also in C.
Attaching the projective plane
We can then write C = C ′ ∪ S, where C ′ ⊂ E(G i−1 ) and C ′ ⊃ { − − → xya, − − → ayz, − − → xzy}. It is then straightforward to check that C ′ ∪ {F i } is a cycle in G i , and hence a cycle in G i−1 . Since G i−1 is a single cycle, necessarily C ′ ∪ {F i } = E(G i−1 ), implying C = E(G i ), completing the proof of the lemma.
Attaching the projective plane
By repeatedly applying Lemma 3.1 to a single cycle, we can construct a single cycle with increasing length. By construction, G i has 4 + 3i vertices, |F i | = i + 1, and G i is a single cycle of length
Attaching the projective plane
. . .
Attaching the projective plane
Now, letting G = G k , we see that G is a single cycle on n = 4 + 3k vertices of length
Attaching a modified projective plane
In order to improve the lower bound in Corollary 3.2, we can try to use a better base single cycle in the inductive construction. Very strangely, it turns out that this will lead to a much improved construction.
Attaching a modified projective plane
By an increment of 3 vertices, Lemma 3.1 produces a larger single cycle, as well as a star system with one extra triple. It would be better if we could have a base single cycle where the new single cycle produced has less than 6 extra vertices and the star system is enlarged by two extra triples. Consider the modified triangulation of the projective plane in Fig. 2 , where each of the 14 faces (triples) are oriented clockwise. Adding the triple {x, y, z} with anticlockwise orientation − − → xzy gives a cycle (in fact a single cycle, where the triple xyz has coefficient 2, while the other triples each has coefficient 1). Now delete the triple − → acb and identify t 1 and t 2 (denote by t 1 = t 2 = t) to obtain the oriented 3-graph S. It is straightforward to check that S is a single cycle with a triple removed.
Attaching a modified projective plane
So S is an oriented 3-graph on 7 vertices and has 14 triples, where V (S) = {x, y, z, t, a, b, c} and
Attaching a modified projective plane
For an oriented 3-graph G that contains a triple F = − → ijk, we can define the (S, F )-attachment on G as in the previous subsection. That is, we say G ′ is the (S, F )-attachment on G (or simply S-attachment on G when F is understood) where G ′ has vertex set V (G ′ ) = V (G) ∪ V (S) with i, j, k identified with a, b, c respectively, and set of triples E(G ′ ) = E(G) ∪ E(S) \ − → ijk . So if G is an oriented 3-graph on k vertices and has l triples, then the S-attachment on G is an oriented 3-graph on k + 4 vertices and has l + 13 triples.
Attaching a modified projective plane
Similarly, we define the (S, F)-attachment on G for an oriented 3-graph G on k vertices, where
Attaching a modified projective plane
is a star system in G, as follows. Let G 1 be the (S, F 1 )-attachment on G. And for i ≥ 2, G i is obtained from G i−1 by deleting the triple F i = −−→ ab i c i and adding the triples
Attaching a modified projective plane
Given a single cycle with a set of triples with a certain property -a star system -we can attach S inductively in such a way that each S-attachment produces a larger single cycle that contains a larger star system. The following lemma, which is very similar to Lemma 3.1, is the key method in our inductive construction. The proof is similar to that of Lemma 3.1 (with extra details) and so is omitted. We remark that the inductive construction above is very far from being an optimal single cycle in a 3-tournament. Indeed, for any single cycle G and any triple F in G, the (S, F )-attachment on G has the property that any orientation of F will give a shorter cycle. Note also that the above construction also shows that the rank of the vector space spanned by its incidence matrix has rank at least 

{'paper_id': '25445664', 'title': 'Cycles in Oriented 3-graphs', 's2_url': 'https://api.semanticscholar.org/CorpusID:25445664', 'source': 'S2ORC'}