Existentially Closed BIBD Block-Intersection Graphs

Abstract

A graph $G$ with vertex set $V$ is said to be $n$-existentially closed if, for every $S \subset V$ with $|S|=n$ and every $T \subseteq S$, there exists a vertex $x \in V-S$ such that $x$ is adjacent to each vertex of $T$ but is adjacent to no vertex of $S-T$. Given a combinatorial design ${\cal D}$ with block set ${\cal B}$, its block-intersection graph $G_{{\cal D}}$ is the graph having vertex set ${\cal B}$ such that two vertices $b_1$ and $b_2$ are adjacent if and only if $b_1$ and $b_2$ have non-empty intersection.

In this paper we study BIBDs (balanced incomplete block designs) and when their block-intersection graphs are $n$-existentially closed. We characterise the BIBDs with block size $k \geq 3$ and index $\lambda=1$ that have 2-e.c. block-intersection graphs and establish bounds on the parameters of BIBDs with index $\lambda=1$ that are $n$-e.c. where $n \geq 3$. For $\lambda \geq 2$ and $n \geq 2$, we prove that only simple $\lambda$-fold designs can have $n$-e.c. block-intersection graphs. In the case of $\lambda$-fold triple systems we show that $n \geq 3$ is impossible, and we determine which 2-fold triple systems (i.e., BIBDs with $k=3$ and $\lambda=2$) have 2-e.c. block-intersection graphs.