Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  703.05044
Autor:  Erdös, Paul; Pach, János; Pyber, L.
Title:  Isomorphic subgraphs in a graph. (In English)
Source:  Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 553-556 (1988).
Review:  [For the entire collection see Zbl 673.00009.]
Let fr,s(n) denote the maximum integer f such that every r-uniform hypergraph H of size n contains s pairwise edge-disjoint isomorphic subhypergraphs of size f each. The authors prove that for every r \geq 3 and s \geq 2 there exist constants cr,s, dr,s > 0 such that

cr,sns/(rs-1) < fr,s(n) < dr,sns/(rs-r+1)· \frac{log n}{log log n}.

The particularization to graphs (r = 2) settles a problem posed by Schönheim.
Reviewer:  K.R.Parthasarathy
Classif.:  * 05C65 Hypergraphs
                   05C70 Factorization, etc.
                   05C60 Isomorphism problems (graph theory)
Keywords:  partition; uniform hypergraph
Citations:  Zbl 673.00009

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page