On the VC-dimension of uniform hypergraphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

On the VC-dimension of uniform hypergraphs

Authors:	Dhruv Mubayi Yi Zhao

Institution:	(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 ${\cal F}$ be a k-uniform hypergraph on n] where k−1 is a power of some prime p and n≥ n ₀(k). Our main result says that if $\|F\|> ({n\atop k-1}) -\log_p n + k!k^k$ , then there exists E ₀∊ ${\cal F}$ such that {E∩ E ₀: E∊ ${\cal F}$ } contains all subsets of E ₀. This improves a longstanding bound of $({n\atop k-1})$ 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 等数据库收录！