Pith. sign in

REVIEW 1 cited by

Maximal independent sets in the middle two layers of the Boolean lattice

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2505.00132 v1 pith:6JA2EPWD submitted 2025-04-30 math.CO

classification math.CO
keywords independentmaximalsetsnumberasymptoticsbinomkahnlayers
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Let $B(2d-1, d)$ be the subgraph of the hypercube $\mathcal{Q}_{2d-1}$ induced by its two largest layers. Duffus, Frankl and R\"odl proposed the problem of finding the asymptotics for the logarithm of the number of maximal independent sets in $B(2d-1, d)$. Ilinca and Kahn determined the logarithmic asymptotics and reiterated the question of what their order of magnitude is. We show that the number of maximal independent sets in $B(2d-1,d)$ is \[ \left(1+o(1)\right)(2d-1)\exp\left(\frac{(d-1)^2}{2^{2d-1}}\binom{2d-2}{d-1}\right)\cdot 2^{\binom{2d-2}{d-1}}, \] and describe their typical structure. The proof uses a new variation of Sapozhenko's Graph Container Lemma, a new isoperimetric lemma, a theorem of Hujter and Tuza on the number of maximal independent sets in triangle-free graphs and a stability version of their result by Kahn and Park, among other tools.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Range of random $\mathbb Z$-homomorphisms on weak expanders

    math.CO 2026-04 unverdicted novelty 7.0 of 10

    Random Z-homomorphisms on weak expanders are O(log log n)-flat with high probability, answering a question of Peled-Samotij-Yehudayoff, and at most 5-valued on Hamming-cube middle layers.

Pith tools