Set systems with distinct sumsets
| Autor: | Oriol Serra, Maximilian Wötzel, Javier Cilleruelo |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics |
| Rok vydání: | 2018 |
| Předmět: |
Combinatorial analysis
Applied Mathematics 010102 general mathematics distinct sumsets Matemàtiques i estadística::Matemàtica discreta::Combinatòria [Àrees temàtiques de la UPC] 010103 numerical & computational mathematics 01 natural sciences Upper and lower bounds Combinatorics Set (abstract data type) 60 Probability theory and stochastic processes::60C05 Combinatorial probability [Classificació AMS] Threshold probability Combinacions (Matemàtica) Random systems Matemàtiques i estadística::Probabilitat [Àrees temàtiques de la UPC] Combinatorial probabilities additive combinatorics Probabilitats Discrete Mathematics and Combinatorics Cardinality (SQL statements) 05 Combinatorics::05E Algebraic combinatorics [Classificació AMS] 0101 mathematics Sidon sets Mathematics |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Recercat. Dipósit de la Recerca de Catalunya instname |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2018.06.004 |
| Popis: | A family A of k-subsets of { 1 , 2 , … , N } is a Sidon system if the sumsets A + A ′ , A , A ′ ∈ A are pairwise distinct. We show that the largest cardinality F k ( N ) of a Sidon system of k-subsets of [ N ] satisfies F k ( N ) ≤ ( N − 1 k − 1 ) + N − k and the asymptotic lower bound F k ( N ) = Ω k ( N k − 1 ) . More precise bounds on F k ( N ) are obtained for k ≤ 3 . We also obtain the threshold probability for a random system to be Sidon for k = 2 and 3. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect