Geometrical solution of an intersection problem for two hypergraphs. (English) Zbl 0546.05048
The author generalizes the following known theorem. If \(A_ 1,...,A_ m\) are a-element and \(B_ 1,...,B_ m\) are b-element sets with \(A_ i\cap B_ j=\emptyset\) iff \(i=j\) then \(m\leq \left( \begin{matrix} a+b\\ a\end{matrix} \right).\) He proves two generalizations below. Let \(A_ 1,...,A_ m\) be a-element and \(B_ 1,...,B_ m\) be b-element sets and \(t\leq\min (a,b).\) If \(| A_ i\cap B_ j|\leq t\) iff \(i=j\) then \(m\leq \left( \begin{matrix} a+b-2t\\ a-t\end{matrix} \right).\) The second result states that if \(A_ 1,...,A_ m\) are a-dimensional and \(B_ 1,...,B_ m\) are b-dimensional subspaces of \(R^ n\), and \(t\leq\min (a,b)\) then \(m\leq \left( \begin{matrix} a+b-2t\\ a-t\end{matrix} \right)\) provided \(\dim (A_ i\cap B_ j)\leq t\) iff \(i=j\).
Reviewer: L.Zaremba
References:
| [1] | Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029 |
| [2] | Burr, S. A.; Grünbaum, B.; Sloan, N. J. A., The orchard problem, Geometriae Dedicata, 2, 397-424 (1974) · Zbl 0311.05024 |
| [3] | Bollobás, B., On generalized graphs, Acta Math. Acad. Sci. Hungar., 16, 447-452 (1965) · Zbl 0138.19404 |
| [4] | Bollobás, B., Weakly \(k\)-saturated graphs, (Sachs, H.; Woss, H.-J.; Walter, H., Beiträge zur Graphentheorie (1968)), 25-31, Leipzig · Zbl 0172.48905 |
| [5] | Bollobás, B., Extremal Graph Theory (1978), Academic Press: Academic Press New York · Zbl 0419.05031 |
| [6] | Erdös, P.; Hajnal, A.; Moon, J. W., A problem in graph theory, Amer. Math. Monthly, 71, 1107-1110 (1964) · Zbl 0126.39401 |
| [7] | Frankl, P., An extremal problem for two families of sets, Europ. J. Combinatorics, 3, 125-127 (1982) · Zbl 0488.05004 |
| [8] | Z. Füredi and I. Pálasti, Arrangements of lines with large number of triangles, Proc. Amer. Math. Soc. (submitted).; Z. Füredi and I. Pálasti, Arrangements of lines with large number of triangles, Proc. Amer. Math. Soc. (submitted). |
| [9] | Z. Füredi and Z. Tuza, Hypergraphs without large stars, J. Combin. Theory, Ser. A (submitted).; Z. Füredi and Z. Tuza, Hypergraphs without large stars, J. Combin. Theory, Ser. A (submitted). |
| [10] | Jaeger, F.; Payan, C., Nombre maximal d’arétes d’un hypergraphe critique de rang \(h\), C R. Acad. Sci. Paris, 273, 221-223 (1971) · Zbl 0234.05119 |
| [11] | Katona, G. O. H., Solution of a problem of Ehrenfeucht and Mycielski, J. Combin. Theory, Ser. A, 17, 265-266 (1974) · Zbl 0289.05002 |
| [12] | Lovász, L., Flats in matroids and geometric graphs, (Cameron, P. J., Combinatorial Surveys (1977), Academic Press: Academic Press New York), 45-86 · Zbl 0361.05027 |
| [13] | Lovász, L., Topological and algebraic methods in graph theory, (Bondy, J. A.; Murty, U. S. R., Graph Theory and Related Topics (1979), Academic Press: Academic Press New York), 1-15, (Proc. of Tutte Conference, Waterloo, 1977) · Zbl 0462.05037 |
| [14] | Lovász, L., Combinatorical Problems and Exercises (1979), Akademiai Kiado: Akademiai Kiado Budapest, and North-Holland, Amsterdam · Zbl 0439.05001 |
| [15] | J. E. Pin, On two combinatorial problems arising from automata theory, Annales Discr. Math. (to appear).; J. E. Pin, On two combinatorial problems arising from automata theory, Annales Discr. Math. (to appear). · Zbl 0523.68042 |
| [16] | Tarján, T., Complexity of lattice-configurations, Studia Sci. Math. Hungar., 10, 203-211 (1975) · Zbl 0395.05017 |
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.
