“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16016  


Abstract:  
Wellgraded families, extremal systems and maximum systems (the last two in the sense of VCtheory and SauerShelah lemma on VCdimension) are three important classes of set systems. This paper aims to study
the notion of duality in the context of these classes of set systems and then use the obtained results for studying graphs. More specifically, we are concerned with the characterization of the finite set systems which themselves and their dual systems are both wellgraded, extremal or maximum. On the way to this goal, and maybe also of independent interest, we study the structure of the wellgraded families with the property that the size of the system is not much bigger than the size of its essential domain, that is, the set of
elements of the domain which are shattered by the system as single element subsets. As another target of the paper, we use the above results to characterize graphs whose set systems of open or closed neighbourhoods, cliques or independent sets are wellgraded, extremal or maximum. We clarify the relation of such graphs to the celebrated halfgraphs. Through the paper, we frequently relate our investigations to the VCdimension of the systems. Also we use oneinclusion graphs associated to set systems as an important technical tool.
Download TeX format 

back to top 