Structural Qualities and Serial Construction of Tournament Braids

Year: 2012 Authors: D. Jacob Wildstrom

Core claim

The best serial construction order for a tournament braid depends on large transitive subtournaments, but finding an optimal plan is NP-complete.

Topics

tournament braids, serial construction, transitive subtournaments, fault-tolerance

Domains

graph theory, combinatorics, tournament digraphs, NP-completeness, braiding, fiber arts, textile design, craft construction

Methods

pseudoplait model, tournament labeling, structural analysis, example braids

Media

thread, fabric, wire, hair, leather, yarn

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2012: Mathematics, Music, Art, Architecture, Culture

Structural Qualities and Serial Construction of Tournament Braids

D. Jacob Wildstrom Department of Mathematics • University of Louisville 328 Natural Sciences Building • Louisville, KY 40292 • USA dwildstr@erdos.math.louisville.edu

Abstract

A braid is described by both the series of permutations performed on the strands and the choice for each crossing of which strand lies on top. For many classes of braids, ranging from the traditional three-strand braid to more complicated weaves of several strands, a single rule of precedence is used for every crossing of two strands, and thus the rules describing which strand lies on top in each crossing are completely characterized by a tournament whose vertices represent the strands. Braids are often constructed with attention to structural cohesion and ease of design, and this work will associate these desiderata with a mathematical property of the underlying tournaments.

Introduction

Braids of thread, fabric, wire, hair, leather, and many other string-like substances are an ancient and nearly universal human design, created for purposes ranging from the artistic to the practical, and even to spiritual and devotional purposes. Since braids are both decorative and functional, societies prize braids that are artistically pleasing as well as those that are unlikely to come undone or tangled.

Here we seek to describe a particular class of braids by means of orientations of complete graphs, or tournaments. In this work we will consider braids subject to a specific restriction: we shall assume that for each pair of strands, every time those two strands cross the same strand is on top; note that by the $i$th strand we refer to the strand in the $i$th position at the beginning of the braid, not to the strand which is in the $i$th position at other points in the braid. Furthermore, in order to have the most specific structural statements with regard to this precedence scheme, we will investigate the presentation of certain tournaments specifically on a braid referred to as the pseudoplait on $n$ strands in which each strand progressively passes from position 1 down to position $n$ and back, crossing other strands in a manner not yet determined. Braids will be drawn horizontally in this work, with the strands conventionally numbered from top to bottom. This indeterminate form of the pseudoplait is visually represented for the specific case $n=5$ in Figure 1(a). A tournament pseudoplait is a determination of the crossings within a pseudoplait by the orientations of edges in a labeled tournament whose nodes correspond to strands of the braid: when $i\to j$ within the tournament, the crossings of strands $i$ and $j$ of the pseudoplait are resolved such that $j$ is above $i$. Such a tournament pseudoplait is shown specifically in Figure 1(b), derived from the tournament given in Figure 1(c). Note that the labeling is significant, and that a different labeling of a tournament may lead to a different braid.

Serial construction techniques for braids

The traditional construction techniques for braids are mostly parallel processes: all of the individual strands are simultaneously worked, and the twists are inserted successively, according to the order in which they appear in the decomposition of the braid into individual swaps. This is an effective and rapid technique for working almost all braided materials, but there are certain occasions under which a braid must be constructed serially, with the placement of each strand in its entirety on the finished work prior to the insertion of the next strand. A serial construction technique may be necessary on occasions where individual strands will

Wildstrom

(a)

(b)

(c)

Figure 1: (a) A 5-strand pseudoplait with undetermined crossings; (b) A tournament determining the standard plait crossing precedence; (c) The pseudoplait determined by the tournament (a)

(b) Figure 2: (a) A cup cozy whose design consists of unbroken loops braided into a five-strand plait (b) Three trivially-entangled strands in the five-strand plait (c) The tournament describing these three strands

(c)

