{"id":3702,"date":"2022-11-10T21:42:24","date_gmt":"2022-11-10T19:42:24","guid":{"rendered":"https:\/\/blog.atlant.is\/?p=3702"},"modified":"2022-12-17T19:43:13","modified_gmt":"2022-12-17T17:43:13","slug":"steiner-systems","status":"publish","type":"post","link":"https:\/\/blog.douzeb.is\/?p=3702","title":{"rendered":"Steiner Triple Systems"},"content":{"rendered":"\n<p class=\"has-text-align-center\">[WORK IN PROGRESS]<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" loading=\"lazy\" width=\"1024\" height=\"512\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2022\/11\/sts15b-1024x512.jpg\" alt=\"\" class=\"wp-image-4009\" srcset=\"https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b-1024x512.jpg 1024w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b-300x150.jpg 300w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b-768x384.jpg 768w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b-1536x768.jpg 1536w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b-1200x600.jpg 1200w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b-1980x990.jpg 1980w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2022\/11\/sts15b.jpg 2048w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>A Steiner Triple System &#8211; STS for short &#8211; denoted by $\\left(X, {\\cal T}_X\\right)$ is a finite set X together with a set ${\\cal T}_X$ of unordered triplets of elements of X &#8211; called triples or blocks &#8211; with an additional requirement: every (unordered) pair of elements of X must appear in exactly one of the triples:<\/p>\n\n\n\n<p>\\begin{align}<br>\\forall a \\neq b \\in X, \\exists! T \\in {\\cal T}_X, \\mbox{ such that } \\{a, b\\} \\subset T<br>\\end{align}<\/p>\n\n\n\n<p>The existence and uniqueness of $T \\in {\\cal T}_X$ allow to define the function $\\tau_X$:<\/p>\n\n\n\n<p>\\begin{align}<br>\\tau_X: \\; &amp; \\left(\\begin{array}{c}<br>X\\\\<br>2<br>\\end{array}<br>\\right) \\to X\\\\<br>&amp; \\{a, b\\} \\stackrel{\\text{def}}{\\mapsto} c,\\; \\mbox{ such that } \\{a, b, c\\} \\in {\\cal T}_X \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>End game: assuming $\\left(A, {\\cal T}_A\\right)$ is an STS, we want to construct a larger STS $\\left(X, {\\cal T}_X\\right)$ of which $\\left(A, {\\cal T}_A\\right)$ would be a sub system &#8212; that is to say $X$ and ${\\cal T}_X$ would be supersets respectively of $A$ and ${\\cal T}_A$.<\/p>\n\n\n\n<h2>A friendly STS<\/h2>\n\n\n\n<p>The diagram below shows two representations of <em>the<\/em> STS with 7 elements (it is actually unique up to a permutation of the elements). The edges are colored by block, which is made possible by the property of being an STS.<\/p>\n\n\n\n<p>Click on the edges to reveal the blocks. Move the nodes for clarity.<\/p>\n\n\n\n<p class=\"has-text-align-center\" id=\"STS7\"><iframe id=\"auto-iframe\" name=\"auto-iframe\" src=\"https:\/\/douzebis.github.io\/sts\/S-2-3-7.html\" width=\"100%\" height=\"220\" frameborder=\"0\" scrolling=\"no\"><\/iframe><\/p>\n\n\n\n<div class=\"is-layout-flow wp-block-group\">\n<p class=\"has-text-align-center\" id=\"STS7\">Figure 1: $\\mbox{STS}(7)$<\/p>\n<\/div>\n\n\n\n<h2>Double plus one<\/h2>\n\n\n\n<h3>Double-plus-one analysis<\/h3>\n\n\n\n<p>Assume:<\/p>\n\n\n\n<ul>\n<li>An STS $\\left(A, {\\cal T}_A\\right)$, where $\\mbox{card}(A) = n$,<\/li>\n\n\n\n<li>An STS $\\left(X, {\\cal T}_X\\right)$, where $\\mbox{card}(X) = 2n+1$,<\/li>\n\n\n\n<li>$\\left(A, {\\cal T}_A\\right)$ is a sub system of $\\left(X, {\\cal T}_X\\right)$,<\/li>\n<\/ul>\n\n\n\n<p>and let $B$ denote the set $X \\setminus A$.<\/p>\n\n\n\n<p>Then for each element $a \\in A$ and each element $b \\in B$, the unique triple in ${\\cal T}_X$ including $\\left\\{a, b\\right\\}$ is a triple $\\left\\{a, b, b_2\\right\\}$, where $b_2 \\in B$.<\/p>\n\n\n\n<p>This is proven by contradiction. Indeed, assume there were a (unique) $\\left\\{a, b, a_2\\right\\} \\in {\\cal T}_X$, with $a_2 \\in A$. Since $\\left(A, {\\cal T}_A\\right)$ is an STS, there exists $a_3 \\in A$ such that $\\left\\{a, a_2, a_3\\right\\} \\in {\\cal T}_A \\subset {\\cal T}_X$. This would contradict the uniqueness of $\\left\\{a, b, a_2\\right\\}$ $\\Box$<\/p>\n\n\n\n<h4>Tau mappings<\/h4>\n\n\n\n<p>Thus it holds that:<\/p>\n\n\n\n<p>\\begin{align}<br>\\forall a \\in A, b \\in B, \\; \\tau_X(\\{a, b\\}) \\in B<br>\\end{align}<\/p>\n\n\n\n<p>For $a \\in A$ and $b \\in B$, let:<\/p>\n\n\n\n<p>\\begin{align}<br>\\tau_a: \\; &amp; B \\to B\\\\<br>&amp; b \\stackrel{\\text{def}}{\\mapsto} \\tau_X(\\{a, b\\}) \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>\\begin{align}<br>\\tau^b: \\; &amp; A \\to B\\\\<br>&amp; a \\stackrel{\\text{def}}{\\mapsto} \\tau_X(\\{a, b\\}) \\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>The following properties hold:<\/p>\n\n\n\n<p>\\begin{equation}<br>\\tau_a \\mbox{ does not have a fixed point}\\label{nofixedpoint}<br>\\end{equation}<br>\\begin{equation}<br>\\tau_a \\mbox{ is an injective mapping}\\label{injectivea}<br>\\end{equation}<br>\\begin{equation}<br>\\tau_a \\circ \\tau_a = \\mbox{id}_B\\label{pair}<br>\\end{equation}<br>\\begin{equation}<br>\\tau^b \\mbox{ is an injective mapping}\\label{injectiveb}<br>\\end{equation}<\/p>\n\n\n\n<p>($\\ref{nofixedpoint}$), ($\\ref{pair}$), ($\\ref{injectivea}$), and ($\\ref{injectiveb}$) derive directly from the definition of $\\tau_a$ and the uniqueness of the triple that includes a given pair.<\/p>\n\n\n\n<h4>Implications of the properties of tau<\/h4>\n\n\n\n<p>($\\ref{injectivea}$) implies that $\\tau_a$ is a permutation of $B$, and ($\\ref{nofixedpoint}$), ($\\ref{pair}$) imply that all cycles are of length 2. Thus for each $a \\in A$, $\\tau_a$ defines a partitioning of $B$ as a set of (unordered) pairs. Let ${\\cal P}_a \\subset {\\cal P}(B)$ denote this partitioning.<\/p>\n\n\n\n<p>(Incidentally, this implies that $n+1 = \\mbox{card}(B)$ is necessarily even.)<\/p>\n\n\n\n<p>Because of ($\\ref{injectiveb}$), $a_1 \\neq a_2 \\in A \\implies {\\cal P}_{a_1} \\cap {\\cal P}_{a_2} = \\emptyset$. Thus $\\mbox{card}\\left(\\bigcup_{a\\in A}{\\cal P}_a\\right) = n\\cdot{n+1\\over2}$. In other words, $\\bigcup_{a\\in A}{\\cal P}_a$ contains all possible (unordered) pairs of elements of $B$.<\/p>\n\n\n\n<p>Or equivalently, for each $b_1 \\neq b_2 \\in B$, there is a unique $a \\in A$ such that $\\{a, b_1, b_2\\} \\in {\\cal T}_X$. And $a = \\tau_X(\\{b_1, b_2\\})$.<\/p>\n\n\n\n<p>Finally, it holds that:<\/p>\n\n\n\n<p>\\begin{equation}<br>{\\cal T}_X = {\\cal T}_A \\cup \\bigcup_{b_1 \\neq b_2 \\in B}\\left\\{\\tau_X(\\{b_1, b_2\\}), b_1, b_2\\right\\}<br>\\end{equation}<\/p>\n\n\n\n<h3>Double-plus-one synthesis<\/h3>\n\n\n\n<p>Let us synthesize an STS of \u00ab\u00a0size\u00a0\u00bb $2n+1$ from an STS of \u00ab\u00a0size\u00a0\u00bb $n$.<\/p>\n\n\n\n<p>Assume an STS $\\left(A, {\\cal T}_A\\right)$, where $\\mbox{card}(A) = n$ odd.<\/p>\n\n\n\n<p>Let us enumerate $A$ as: $A = \\{a_1, a_2, &#8230;, a_n\\}$.<\/p>\n\n\n\n<p>Let us consider the set $B = \\{0, 1, 2, &#8230;, n\\}$.<\/p>\n\n\n\n<p>Finally let $X = A \\uplus B\\;$ denote the disjoint union of $A$ and $B$, and define the mapping $\\tau_X: \\left(\\begin{array}{c}<br>X\\\\<br>2<br>\\end{array}<br>\\right) \\to X$ as follows:<\/p>\n\n\n\n<p>\\begin{align}<br>&amp;\\mbox{for } a_i \\neq a_j \\in A, \\; \\tau_X(\\{a_i, a_j\\}) = \\tau_A(\\{a_i, a_j\\})\\;\\in A\\label{a_and_a}\\\\<br>&amp;\\mbox{for } (a_i, b) \\in A \\times B, \\; \\tau_X(\\{a_i, b\\}) = i \\oplus b\\;\\in B\\label{a_and_b}\\\\<br>&amp;\\mbox{for } b_1 \\neq b_2 \\in B, \\; \\tau_X(\\{b_1, b_2\\}) = a_{b_1 \\oplus b_2}\\;\\in A\\label{b_and_b}<br>\\end{align}<\/p>\n\n\n\n<p>($\\oplus$ denotes the binary \u00ab\u00a0xor\u00a0\u00bb operator.)<\/p>\n\n\n\n<p>Note that:<\/p>\n\n\n\n<ul>\n<li>in (\\ref{a_and_b}), since $i&gt;0,\\;$ $\\tau_X(\\{a_i, b\\})$ is different from $b$, \/!\\ Here there is a mistake, if $n$ is not of the form $2^k &#8211; 1$, then $i \\oplus b$ could be outside $B$. A slightly different construction has to be used&#8230; stay tuned!<\/li>\n\n\n\n<li>in (\\ref{b_and_b}), since $b_1 \\neq b_2,\\;$ $\\tau_X(\\{b_1, b_2\\})$ is well defined as an element of $A$.<\/li>\n<\/ul>\n\n\n\n<p>If we write:<\/p>\n\n\n\n<p>\\begin{align}<br>{\\cal T}_X \\;\\; &amp;\\stackrel{\\text{def}}{=} &amp; \\bigcup_{x \\neq y \\in X}\\left\\{\\{x, y, \\tau_X(\\{x, y\\})\\}\\right\\}\\\\<br>&amp; = &amp; {\\cal T}_A \\uplus \\biguplus_{x \\neq y \\in B}\\left\\{\\{x, y, \\tau_X(\\{x, y\\})\\}\\right\\}\\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>then $\\left(X, {\\cal T}_X\\right)$ is an STS.<\/p>\n\n\n\n<p>This is proven by verifying the existence and uniqueness of a superset in ${\\cal T}_X$, for each given unordered pair $\\{x, y\\}$.<\/p>\n\n\n\n<p>Existence is straightforward.<\/p>\n\n\n\n<p>For uniqueness, consider $\\{x, y, z\\}$ and $\\{x, y, z_2\\}$ in ${\\cal T}_X$. Without loss of generality, we can restrict the analysis to the following three cases:<\/p>\n\n\n\n<ul>\n<li>case (\\ref{a_and_a}): if $(x, y, z) = (a_i, a_j, \\tau_A(\\{a_i, a_j\\}))$, then it is also the case that $z_2 = \\tau_A(\\{a_i, a_j\\}) = z$.<\/li>\n\n\n\n<li>case (\\ref{a_and_b}): if $(x, y, z) = (a_i, b, i \\oplus b)$, then either:\n<ul>\n<li>subcase (\\ref{a_and_b}): $z_2 = i \\oplus b = z$, or<\/li>\n\n\n\n<li>subcase (\\ref{b_and_b}): $z_2 \\in B$ and $i = b \\oplus z_2$. Then $z_2 = i \\oplus b = z$.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>case (\\ref{b_and_b}): if $(x, y, z) = (b_1, b_2, a_{b_1 \\oplus b_2})$, then $z_2 = a_i \\in A$ and either:\n<ul>\n<li>subcase (\\ref{a_and_b}): $b_2 = b_1 \\oplus i$, hence $i = b_1 \\oplus b_2$, hence $z_2 = z$, or<\/li>\n\n\n\n<li>subcase (\\ref{b_and_b}): $i = b_1 \\oplus b_2$, hence again $z_2 = z$.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>In all three cases, $z_2 = z$ $\\Box$<\/p>\n\n\n\n<h4>Interpretation<\/h4>\n\n\n\n<p>In summary, we have shown how to derive an STS for a set of cardinal $2n+1$, from an STS for a set of cardinal $n$ odd.<\/p>\n\n\n\n<p>This can be interpreted with the metaphor of a sport&rsquo;s tournament.<\/p>\n\n\n\n<p>Imagine:<\/p>\n\n\n\n<ul>\n<li>$B = \\{0, 1, &#8230;, n\\}$ represents a set of $n+1$ (even) players,<\/li>\n\n\n\n<li>$A = \\{d_1, d_2, &#8230;, d_n\\}$ represents a set of $n$ \u00ab\u00a0days\u00a0\u00bb.<\/li>\n<\/ul>\n\n\n\n<p>The rule is that on day $d_i$, the following $n+1\\over2$ matches occur: player $p$ playing with player $p \\oplus i$ (for every $p$).<\/p>\n\n\n\n<p>This results in an \u00ab\u00a0optimal\u00a0\u00bb organization for the tournament, in the sense that:<\/p>\n\n\n\n<ul>\n<li>on each day, every player plays exactly once,<\/li>\n\n\n\n<li>during the tournament, each player encounters each other player exactly once,<\/li>\n\n\n\n<li>at the end of the tournament (on the evening of day $d_n$) every player has played with every other player, for a total of $\\left(n\\cdot{ n+1\\over2}\\right)$ matches.<\/li>\n<\/ul>\n\n\n\n<div class=\"is-layout-flow wp-block-group\">\n<p class=\"has-text-align-center\" id=\"2nplus1\"><iframe id=\"auto-iframe\" name=\"auto-iframe\" src=\"https:\/\/douzebis.github.io\/sts\/STS-15.html\" width=\"100%\" height=\"220\" frameborder=\"0\" scrolling=\"no\"><\/iframe><\/p>\n\n\n\n<p class=\"has-text-align-center\">Figure 2: $\\mbox{STS}(2\\times7+1)$<\/p>\n<\/div>\n\n\n\n<h2>Further ideas<\/h2>\n\n\n\n<p>In general when the set $X$ is $X_n = \\{1, 2, &#8230;, 2^n-1\\}$, the following tau mapping produces a \u00ab\u00a0natural\u00a0\u00bb STS:<\/p>\n\n\n\n<p>\\begin{align}<br>\\tau_n: \\; \\left(<br>\\begin{array}{c}<br>X_n\\\\<br>2<br>\\end{array}<br>\\right)<br>\\to X_n\\\\<br>\\{i, j\\} \\mapsto i \\oplus j\\nonumber<br>\\end{align}<\/p>\n\n\n\n<p>With that, we obtain a sequence of STSs, each one a subsystem of the next one in the sequence:<\/p>\n\n\n\n<p>\\begin{align*}<br>(X_0, {\\cal T}_0) \\to (X_1, {\\cal T}_1) \\to (X_2, {\\cal T}_2)\\to \\dots\\\\<br>\\forall i \\in \\mathbb{N}, X_i \\subset X_{i+1} \\mbox{ and } {\\cal T}_i \\subset {\\cal T}_{i+1}<br>\\end{align*}<\/p>\n\n\n\n<p>And $(\\cup X_n, \\cup {\\cal T}_n)$ can be viewed as a countably infinite STS.<\/p>\n\n\n\n<p>The figure below represents $(X_4, {\\cal T}_4)$ and is identical to <a href=\"#2nplus1\">figure 2<\/a> (up to a permutation of the elements).<\/p>\n\n\n\n<div class=\"is-layout-flow wp-block-group\">\n<p class=\"has-text-align-center\"><script type=\"text\/javascript\">\/\/ <![CDATA[\njQuery(document).ready(function(){\n\tsetInterval( function() { AutoiFrameAdjustiFrameHeight( 'auto-iframe', 50); }, 1000 );\n});\n\/\/ ]]><\/script>\n<iframe id=\"auto-iframe\" name=\"auto-iframe\" src=\"https:\/\/douzebis.github.io\/sts\/S-2-power-n-minus-one.html?n=4\" width=\"100%\" height=\"400\" frameborder=\"0\" scrolling=\"no\"onload=\"AutoiFrameAdjustiFrameHeight('auto-iframe',50);\"><\/iframe><\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>Figure 3: $\\mbox{STS}(2^4-1)$<\/em><\/p>\n<\/div>\n\n\n\n<div class=\"is-layout-flow wp-block-group\">\n<p class=\"has-text-align-center\"><script type=\"text\/javascript\">\/\/ <![CDATA[\njQuery(document).ready(function(){\n\tsetInterval( function() { AutoiFrameAdjustiFrameHeight( 'auto-iframe', 50); }, 1000 );\n});\n\/\/ ]]><\/script>\n<iframe id=\"auto-iframe\" name=\"auto-iframe\" src=\"https:\/\/douzebis.github.io\/sts\/S-2-power-n-minus-one.html?n=5\" width=\"100%\" height=\"400\" frameborder=\"0\" scrolling=\"no\"onload=\"AutoiFrameAdjustiFrameHeight('auto-iframe',50);\"><\/iframe><\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>Figure 4: $\\mbox{STS}(2^5-1)$<\/em><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>[WORK IN PROGRESS] A Steiner Triple System &#8211; STS for short &#8211; denoted by $\\left(X, {\\cal T}_X\\right)$ is a finite set X together with a set ${\\cal T}_X$ of unordered triplets of elements of X &#8211; called triples or blocks &#8211; with an additional requirement: every (unordered) pair of elements of X must appear in [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":4007,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,19],"tags":[],"ppma_author":[76,78],"authors":[{"term_id":76,"user_id":1,"is_guest":0,"slug":"fred","display_name":"Fred","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/ec0326d654fdf9f66e9eb42bb34a9bc4?s=96&d=mm&r=g","description":"","first_name":"","last_name":"","user_url":""},{"term_id":78,"user_id":138,"is_guest":0,"slug":"eric","display_name":"\u00c9ric","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/bd048036a0dd651d4b02ebba6b91f97a?s=96&d=mm&r=g","description":"","first_name":"\u00c9ric","last_name":"Brier","user_url":""}],"_links":{"self":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/3702"}],"collection":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3702"}],"version-history":[{"count":197,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/3702\/revisions"}],"predecessor-version":[{"id":4254,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/3702\/revisions\/4254"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/media\/4007"}],"wp:attachment":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3702"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3702"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3702"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fppma_author&post=3702"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}