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

DOI10.1016/J.EJC.2019.05.005zbMATH Open1458.05252arXiv1810.01225OpenAlexW2947265299MaRDI QIDQ2323091FDOQ2323091

Authors: Jason Long, Adam Zsolt Wagner 

Publication date: 30 August 2019

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

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.

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

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

zbMATH Keywords

Samotij's theorem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• The largest $(k,\ell )$-sum-free subsets

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)