On the VC-dimension of uniform hypergraphs
Dhruv Mubayi1
and Yi Zhao2
1University of Illinois Department of Mathematics, Statistics, and Computer Science Chicago IL USA 60607 Chicago IL USA 60607
2Georgia State University Department of Mathematics and Statistics Atlanta GA USA 30303 Atlanta GA USA 30303
2Georgia State University Department of Mathematics and Statistics Atlanta GA USA 30303 Atlanta GA USA 30303
DOI: 10.1007/s10801-006-0025-4
Abstract
Let F {\cal F} be a k-uniform hypergraph on [ n] where k - 1 is a power of some prime p and n\geq n 0( k). Our main result says that if $|F|> ({n\atop k-1}) -\log_p n + k!k^k $ |F|> ({n\atop k-1}) -\log_p n + k!k^k , then there exists E 0ϵ F {\cal F} such that { E\cap E 0: Eϵ F {\cal F}} contains all subsets of E 0. This improves a longstanding bound of ([( n) || ( k -1)]) ({n\atop k-1}) due to Frankl and Pach [7].
Pages: 101–110
Keywords: keywords trace; hypergraph; VC-dimension; extremal problems
Full Text: PDF
References
1. R. Ahlswede and L.H. Khachatrian, “Counterexample to the Frankl-Pach conjecture for uniform, dense families,” Combinatorica 17(2) (1997), 299-301.
2. N. Alon, L. Babai, and H. Suzuki, “Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems,” J. Combin. Theory Ser. A 58(2) (1991), 165-180.
3. L. Babai and P. Frankl, Linear Algebra Method in Combinatorics, preliminary version 2, University of Chicago, 1992.
4. A. Blokhuis, “A new upper bound for the cardinality of 2-distance sets in Euclidean space,” Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., 87, North-Holland, Amsterdam, 1984, pp. 65-66. Springer J Algebr Comb (2007) 25:101-110
5. P. Erd\Acute\Acute os, C. Ko, and R. Rado, “Intersection theorems for systems of finite sets,” Quart. J. Math. Oxford Ser. 12(2) (1961), 313-320.
6. P. Erd\Acute\Acute os and R. Rado, “Intersection theorems for systems of sets,” J. London Math. Soc. 35 (1960), 85-90.
7. P. Frankl and J. Pach, “On disjointly representable sets,” Combinatorica 4 (1984), 39-45.
8. K. Friedl and L. Rónyai, “Order shattering and Wilson's theorem,” Discrete Math. 270(1-3) (2003), 127-136.
9. Z. F\ddot uredi and J. Pach, “Traces of finite sets: extremal problems and geometric applications,” Extremal Problems for Finite Sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, János Bolyai Math. Soc., Bu- dapest, 1994, pp. 251-282.
10. N. Sauer, “On the density of families of sets,” J. Combinatorial Theory Ser. A 13 (1972), 145-147.
11. S. Shelah, “A combinatorial problem; stability and order for models and theories in infinitary languages,” Pacifc J. Math. 41 (1972), 247-261.
12. V.N. Vapnik and A. Ya Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” Theory Probab. Appl. 16 (1971), 264-280.
2. N. Alon, L. Babai, and H. Suzuki, “Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems,” J. Combin. Theory Ser. A 58(2) (1991), 165-180.
3. L. Babai and P. Frankl, Linear Algebra Method in Combinatorics, preliminary version 2, University of Chicago, 1992.
4. A. Blokhuis, “A new upper bound for the cardinality of 2-distance sets in Euclidean space,” Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., 87, North-Holland, Amsterdam, 1984, pp. 65-66. Springer J Algebr Comb (2007) 25:101-110
5. P. Erd\Acute\Acute os, C. Ko, and R. Rado, “Intersection theorems for systems of finite sets,” Quart. J. Math. Oxford Ser. 12(2) (1961), 313-320.
6. P. Erd\Acute\Acute os and R. Rado, “Intersection theorems for systems of sets,” J. London Math. Soc. 35 (1960), 85-90.
7. P. Frankl and J. Pach, “On disjointly representable sets,” Combinatorica 4 (1984), 39-45.
8. K. Friedl and L. Rónyai, “Order shattering and Wilson's theorem,” Discrete Math. 270(1-3) (2003), 127-136.
9. Z. F\ddot uredi and J. Pach, “Traces of finite sets: extremal problems and geometric applications,” Extremal Problems for Finite Sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, János Bolyai Math. Soc., Bu- dapest, 1994, pp. 251-282.
10. N. Sauer, “On the density of families of sets,” J. Combinatorial Theory Ser. A 13 (1972), 145-147.
11. S. Shelah, “A combinatorial problem; stability and order for models and theories in infinitary languages,” Pacifc J. Math. 41 (1972), 247-261.
12. V.N. Vapnik and A. Ya Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” Theory Probab. Appl. 16 (1971), 264-280.