not easily stay distinct from other strands while they are all being worked, or when the time available for the handling of each strand is limited, as occurs in some forms of metalworking and glasswork, or when the construction is such that each piece must be individually fixed to a background, as occurs in quilting and some yarnwork. The necessity to work a braid strand-by-strand arose naturally as the result of a crochet design: in the woven cup cozy seen in Figure 2, each of the five strands is worked in the round to avoid the need for a seam from sewing ends together, so it is unfeasible to crochet all the strands first and then braid them; rather, the braiding must be established in the process of crocheting each individual strand.

A complication arose in the course of this work: the first two strands were easy to make, as they were not interlocked, but future strands promised to be difficult, as carrying yarn and a hook over and under other pieces of the design is considerably more difficult than crocheting a simple ring. While at first it appeared that it would be necessary to crochet three separate strands within a nontrivially braided work, a simpler construction method is possible, in that one can render the interlocking of the first three strands trivial and it was only necessary to perform difficult braiding steps with the last two strands. The three non-interlocked strands are seen in Figure 2(b), and their associated tournament is given in Figure 2(c).

The exhibited braid of the selected strands in Figure 2(b) is clearly decomposable: the fourth strand lies on top, the fifth strand lies on the bottom, and the first strand lies between them. This is reflected in its tournament by transitivity, a property of tournaments whose orientation corresponds to a total ordering of its vertices; here the ordering 5 < 1 < 4 induces the given orientation.

Based on this example, we may conclude that, from a serial-construction standpoint, an important consideration in choosing the order of strand-placement in a tournament braid is the size of the tournament’s largest transitive subtournament, which is a computationally difficult problem; let us note that there are often maximal transitive subtournaments that are not even close to being of maximum size, so simply laying arbitrary strands until no more strands can be placed by overlaying them could be an extremely poor construction plan. However, devising an optimal construction plan would be an NP-complete problem [1]. While the algorithmic complexity is probably not a major concern for real-world tournament braids, which will not tend

Structural Qualities and Serial Construction of Tournament Braids

(a)

(b) Figure 3: (a) A five-strand pseudoplait with two disentangled strands (b) Exhibition of disentanglement of the “winner” and “loser” of the tournament

to have extremely large numbers of strands, it necessarily hampers further theoretical exploration of the optimal construction orders for arbitrary tournament braids.

Structural significance of transitive subtournaments

From a serial-construction standpoint, a large transitive subtournament is clearly desirable, since it renders the braid easy to produce. However, other factors make large transitive subtournaments undesirable: the transitive tournament on $n$ vertices will yield an easy-to-construct $n$ -strand pseudoplait, but the same factors that render this strand easy to construct will intrinsically render it easy to deconstruct. Any tournament with a “winner” or “loser” — that is, a vertex with only incoming or outgoing edges — yields a highly unsatisfactory pseudoplait from a structural standpoint, since one strand will invariably lie either above or below all other strands, and not be entangled with them at all. Such a pseudoplait is seen in Figure 3(a); its associated tournament depicted in Figure 3(b) illustrates that, while the second, third, and fourth strands have nontransitive mutual orientations which describe the traditional plait, the first and last strands are completely disentangled. Note that this tournament has a four-vertex transitive subtournament, which indicates ease of creation, but this easy-to-create braid is flawed in that it is structurally unsound. Thus, we can see that, as quantified by the size of the maximal transitive subtournament, structural considerations are at odds with the most desirable serial-construction techniques.

Traditional plaits

When investigating the structural and serial-construction characteristics of pseudoplaits, it is natural to inquire into the value of these parameters for the traditional plait. Given that the largest possible number of nodes of an $n$ -vertex tournament that can be in a transitive subtournament is $n$ , and the size of the least maximum transitive subtournament is sublinear in $n$ [2], the most reasonable compromise between the highly transitive (easy to construct but insufficiently structural) and highly intransitive (difficult to construct but highly structural) tournament would be a tournament whose largest transitive subtournament was on approximately half of its vertices. Happily, the tournament associated with a traditional plait exhibits exactly these qualities.

