On the VC-dimension of uniform hypergraphs |
| |
Authors: | Dhruv Mubayi Yi Zhao |
| |
Affiliation: | (1) Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL USA, 60607;(2) Department of Mathematics and Statistics, Georgia State University, Atlanta, GA USA, 30303 |
| |
Abstract: | Let be a k-uniform hypergraph on [n] where k−1 is a power of some prime p and n≥ n 0(k). Our main result says that if , then there exists E 0∊ such that {E∩ E 0: E∊ } contains all subsets of E 0. This improves a longstanding bound of due to Frankl and Pach [7].Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship.Research supported in part by NSA grant H98230-05-1-0079. Part of this research was done while working at University of Illinois at Chicago. |
| |
Keywords: | Trace Hypergraph VC-dimension Extremal problems |
本文献已被 SpringerLink 等数据库收录! |
|