Random Sidon sequences (Q1283038): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 10:16, 31 January 2024

scientific article
Language Label Description Also known as
English
Random Sidon sequences
scientific article

    Statements

    Random Sidon sequences (English)
    0 references
    0 references
    0 references
    0 references
    26 May 1999
    0 references
    Consider a subset \(A\) chosen randomly from the \( n \choose k_n\) subsets of size \(k_n\) of \([1, 2,\dots, n]\). The paper investigates the probability that such a set has the \(B_h\) property, that is, whether the sums of \(h\) elements of \(A\) are all distinct. It is proved that if \(k_n/n^{1/2h} \rightarrow \Lambda \) as \(n \rightarrow \infty \), then this probability tends to \( \exp \bigl( -\kappa _h \Lambda ^{2k} \bigr) \) with certain positive constants \(\kappa _h\). In particular, if \(k_n/n^{1/2h} \rightarrow 0\), then almost all sets have the \(B_h\) property, and if \(k_n/n^{1/2h} \rightarrow \infty \), then almost all do not have it. The proofs are based on Janson's inequality and the Stein-Chen approximation for positively related random variables.
    0 references
    0 references
    Sidon sets
    0 references

    Identifiers