Embedding maximal cliques of sets in maximal cliques of bigger sets (Q1078196): Difference between revisions

An incidence structure \(\Sigma\) is a set of elements (called points) together with a collection of distinguished subsets (called lines). If \(\Sigma\) has a constant line size k and every point lies on at least one line and every pair of lines has at least one common point then \(\Sigma\) is called a k-clique. A k-clique is said to be maximal if it cannot be extended to another k-clique by adjoining another line and, possibly, additional points. First the author characterizes all maximal \((k+1)\)- cliques that contain a given maximal k-clique as a subclique. For arbitrary s he describes all maximal \((k+s)\)-cliques containing a maximal k-clique without so-called piercing lines. Finally, he uses these characterizations to obtain maximal cliques which have fewer lines (for given k) than previously known examples.