Existential Closure in Uniform Hypergraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911948524748800 |
|---|---|
| author | Burgess, Andrea C. Luther, Robert D. Pike, David A. |
| author_facet | Burgess, Andrea C. Luther, Robert D. Pike, David A. |
| contents | 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\subseteq S$, there is a vertex $x\not\in S$ adjacent to each vertex of $T$ and no vertex of $S\setminus 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06054 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Existential Closure in Uniform Hypergraphs Burgess, Andrea C. Luther, Robert D. Pike, David A. Combinatorics 05B05, 05C65, 05C80, 05C99 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\subseteq S$, there is a vertex $x\not\in S$ adjacent to each vertex of $T$ and no vertex of $S\setminus 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. |
| title | Existential Closure in Uniform Hypergraphs |
| topic | Combinatorics 05B05, 05C65, 05C80, 05C99 |
| url | https://arxiv.org/abs/2407.06054 |