On sums of distinct representatives
A finite sequence \(\{A_i\}^n_{i=1}\) of sets is said to have a system of distinct representatives (SDR) \(\{a_i\}^n_{i=1}\) if \(a_i\in A_i\) for each \(i\) and \(a_i\neq a_j\) for \(i\neq j\). A famous theorem of P. Hall asserts that such a SDR exists iff \(|\cup_{i\in I} A_i| \geq| I|\) for all \(I\subseteq \{1,\dots, n\}\). Now let \(A_1, \dots,A_n\) be the subsets of any additive abelian group \(G\). With each SDR \(\{a_i\}\) of \(\{A_i\}\), define \(S(A_1, \dots,A_n)= \{a_1+ \cdots+a_n\}\). The authors consider the problem of determining sharp lower bounds for \(S(A_1, \dots,A_n)\) given that at least one SDR is guaranteed to exist by Hall's theorem. Let \(A_1,\dots,A_n\) be finite subsets of \(\mathbb{Z}\) with \(0<| A_1| <\cdots <| A_n|\). By applying a general result of \textit{N. Alon}, \textit{M. Nathanson} and \textit{I. Ruzsa} [J. Number Theory 56, 404-417 (1996; Zbl 0861.11006)], one obtains that \[ \bigl| S(A_1,\dots,A_n) \bigr|\geq \sum^n_{i=1} \bigl(| A_i |- i\bigr)+1. \] The authors give a new constructive proof of this result and discuss cases where equality is achieved.
- scientific article; zbMATH DE number 3997795
- On the supremum of the representation function of a sumset
- Infinite sumsets with many representations
- On the number of sums and differences
- Variations on the Erdős distinct-sums problem
- A note on sumsets and restricted sumsets
- On the structure of the \(h\)-fold sumsets
- Lower bounds on multiple distinct sum sets
- A conjecture on the number of SDRs of a \((t,n)\)-family
- scientific article; zbMATH DE number 2147936
- On the number of SDR of a (t,n)-family
- The Helly bound for singular sums
- Hall's theorem revisited
- A note on system of distinct representatives
- A Generalization of Distinct Representatives and Its Applications
- Counting common representatives and symmetric chain decompositions
- On the representation of integers as sums of distinct terms from a fixed set
This page was built for publication: On sums of distinct representatives
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4236022)
