Back to Search
Start Over
On partial cubes, well-graded families and their duals with some applications in graphs
- Source :
- Discrete Applied Mathematics. 283:207-230
- Publication Year :
- 2020
- Publisher :
- Elsevier BV, 2020.
-
Abstract
- Well-graded families, extremal systems and maximum systems (the last two in the sense of VC-theory and Sauer-Shelah lemma on VC-dimension) 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 well-graded, extremal or maximum. On the way to this goal, and maybe also of independent interest, we study the structure of the well-graded 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 well-graded, extremal or maximum. We clarify the relation of such graphs to the celebrated half-graphs. Through the paper, we frequently relate our investigations to the VC-dimension of the systems. Also we use one-inclusion graphs associated to set systems as an important technical tool.<br />Comment: 32 pages
- Subjects :
- Structure (mathematical logic)
Discrete mathematics
Lemma (mathematics)
05C75, 05C65, 05D05, 05C20, 03C45
Applied Mathematics
Duality (mathematics)
0211 other engineering and technologies
021107 urban & regional planning
Context (language use)
Mathematics - Logic
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Domain (mathematical analysis)
Set (abstract data type)
010201 computation theory & mathematics
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Dual polyhedron
Combinatorics (math.CO)
Logic (math.LO)
Finite set
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 283
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....aba872d1d19e2c5c92b25d947ca6164a