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
    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
    Jun 4, 2021 at 8:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.