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$

The End

(Thanks)