Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652132 | Electronic Notes in Discrete Mathematics | 2013 | 4 Pages |
We present a unified framework to deal with threshold functions for the existence of certain combinatorial structures in random sets. More precisely, let M⋅x=0 be a linear system defining a fixed structure (k-arithmetic progressions, k-sums, Bh[g] sets or Hilbert cubes, for example), and A be a random set on 1,…,n where each element is chosen independently with the same probability.We show that, under certain natural conditions, there exists a threshold function for the property “Am contains a non-trivial solution of M⋅x=0” which only depends on the dimensions of M. We study the behavior of the limiting distribution of the number of non-trivial solutions in the threshold scale, and show that it follows a Poisson distribution in terms of volumes of certain convex polytopes arising from the linear system under study.