Embedding maximal cliques of sets in maximal cliques of bigger sets. (English) Zbl 0596.05038
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.
Reviewer: J.Sedláček
References:
| [1] | Blokhuis, A., On subsets of GF \((q^2)\) with square differences, (Proc. Akademie van Wetenschappen, A 87 (1984)), 369-372 · Zbl 0561.12009 |
| [2] | Bruck, R. H., Finite nets, II: uniqueness and imbedding, Pacific J. Math., 13, 421-457 (1963) · Zbl 0124.00903 |
| [3] | Dénes, J.; Keedwell, A. D., Latin Squares and their Applications (1974), English Universities Press: English Universities Press London · Zbl 0283.05014 |
| [4] | Dow, S. J.; Drake, D. A.; Füredi, Z.; Larson, J. A., A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size, (Proc. 16th S.E. Conf. on Combin., Graph Theory and Computing (1985)), to appear · Zbl 0648.05001 |
| [5] | Drake, D. A., Maximal \((k + 1)\)-cliques that carry maximal \(k\)-cliques, (Proc. Conference on Finite Geometries. Proc. Conference on Finite Geometries, Winnipeg, 1984 (1985), Marcel Dekker: Marcel Dekker New York) · Zbl 0583.51007 |
| [6] | Drake, D. A.; Sane, S. S., Maximal intersecting families of finite sets and \(n\)-uniform Hjelmslev planes, (Proc. Amer. Math. Soc., 86 (1982)), 358-362 · Zbl 0504.05003 |
| [7] | Erdös, P.; Lovász, L., Proble,s and results on 3-chromatic hypergraphs and some related questions, (Proc. Colloq. Math. Soc. J. Bolyai, 10 (1974), North-Holland: North-Holland Amsterdam), 609-627 |
| [8] | Füredi, Z., On maximal intersecting families of finite sets, J. Combin. Theory Ser. A, 28 (1980) · Zbl 0438.05002 |
| [9] | Lovász, L.; Schrijver, A., Remarks on a theorem of Rédei, Studia Sci. Math. Hungarica, 16, 449-454 (1981) · Zbl 0535.51009 |
| [10] | Meyer, J.-C, Quelques problèmes conçernant les cliques des hypergraphes \(h\)-complets et \(q\)-parti \(h\)-complets, (Lecture Notes in Math., 411 (1974), Springer: Springer Berlin-New York), 127-139 · Zbl 0302.05112 |
| [11] | Pintz, J., On primes in short intervals I, Studia Sci. Math. Hungarica, 16, 395-414 (1981) · Zbl 0469.10013 |
| [12] | Rédei, L., Lancunary Polynomials over Finite Fields (1973), North-Holland, Amsterdam · Zbl 0255.12009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
