Baranyai's Theorem

Let's talk about perfect hypergraph matchings

En JavaScript. Parce que LaTeX, ça va 5 minutes.

Perfect Matchings in Hypergraphs

 Disjoint sets Covering all vertices Not necessarily uniform

Perfect matchings in $\binom {[n]} 2$

$\binom {[n]} 2$ can be partitionned into perfect matchings
when $n$ is even.

What about $\binom {[n]} 3$ ?

Partition of $\binom {[6]} {3}$ into partitions of size 2
Peltesohn (1963) If 3 divides $n$, then $\binom {[n]} 3$ admits a decomposition into perfect matchings
... so what about $\binom {[n]} k$ ?

Partitions of $\binom {[n]} k$ into perfect matchings

Sylverster (Conjecture, 1857)If $k$ divides $n$, then $\binom {[n]} k$ admits a decomposition into perfect matchings
~120 years later, Jean-Claude Bermond
shares it with Zsolt Baranyai ...

... who proves it in 2 pages,
with a recurrence and a max flow.

Let us consider a decomposition ...

All sets of $\binom {[n]} 3$

Let us consider a decomposition ...

All sets of $\binom {[n]} 3$

Let us consider a decomposition ...

All sets of $\binom {[n-1]} 3 \bigcup\binom {[n-1]} 2$

Let us consider a decomposition ...

All sets of $\binom {[n-1]} 3 \bigcup\binom {[n-1]} 2$

Let us consider a decomposition ...

$\binom {[n-2]} 3 \bigcup {\scriptsize 2 \times} \binom {[n-2]} 2 \bigcup\binom {[n-2]} 1$
Every partition of $[n]$ has a type.

Baranyai (1975) Let $\alpha_{ij}$ be a $r\times s$ matrix and $t$ a vector such that:
• $\sum_j t_j \alpha_{ij}=n\phantom{\binom {n} {t_j}}$ for every $i$
• $\sum_i \phantom{t_j} \alpha_{ij}=\binom {n} {t_j}\phantom{n}$ for every $j$
Then each cell $\alpha_{ij}$ corresponds to $\alpha_{ij}$ sets such that:
• Every row is a partition of $[n]$
• Every column $j$ is a partition of $\binom {[n]} {t_j}$
In particular, $\binom {[n]} {k}$ admits a partition into partitions of $[n]$
whenever $k$ divides $n$
Sketch of the proof:

• Take a feasible decomposition profile (i.e. $M$ and $t$)
for $[n]$
• In each partition, decrease by 1 the size of one set
(that set will contain $n$ later)
• Deduce a feasible decomposition profile for $[n-1]$
• Compute by induction the sets of the decomposition
• Add a new point $n$ to the previously reduced sets

Where does point $n$ appear in a decomposition profile ?

 $\alpha_{1,1}$ $\cdots$ $\alpha_{1,j}$ $\cdots$ $\alpha_{1,s}$ $\vdots$ $\vdots$ $\vdots$ $\alpha_{1,1}$ $\cdots$ $\alpha_{1,j}$ $\cdots$ $\alpha_{1,s}$ $\vdots$ $\vdots$ $\vdots$ $\alpha_{r,1}$ $\cdots$ $\alpha_{r,j}$ $\cdots$ $\alpha_{r,s}$ =$\binom {n} {t_1}$ =$\binom {n} {t_j}$ =$\binom {n} {t_s}$
• Once per line, in a cell with $\alpha_{ij}>0$
• $\binom {n-1} {t_j-1}$ times in a column of sum $\binom {n} {t_j}$
$\Rightarrow$ An integral flow is feasible $\Leftarrow$

 Graph - An edge $P_iC_j$ if $\alpha_{ij}$>0   with capacity 1 Flow - $P_i$ sends $\frac {\alpha_{ij}t_j}{n}$ to $C_j$ - $P_i$ sends $\frac {\sum_j \alpha_{ij}t_j}{n}=1$ - $C_j$ gets $\frac {t_j} n \binom {n}{t_j}$=$\binom {n-1} {t_j-1}$
There exists a decomposition profile for $n-1$ ...

... and we can extend it with a new point!

That's it for Baranyai

But there is another thing I want to tell you.

Difference Set

It is a BIBD with a an automorphism of order $v$.
$\mathbb Z_7,\{0, 1, 3\}$
$\mathbb Z_{13},\{0, 1, 11, 5\}$
$\mathbb Z_{21}, \{0, 1, 4, 14, 16\}$
It is a $k$-subset of $\mathbb Z_v$ in which every distance
occurs $\lambda$ times.
A cool trick (from Alon)
• Ingredients: a graph $H$
• Goal: a regular graph $G$ that decomposes into $H$

• Solution:
• Take a large difference set
• Draw $H$ inside one block
• Let the automorphism group act
• Keep only the edges covered by copies of $H$

Desarguesian Projective Planes

Let $q$ be a prime power.

We look at the 1- and 2-dimensional subspaces of $\mathbb F_q^3$.

• Dimension 1: a total of $q^2+q+1=\frac {q^3-1}{q-1}$
Every line has $q-1$ nonzero elements

• Dimension 2: again $q^2+q+1$
Each is orthogonal to a 1-space

Incidences

• Any two 1-spaces are contained in a unique 2-space
• A 2-space contains $\frac {q^2-1}{q-1}$=$q+1$ different 1-spaces
That is a $(q^2+q+1,q+1,1)$-BIBD
That is a projective plane
Difference Sets and projective planes

Singer (1938)A Desarguesian projective plane on $[v]$ has an automorphism of order $v$

Proof: $\mathbb F_{q^3}$ is a 3-dimensional space over $\mathbb F_q$. It has:

• $q^2+q+1$ spaces of dim 1: $L_1,L_2,\dots$
• $q^2+q+1$ spaces of dim 2: $P_1,P_2,\dots$
• a primitive element $\omega\in \mathbb F_{q^3}$, so that $\mathbb F_{q^3}=\{0,\omega,\omega^2,\omega^3,\dots\}$
All in all ...

• $\omega,\omega^2,\omega^3,\dots$
goes through all nonzero elements of $\mathbb F_{q}^3$
• $L_1,\omega L_1,\omega^2 L^1,\omega^3 L^1,\dots$
goes through all 1-spaces of $\mathbb F_{q}^3$
• $\omega P_i\in \{P_1,\dots\}$
Multiplication by $\omega$ preserves 2-spaces

It is an automorphism of order $v=q^2+q+1$
$\square$

(Thanks)