Existential closure in uniform hypergraphs
For a positive integer n , a graph with at least n vertices is n -existentially closed or simply n -e.c. if for any set of vertices S of size n and any set T ⊆ S , there is a vertex x ∉ S adjacent to each vertex of T and no vertex of S ∖ T . We extend this concept to uniform hypergraphs, find necessary conditions for n -e.c. hypergraphs to exist, and prove that random uniform hypergraphs are asymptotically n -existentially closed. We then provide constructions to generate infinitely many examples of n -e.c. hypergraphs. In particular, these constructions use certain combinatorial designs as ingredients, adding to the ever-growing list of applications of designs.
Authors
- Robert D. Luther (ORCID: https://orcid.org/0000-0002-3684-2889)
- Andrea C. Burgess (ORCID: https://orcid.org/0009-0001-0504-7823)
- David A. Pike (ORCID: https://orcid.org/0000-0001-8952-3016)
Institutions
- University of New Brunswick (CA)
- Memorial University of Newfoundland (CA)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2024-12-23
- DOI
- https://doi.org/10.1016/j.disc.2024.114372
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Natural Sciences and Engineering Research Council of Canada