The VC dimension of k-uniform random hypergraphs

B. Ycart, J. Ratsaby

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

2 اقتباسات (Scopus)

ملخص

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.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)564-572
عدد الصفحات9
دوريةRandom Structures and Algorithms
مستوى الصوت30
رقم الإصدار4
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يوليو 2007
منشور خارجيًانعم

بصمة

أدرس بدقة موضوعات البحث “The VC dimension of k-uniform random hypergraphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا