Premium
The VC dimension of k ‐uniform random hypergraphs
Author(s) -
Ycart B.,
Ratsaby J.
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20142
Subject(s) - combinatorics , cardinality (data modeling) , mathematics , intersection (aeronautics) , dimension (graph theory) , hypergraph , integer (computer science) , packing dimension , function (biology) , dimension function , discrete mathematics , vc dimension , set (abstract data type) , hausdorff dimension , minkowski–bouligand dimension , computer science , mathematical analysis , fractal dimension , fractal , evolutionary biology , biology , engineering , data mining , programming language , aerospace engineering
A set of vertices is shattered in a hypergraph if any of its subsets is obtained as the intersection of an edge with the set. The VC dimension is the size of the largest shattered subset. Under the binomial model of k ‐uniform random hypergraphs, the threshold function for the VC dimension to be larger than a given integer is obtained. The same is done for the testing dimension, which is the largest integer d such that all sets of cardinality d are shattered. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007