Name
Abstract | ||
|---|---|---|
We show that, for a positive integer $r$, every minimal 1-saturating set in ${PG}(r-1,2)$ of size at least $\frac{11}{36}\,2^r+3$ either is a complete cap or can be obtained from a complete cap $S$ by fixing some $s\in S$ and replacing every point $s'\in S\setminus\{s\}$ by the third point on the line through $s$ and $s'$. Since, conversely, every set obtained in this way is a minimal 1-saturating set and the structure of large sum-free sets in an elementary abelian 2-group is known, this provides a complete description of large minimal 1-saturating sets. An algebraic restatement is as follows. Suppose that $G$ is an elementary abelian 2-group and a subset $A\subseteq G\setminus\{0\}$ satisfies $A\cup2A=G$ and is minimal subject to this condition. If $|A|\ge\frac{11}{36}\,|G|+3$, then either $A$ is a maximal sum-free set or there are a maximal sum-free set $S\subseteq G$ and an element $s\in S$ such that $A=\{s\}\cup\bigl(s+(S\setminus\{s\})\bigr)$. Our approach is based on characterizing those large sets $A$ in elementary abelian 2-groups such that, for every proper subset $B$ of $A$, the sumset $2B$ is a proper subset of $2A$. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/090747099 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
maximal sum-free set,1-saturating sets,large set,proper subset,1-saturating set,subseteq g,large sum-free set,complete cap,elementary abelian,minimal subject,binary spaces,doubling-critical sets,complete description,cap,blocking set | Integer,Abelian group,Discrete mathematics,Blocking set,Combinatorics,Algebraic number,Sum-free set,Sumset,Mathematics,Binary number | Journal |
Volume | Issue | ISSN |
24 | 1 | 0895-4801 |
Citations | PageRank | References |
2 | 0.49 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Grynkiewicz | 1 | 42 | 10.33 |
| Vsevolod F. Lev | 2 | 37 | 17.97 |