Coast to Coast Seminar Series: Live from St. John's, Newfoundland "Existential Closure and BIBD Block-Intersection Graphs"

Abstract

A graph G with vertex set V is said to be n-existentially closed (or n-e.c. for short) if, for every proper subset S of V with |S|=n and every subset T of 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.

A balanced incomplete block design (BIBD) with parameters (v,k,lambda) consists of a set of blocks, each of which is a k-subset of a set V of cardinality v, such that each 2-subset of V occurs in precisely lambda of the blocks of the design.

Given a combinatorial design D with block set B, its block-intersection graph is the graph having B as its vertex set, 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 talk we will present some recent results concerning balanced incomplete block designs (BIBDs) and when their block-intersection graphs are n-existentially closed.

This is joint work with Neil A. McKay.