×

Existential closure of block intersection graphs of infinite designs having finite block size and index. (English) Zbl 1273.05186

Summary: We study the \(n\)-existential closure property of the block intersection graphs of infinite \(t\)-\((v,k,\lambda)\) designs for which the block size \(k\) and the index \(\lambda\) are both finite. We show that such block intersection graphs are 2-e.c. when \(2 \leq t \leq k-1\). When \(\lambda = 1\) and \(2 \leq t \leq k\), then a necessary and sufficient condition on \(n\) for the block intersection graph to be \(n\)-e.c. is that \(n\leq\min\{t, \lfloor(k-1)/(t-1)\rfloor+1\}\). If \(\lambda \geq 2\) then we show that the block intersection graph is not \(n\)-e.c. for any \(n \geq \min\{t+1,\lceil k/t\rceil + 1\}\), and that for \(3 \leq n \leq \min\{t, \lceil k/t\rceil\}\) the block intersection graph is potentially but not necessarily \(n\)-e.c. The cases \(t = 1\) and \(t = k\) are also discussed.

MSC:

05C75 Structural characterization of families of graphs
05B05 Combinatorial aspects of block designs
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI

References:

[1] Beutelspacher, Transfinite methods in geometry, Bull Belg Math Soc 3 pp 337– (1994) · Zbl 0804.51001
[2] Bonato, The search for n-e.c. graphs, Contrib Discrete Math 4 pp 40– (2009) · Zbl 1203.05138
[3] Cameron, Research Notes in Mathematics Series, in: Geometrical Combinatorics pp 13– (1984)
[4] Cameron, Note on large sets of infinite Steiner systems, J Combin Des 3 pp 307– (1995) · Zbl 0885.05029 · doi:10.1002/jcd.3180030408
[5] Cameron, What is an infinite design?, J Combin Des 10 pp 79– (2002) · Zbl 1003.05017 · doi:10.1002/jcd.10005
[6] D. Cohen On the ubiquity of infinite perfect codes and infinite Steiner systems 1993
[7] Erdos, Asymmetric graphs, Acta Math Acad Sci Hungar 14 pp 295– (1963) · Zbl 0118.18901 · doi:10.1007/BF01895716
[8] Forbes, Steiner triple systems and existentially closed graphs, Electron J Combin 12 (2005) · Zbl 1075.05012
[9] Grannell, Countably infinite steiner triple systems, Ars Combinatoria 24B pp 189– (1987) · Zbl 0724.05009
[10] Grannell, On infinite Steiner systems, Discrete Math 97 pp 199– (1991) · Zbl 0762.05016 · doi:10.1016/0012-365X(91)90435-5
[11] McKay, Existentially closed BIBD block-intersection graphs, Electron J Combin 14 pp 10– (2007) · Zbl 1158.05011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.