The Binomial k ‐Clique

A finite collection C of k ‐sets, where k ≥ 2 , is called a k ‐clique if every two k ‐sets (called lines) in C have a nonempty intersection and a k ‐clique is a called a maximal k ‐clique if | C | < ∞ and C is maximal with respect to this property. That is, every two lines in C have a nonempty intersection and there does not exist A such that | A | ≤ k , A ∉ C and A ∩ X ≠ ∅ for all X ∈ C . An elementary example of a maximal k ‐clique is furnished by the family of all the k ‐subsets of a ( 2 k − 1 ) ‐set. This k ‐clique will be called the binomial k ‐clique. This paper is intended to give some combinatorial characterizations of the binomial k ‐clique as a maximal k ‐clique. The techniques developed are then used to provide a large number of examples of mutually nonisomorphic maximal k ‐cliques for a fixed value of k .