A new proof of Delahan's induced-universality result

This paper presents a concise and self-contained proof of Delahan's theorem, demonstrating that every simple graph with $n$ vertices appears as an induced subgraph of a Steinhaus graph with $\frac{n(n-1)}{2}+1$ vertices by utilizing the concept of generating index sets for Steinhaus triangles.

The Gist

Imagine you have a giant, magical Lego set. This isn't just any set; it's a specific type of structure called a Steinhaus Graph. These structures are built using a very strict, simple rule: every new piece you add depends entirely on the two pieces directly above it, following a pattern similar to how numbers are added in Pascal's Triangle (but using only 0s and 1s, like a light switch being on or off).

For a long time, mathematicians knew that these Steinhaus Graphs were huge and complex. But a mathematician named Delahan made a bold claim: No matter what small, simple shape you can imagine building with $n$ Lego bricks, you can find that exact shape hidden inside a Steinhaus Graph.

Think of it like this: If you have a library containing every possible book ever written, you can find the story of your life hidden somewhere in the pages. Delahan said Steinhaus Graphs are that library. Specifically, he said that if you want to find a graph with $n$ vertices (dots), you only need to look inside a Steinhaus Graph that is roughly $n^2/2$ in size.

The Problem with the Old Proof
The original proof of this idea was like a heavy, complex machine. It worked, but it was hard to take apart to see how the gears turned. It relied on deep, abstract algebra that felt like trying to fix a watch with a sledgehammer.

The New, Simple Proof
Jonathan Chappelon, the author of this paper, has built a new proof. Instead of a sledgehammer, he used a key.

Here is the simple analogy of his new method:

1. The "Blueprint" Concept (Generating Index Sets)

Imagine a Steinhaus Triangle (the top half of the graph) as a massive, intricate tapestry. Usually, to know what the whole tapestry looks like, you need to see the entire thing.

However, Chappelon discovered that you don't need the whole tapestry. You only need to know the pattern of specific, scattered threads to figure out the rest. He calls these specific spots "Generating Index Sets."

Think of it like a crossword puzzle. If you are given a few specific, carefully chosen letters, you might be able to solve the entire puzzle because the rules of the game (the math) force the other letters to fall into place. Chappelon found a specific set of "magic coordinates" (a list of specific dots in the triangle) that act as the master key. If you know the values at these specific spots, you can mathematically reconstruct the entire triangle.

2. The "Lock and Key" (Invertible Matrices)

In math, proving that these "magic coordinates" work is like proving a lock has a key.

• The Lock is the rule that connects the scattered dots to the rest of the triangle.
• The Key is a special mathematical table (a matrix) that Chappelon built.

Chappelon showed that this table is "invertible." In everyday terms, this means the table is a perfect translator. It can take the information from your "magic coordinates" and translate it into the full picture without losing any data or getting confused. If the table is "invertible," it means the translation is one-to-one: every unique pattern of scattered dots creates a unique full triangle, and every full triangle has a unique pattern of scattered dots.

3. The "Odd Number" Trick

How did he prove the table was a perfect translator? He looked at the "determinant" of the table (a single number that tells you if a matrix is invertible).
He proved that for his specific set of coordinates, this number is always odd.
In the world of binary math (0s and 1s), being "odd" is the same as being "1," which is the magic number that means "Yes, this works!" If the number were even (0), the translation would fail. By showing the number is always odd, he proved the key fits the lock perfectly.

The Grand Conclusion

So, what does this paper actually do?

1. It simplifies the magic: Instead of a complex machine, Chappelon shows us that Steinhaus Graphs are like a giant puzzle where a small, specific set of clues (the Generating Index Set) unlocks the entire picture.
2. It proves universality: Because these clues can unlock any pattern, it means that inside a Steinhaus Graph of a certain size, you can find every possible simple graph you could ever draw.
3. It's self-contained: The proof doesn't rely on other heavy theories; it builds its own logic from the ground up using simple rules of triangles and numbers.

In a nutshell:
Delahan said, "These giant structures contain every small shape."
Chappelon said, "Here is a simple, elegant key that proves it. If you know the right few spots in the giant structure, you can mathematically reconstruct any shape you want hidden inside it."

This new proof is shorter, clearer, and gives us a better "feel" for why these mathematical structures are so incredibly powerful and universal.

Technical Summary

Here is a detailed technical summary of the paper "A new proof of Delahan's induced-universality result" by Jonathan Chappelon.

1. Problem Statement

The paper addresses a fundamental question in the theory of Steinhaus graphs: To what extent can these graphs represent arbitrary simple graphs?

• Context: A Steinhaus graph of order $n$ is a simple graph whose adjacency matrix's upper-triangular part forms a Steinhaus triangle of size $n-1$. A Steinhaus triangle is a binary triangle generated by a local rule similar to Pascal's triangle modulo 2 ($a_{i,j} \equiv a_{i-1,j} + a_{i-1,j+1} \pmod 2$).
• The Core Problem: Delahan (2024) previously proved that the family of Steinhaus graphs of order $t_{n-1} + 1$ (where $t_k = k(k+1)/2$ is the $k$-th triangular number) is $n$-induced-universal. This means that every simple graph on $n$ vertices appears as an induced subgraph of some Steinhaus graph of that specific size.
• Goal: The author aims to provide a short, self-contained, and constructive proof of Delahan's theorem, moving away from the original isomorphism-based approach by utilizing the algebraic properties of generating index sets.