Plaits must use an odd number of strands, and can be more easily subjected to precedence rules based on a different numbering than is conventional. Let $\pi$ be a permutation of $(1,\dots ,2n-1)$ given by $\pi (2i)=i$ and $\pi (2i+1)=2n-i$ . This ordering allows for a concise tournament description: for \pi (i) < \pi (j) , $i\to j$ if and only if $\pi (j)-\pi (i)$ is even. This tournament ordering can be seen in Figure 1(b).

It is clear that in such a tournament there is a transitive subtournament on $n$ vertices, specifically on the vertices ${\pi }^{-1}(1),{\pi }^{-1}(3),{\pi }^{-1}(5),\dots ,{\pi }^{-1}(2n-1)$ ; by construction each vertex of this sequence has an outgoing edge to later vertices in the sequence. It is less obvious that there is no transitive subtournament on more than $n$ vertices, but this can be shown with a simple combinatorial argument. Let us suppose that

Wildstrom

(a)

(b) Figure 4: (a) A labeling of the unique tournament on 7 vertices without a 4-vertex transitive subtournament (b) The pseudoplait determined by the tournament

we have selected $n+1$ vertices ${\pi }^{-1}(i_1),{\pi }^{-1}(i_2)\cdots ,{\pi }^{-1}(i_{n+1})$ that form a transitive subtournament with i_1 < i_2 < \cdots < i_n and without loss of generality set $i_1=1$ . For some even $i_j$ , note that since $\pi (i_j)\to \pi (1)$ and $\pi (1)\to \pi (i_k)$ for each odd i_k > 1 , it follows from transitivity that $\pi (i_j)\to \pi (i_k)$ and thus i_j > i_k for each odd $k$ . Thus every even element of this set exceeds every odd element; a simple partition of the integer interval $1,\dots ,2n-1$ into a lower odd half and upper even half shows that no such decomposition ever yields $n+1$ numbers in total.

Highly intransitive tournaments

Since ease of construction and transitivity are associated with structural weakness, the lack of a large transitive subtournament would be indicative of fault-tolerance: if a pseudoplait’s largest transitive subtournament was very small, then several or even a majority of the strands could be removed without compromising its structural integrity. However, the tournament on $n$ vertices with smallest maximum subtournament is not generally known, and even the size of the subtournament is not known for n > 31 [5]; the best bounds on its size are the lower bound $\lfloor {\log }_2\frac{n}{54}\rfloor +7$ for $n\ge 32$ of Sanchez-Flores [4] and the upper bound $2\lfloor {\log }_{2}n\rfloor +1$ of Erdős and Moser [2]. The specific tournaments in the $n\le 31$ case are all circulant or Galois tournaments, and in several cases are unique. It is hoped that these tournaments admit a labeling whose pseudoplait has both aesthetically pleasing properties and an unusually high structural integrity, surpassing traditional plaits. Such a labeled tournament and its associated pseudoplait are exhibited in Figure 4; this braid is remarkable among 7-strand pseudoplaits in that there are no three strands whose removal will disentangle it. Graumont and Hensel’s compendium of knots [3] identifies this particular braid as a seven-stranded French sennit and give it pride of place early among the upwards of 300 sennits appearing therein, but no source appears to make mention of this braid’s remarkably high fault-tolerance.

References

[1] Jørgen Bang-Jensen and Carsten Thomassen. A polynomial algorithm for the 2-path problem for semi-complete digraphs. SIAM J. Discrete Math., 5(3):366-376, 1992. [2] P. Erdős and L. Moser. On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125-132, 1964. [3] R. Graumont and J.J. Hensel. Encyclopedia of knots and fancy rope work. Cornell Maritime Press, 1952. [4] Adolfo Sanchez-Flores. On tournaments free of large transitive subtournaments. Graphs Combin., 14(2):181-200, 1998. [5] Warren D. Smith. The On-Line Encyclopedia of Integer Sequences. http://oeis.org/A122027. Largest integer $m$ so that every $n$ -tournament contains a transitive (i.e. acyclic) sub-tournament with at least $m$ vertices.