The largest projective cube-free subsets of Z₂^n

DOI10.1016/J.EJC.2019.05.005MaRDI QIDQ2323091zbMATHOpenAlexFDO

Authors Jason Long, Adam Zsolt Wagner

Publication date 30 August 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.01225

zbMATH Keywords

Samotij's theorem

Mathematics Subject Classification ID

Extremal set theory (05D05) Ramsey theory (05D10) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: In the Boolean lattice, Sperner's, ErdH{o}s's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $mathbb{Z}_2^n$ we work in $mathbb{Z}_{2^n}$, several analogous statements hold if one replaces the word $k$-chain by projective cube of dimension $2^{k-1}$. We say that $B_d$ is a projective cube of dimension $d$ if there are numbers $a_1,a_2,ldots,a_d$ such that ${\displaystyle }$B_d = left{sum_{iin I} a_i �igg vert emptyset eq Isubseteq [d] ight}.${\displaystyle }$ As an analog of Sperner's and ErdH{o}s's theorems, we show that whenever $d=2^{ell}$ is a power of two, the largest $d$-cube free set in $mathbb{Z}_{2^n}$ is the union of the largest $ell$ layers. As an analog of Kleitman's theorem, Samotij and Sudakov asked whether among subsets of $mathbb{Z}_{2^n}$ of given size $M$, the sets that minimize the number of Schur triples (2-cubes) are those that are obtained by filling up the largest layers consecutively. We prove the first non-trivial case where $M=2^{n-1}+1$, and conjecture that the analog of Samotij's theorem also holds. Several open questions and conjectures are also given.

Recommendations

• On sumfree subsets of hypercubes
• Some Ramsey-type results for the \(n\)-cube
• On combinatorial cubes
• Irredundant families of subcubes
• Extremal Problems for Affine Cubes of Integers

Cites work

• scientific article; zbMATH DE number 3823861 (Why is no real title available?)
• scientific article; zbMATH DE number 3456942 (Why is no real title available?)
• scientific article; zbMATH DE number 3256524 (Why is no real title available?)
• Extremal Problems for Affine Cubes of Integers
• Monochromatic Hilbert cubes and arithmetic progressions
• On a lemma of Littlewood and Offord
• On saturated \(k\)-Sperner systems
• On sums of subsets of a set of integers
• On two additive problems
• Saturating Sperner families
• Studien zur Kombinatorik
• Subset sums
• Subsets of posets minimising the number of chains
• The maximum number of disjoint pairs in a family of subsets
• The number of additive triples in subsets of abelian groups

Cited in

(2)

• The largest $(k,\ell )$-sum-free subsets
• Extremal set theory, cubic forms on \(\mathbb F_{2}^{n}\) and Hurwitz square identities

Describes a project that uses

Uses Software

• Gurobi

This page was built for publication: The largest projective cube-free subsets of \(\mathbb{Z}_{2^n}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2323091)