Bounds for generalized Sidon sets

DOI10.1016/J.DISC.2014.11.006MaRDI QIDQ482225zbMATH OpenOpenAlexFDO

Authors Xing Peng, Rafael Tesoro, Craig Timmons

Publication date 19 December 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

generalized Sidon setsnorm graphsSidon setsZarankiewicz problem

Mathematics Subject Classification ID

Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Other combinatorial number theory (11B75)

Abstract: Let $Gamma$ be an abelian group and $ggeqhgeq2$ be integers. A set $AsubsetGamma$ is a $C_h[g]$-set if given any set $XsubsetGamma$ with $|X|=k$, and any set $k_1,dots,k_{g}subsetGamma$, at least one of the translates $X+k_i$ is not contained in $A$. For any $ggeqhgeq2$, we prove that if $Asubset1,2,dots,n$ is a $C_h[g]$-set in $mathbbZ$, then $|A|leq(g-1{)}^{1/h}{n}^{1-1/h}+O(n^{1/2-1/2h})$. We show that for any integer $ngeq1$, there is a $C_3[3]$-set $Asubset1,2,dots,n$ with $|A|geq(4^{-2/3}+o(1))n^{2/3}$. We also show that for any odd prime $p$, there is a $C_3[3]$-set $Asubsetmathbb{F}_p^3$ with $|A|geq{p}^2-p$, which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer $hgeq3$, there is a $C_h[h!+1]$-set $Asubset1,2,dots,n$ with $|A|geq(c_h+o(1))n^{1-1/h}$. A set $A$ is a emph{weak $C_h[g]$-set} if we add the condition that the translates $X+k_1,dots,X+k_g$ are all pairwise disjoint. We use the probabilistic method to construct weak $C_h[g]$-sets in $1,2,dots,n$ for any $ggeqhgeq2$. Lastly we obtain upper bounds on infinite $C_h[g]$-sequences. We prove that for any infinite $C_h[g$]-sequence $AsubsetmathbbN$, we have $A(n)=O(n^{1-1/h}(logn{)}^{-1/h})$ for infinitely many $n$, where $A(n)=|Acap1,2,dots,n|$.

Recommendations

• Constructions of generalized Sidon sets.
• scientific article; zbMATH DE number 795113
• Sidon Sets
• On strong infinite Sidon and \(B_h\) sets and random sets of integers
• On sum sets of Sidon sets. II

Cites work

• An overlapping theorem with applications
• An Upper Bound on Zarankiewicz' Problem
• scientific article; zbMATH DE number 1571509 (Why is no real title available?)
• scientific article; zbMATH DE number 3126645 (Why is no real title available?)
• scientific article; zbMATH DE number 5652361 (Why is no real title available?)
• scientific article; zbMATH DE number 3918485 (Why is no real title available?)
• scientific article; zbMATH DE number 795113 (Why is no real title available?)
• Norm-graphs and bipartite Turán numbers
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On Graphs that do not Contain a Thomsen Graph
• Probabilistic constructions of \(B_2[g]\) sequences
• Sidon sets in \(\mathbb N^d\)
• The difference between consecutive primes. II
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(1)

• On Sidon sets and asymptotic bases

This page was built for publication: Bounds for generalized Sidon sets

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