(2,1)-separating systems beyond the probabilistic bound

Details (2,1)-separating systems beyond the probabilistic bound (2,1)-separating systems beyond the probabilistic bound

2010-10-27

arxiv.org/abs/1010.5764v7

Mathematics

Combinatorics

Version 7 is a shortened version, so that numbering should match with the journal version (to appear soon). Material on convex

Scientific paper

Building on previous results of Xing, we give new lower bounds on the rate of intersecting codes over large alphabets. The proof is constructive, and uses algebraic geometry, although nothing beyond the basic theory of linear systems on curves. Then, using these new bounds within a concatenation argument, we construct binary (2,1)-separating systems of asymptotic rate exceeding the one given by the probabilistic method, which was the best lower bound available up to now. This answers (negatively) the question of whether this probabilistic bound was exact, which has remained open for more than 30 years. (By the way, we also give a formulation of the separation property in terms of metric convexity, which may be an inspirational source for new research problems.)

Affiliated with

Also associated with

No associations

Rating

(2,1)-separating systems beyond the probabilistic bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with (2,1)-separating systems beyond the probabilistic bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (2,1)-separating systems beyond the probabilistic bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-486138