google-deepmind / google-deepmind/formal-conjectures

Add the Shearer–Kleitman conjecture on orthogonal symmetric chain decompositions

Open
#5,273 0 comments 0 reactions 0 assignees View on GitHub
new conjecture
Dominant language
Lean
Stars
1.3k
Forks
485
Avg merge
1d 20h
Merged PRs (30d)
327

Description

### What is the conjecture

The n-cube is the poset of all subsets of `{1, …, n}` ordered by inclusion. It can be partitioned into `binom(n, ⌊n/2⌋)` chains, which is the minimum possible number (the width of the poset, by Sperner's theorem). A partition into that many *symmetric* chains (each chain spanning levels symmetric about the middle) is a symmetric chain decomposition (SCD). Two SCDs are called orthogonal if any chain of the one and any chain of the other share at most a single element.

The Shearer–Kleitman conjecture (1979) states that the n-cube has `⌊n/2⌋ + 1` pairwise orthogonal symmetric chain decompositions. Shearer and Kleitman constructed two of them. The best known bounds are four pairwise orthogonal SCDs for `n ≥ 60` and five pairwise edge-disjoint ones for `n ≥ 90`, due to Däubel, Jäger, Mütze and Scheucher. The conjecture is still open.

References:
- J. B. Shearer and D. J. Kleitman, *Probabilities of independent choices being ordered*, Studies in Applied Mathematics 60 (1979), 271–276.
- R. Däubel, S. Jäger, T. Mütze and M. Scheucher, [*On orthogonal symmetric chain decompositions*](https://doi.org/10.37236/8531), Electronic Journal of Combinatorics 26(3) (2019), no. P3.64.
- [Symmetric chain decomposition (Wikipedia)](https://en.wikipedia.org/wiki/Symmetric_chain_decomposition)

### Prerequisites needed

None beyond the statement itself. The formalization is purely combinatorial (subsets of `Fin n` as `Finset`, chains, and decompositions), so no addition to `FormalConjecturesForMathlib` and no open Mathlib dependency are needed.

### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)

* ams-05 Combinatorics
* ams-06 Order, lattices, ordered algebraic structures

### Choose either option
- [x] I plan on adding this conjecture to the repository
- [ ] This issue is up for grabs: I would like to see this conjecture added by somebody else

Contributor guide

Open the contributing guide

Research direction

Use the conjecture statement and listed references as the specification; the payload names no repository files, tests, or entry points. Done means adding the Shearer–Kleitman conjecture as a Lean formal statement, including the definitions needed for subsets, chains, symmetric chain decompositions, and orthogonality.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.