Abstract | ||
---|---|---|
Given a finite n-element set X, a family of subsets F ź 2 X is said to separate X if any two elements of X are separated by at least one member of F . It is shown that if | F | 2 n - 1 , then one can select ź log ź n ź + 1 members of F that separate X. If | F | ź α 2 n for some 0 |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.jcta.2016.06.002 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
Search theory,Separation,VC-dimension,Erdős–Szekeres theorem | Family of sets,Discrete mathematics,VC dimension,Combinatorics,Regular polygon,Mathematics,Bounded function,Erdős–Szekeres theorem | Journal |
Volume | Issue | ISSN |
144 | C | 0097-3165 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zsolt Langi | 1 | 7 | 2.53 |
Marton Naszodi | 2 | 21 | 7.87 |
János Pach | 3 | 2366 | 292.28 |
Gábor Tardos | 4 | 1261 | 140.58 |
Géza Tóth | 5 | 72 | 9.25 |