2. Methodology

The proof relies on linear algebra over the field $\mathbb{Z}/2\mathbb{Z}$ and combinatorial properties of binomial coefficients. The methodology proceeds in three main stages:

A. Generating Index Sets

The author introduces the concept of a generating index set for the vector space of Steinhaus triangles $ST(n)$.

• Since $ST(n)$ has dimension $n$, a subset of indices $A \subset T_n$ is a generating set if knowing the values $\{a_{i,j} \mid (i,j) \in A\}$ uniquely determines the entire triangle.
• Proposition 2.2: A set $A$ is a generating index set if and only if the associated matrix $M_A$, formed by binomial coefficients derived from the indices, is invertible modulo 2.
  $$(M_A)_{k,\ell} = \binom{i_k}{\ell - j_k}$$
  where $(i_k, j_k)$ are the elements of $A$.

B. Analysis of Binomial Minors

The paper investigates the determinants of specific submatrices of the infinite binomial matrix $B = \binom{i}{j}$.

• Proposition 3.1: Establishes a formula for the determinant of a binomial matrix with rows $a_1, \dots, a_n$ and columns $0, \dots, n-1$. It relates this determinant to the **Vandermonde determinant**$\Delta(a_1, \dots, a_n) = \prod_{i<j} (a_j - a_i)$ divided by factorials.
• Proposition 3.2: Applies this to the specific case where the row indices are the first $n$ triangular numbers ($t_0, t_1, \dots, t_{n-1}$). The author proves that the determinant of this specific matrix is a product of odd integers:
  $$\det B \left[ \begin{matrix} t_0, \dots, t_{n-1} \\ 0, \dots, n-1 \end{matrix} \right] = \prod_{i=1}^{n-1} (2i-1)^{n-i}$$
  Crucial Result: Since the product consists only of odd numbers, the determinant is odd, implying the matrix is invertible modulo 2.

C. Block Matrix Construction

The proof constructs a specific set of indices $A_n$ designed to extract the induced subgraph.

• Theorem 4.1: The set $A_n = \{(t_s, t_{r+1} - t_s - 1) \mid 0 \le s \le r \le n-2\}$ is a generating index set for $ST(t_{n-1})$.
• Lemma 4.2: The matrix $M_{A_n}$ associated with this set is shown to be a block lower-triangular matrix. The diagonal blocks correspond to the binomial matrices analyzed in Proposition 3.2 (specifically, blocks of size $1, 2, \dots, n-1$).
• Since all diagonal blocks have odd determinants (are invertible mod 2), the entire matrix $M_{A_n}$ is invertible mod 2.

3. Key Contributions

1. New Proof of Delahan's Theorem: The paper provides a rigorous, self-contained proof that the family of Steinhaus graphs of order $t_{n-1} + 1$ is $n$-induced-universal.
2. Introduction of Generating Index Sets: It formalizes the notion of generating index sets for Steinhaus triangles, linking the combinatorial structure of the triangle to the invertibility of binomial matrices.
3. Explicit Construction: Unlike abstract existence proofs, this approach identifies a specific set of indices ($A_n$) that allows the reconstruction of any $n$-vertex graph from a Steinhaus graph of size $t_{n-1} + 1$.
4. Combinatorial Determinant Identity: It derives and utilizes a specific identity showing that binomial matrices formed by triangular numbers have odd determinants, a result of independent combinatorial interest.

4. Results

• Main Theorem (Theorem 1.1): For any positive integer $n$, the linear map from the space of Steinhaus graphs of order $t_{n-1} + 1$ to the set of simple graphs on $n$ vertices (via induced subgraphs on the vertex set $W_n = \{t_i + 1 \mid 0 \le i \le n-1\}$) is an isomorphism.
• Corollary: Every simple graph on $n$ vertices is isomorphic to an induced subgraph of a Steinhaus graph on $t_{n-1} + 1$ vertices.
• Structural Insight: The proof demonstrates that the "upper-triangular part" of the adjacency matrix of the induced subgraph corresponds exactly to the values of the Steinhaus triangle at the indices in the generating set $A_n$.

5. Significance

• Universality in Combinatorics: The result confirms that Steinhaus graphs, despite being generated by a simple local rule (Pascal's triangle mod 2), are structurally rich enough to contain all possible simple graphs of a given size as induced subgraphs.
• Algebraic Approach: The paper shifts the perspective from purely combinatorial enumeration to linear algebra over finite fields. By characterizing universality through the invertibility of binomial matrices, it opens new avenues for studying structural properties of Steinhaus objects.
• Efficiency: The proof is described as "short and self-contained," offering a more accessible route to Delahan's result compared to previous methods, potentially facilitating further research into the embedding properties of other recursively defined graph families.
• Applications: Understanding the universality of Steinhaus graphs has implications for graph encoding, network design, and the study of cellular automata (as Steinhaus triangles are essentially 1D cellular automata traces).

In summary, Chappelon's paper elegantly resolves the induced-universality of Steinhaus graphs by proving that a specific selection of indices in a large Steinhaus triangle forms a basis for the space of all possible $n$-vertex graphs, leveraging the oddness of determinants involving triangular numbers.