Rich subcontexts
From MaRDI portal
Publication:6281865
Abstract: For a finite binary relation, we show a local operation which does not decrease its number of (Galois-)closed sets and eventually increases its (Vapnik-Chervonenkis)-dimension. Specifically, we show that there always exist a pair of elements, one belonging to each ground set, such that the subrelation not relating any of those elements has at least half of the Galois-closed sets. As a consequence, for each triple (n,m,k) there exists a binary relation with VC-dimension precisely k and maximum number of Galois-closed sets, such maximum being over all binary relations having ground sets with precisely n and m elements.
This page was built for publication: Rich subcontexts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281865)
