3
$\begingroup$

I'm interested in inequalities that guarantee the presence of cliques in incomplete block designs. Here's the set-up:

I have an incidence structure $(V, B)$ which is an incomplete block design: $V$ is a set of size $v$ (the vertices), $B$ is a set of size $b$ (the blocks) and the following properties hold

  • every block is incident with $k$ vertices;
  • every vertex is incident with $r$ blocks;
  • any two blocks intersect in either 0 or 1 vertices.

It is easy enough to prove that if $$k(k-1)(r-1)+k>v$$ then there is a 3-clique, i.e. a set of 3 vertices and 3 blocks whose incidence graph is a $K_{3,3}$ complete bipartite graph. I'm imagining that there might be an analogous inequality for $4$-cliques, 5-cliques and so on... and I'd like to know if someone can point me to it in the literature.

Note: the only slightly unusual part of this set up is that two of my blocks can intersect in either 0 or 1 vertices. In design theory terms I'm saying that $\lambda \in\{0,1\}$ $-$ the fact that $\lambda$ can take on more than one value is the reason my incidence structure is not a balanced incomplete block design.

Improve this question
$\endgroup$
2
  • $\begingroup$ The incidence structures you mention seem to have been studied under the name of partial linear spaces. Also - in a $t$-$(v,k,\lambda)$ design, it's normal to use $\lambda$ for the number of blocks containing any $t$-set of points. When the design is symmetric, then $t = 2$ and the block intersection numbers are also all equal to $\lambda$ but this does not hold in general. I don't know if there's a better symbol than $\lambda$ for the block intersections in this context... $\endgroup$
    – Padraig Ó Catháin
    Commented Jun 3, 2021 at 20:23
  • $\begingroup$ @PadraigÓCatháin, thank you for this, that's very helpful. I'll look up partial linear spaces now... $\endgroup$
    – Nick Gill
    Commented Jun 4, 2021 at 8:43

0

Reset to default

You must log in to answer this question.