On Families of Weakly Cross-intersecting Set-pairs

• Autorzy: Kiraly Z. , Nagy Z. L. , Palvölgyi D. , Visontai M.
• Języki publikacji: EN

Abstrakty

EN

Let F be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in F we have that |A| = a, |B| = b, and A∩B = ∅. Furthermore, F is weakly crossintersecting if for any (Ai,Bi), (Aj ,Bj) ∈ F with i ≠j we have that Ai∩Bj and Aj ∩Bi are not both empty. We investigate the maximum possible size of weakly cross-intersecting (a, b)-set systems. We give an explicit construction for the best known asymptotic lower bound. We introduce a fractional relaxation of the problem and prove that the best known upper bound is optimal for this case. We also provide the exact value for the case when a = b = 2.

Słowa kluczowe

EN

cross-intersecting set-pairs; lattice paths

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 189--198
• Opis fizyczny: Bibliogr. 15 poz., wykr.

Twórcy

autor

Kiraly Z.

autor

Nagy Z. L.

autor

Palvölgyi D.

autor

Visontai M.

• Department of Mathematics, University of Pennsylvania, 209 S. 33rd Street, Philadelphia, PA 19104 USA,

Bibliografia

• [1] Alon, N.: An extremal problem for sets with applications to graph theory, J. Combin. Theory Ser. A, 40, 1985, 82-89.
• [2] Alon, N.: Neighborly families of boxes and bipartite coverings, in: The Mathematics of Paul Erdös, vol. II, Springer Verlag, Berlin, 1997, 27-31.
• [3] Alon, N., Spencer, J. H.: The probabilistic method, 3rd edition,Wiley, 2008.
• [4] Anderson, I.: Combinatorics of finite sets, Dover, 2002.
• [5] Bizley, M. T. L.: Derivation of a new formula for the number of minimal lattice paths from (0,0) to (km, kn) having just t contacts with the line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above the line, J. Inst. Actuar., 80, 1954, 55-62.
• [6] Bollobás, B.: On generalized graphs, Acta Math. Acad. Hungar., 16, 1965, 447-452.
• [7] Frankl, P.: An extremal problem for two families of sets, European J. Combin., 3, 1982, 125-127.
• [8] Füredi, Z.: Geometrical solution of a problem for two hypergraphs, European J. Combin., 5, 1984, 133-136.
• [9] Hoheisel, G.: Primzahlenprobleme in der Analysis, Sitzungsber. Berlin Math. Ges., 1930, 550-558.
• [10] Lovász, L.: Combinatorial Problems and Exercises, North Holland, 1979.
• [11] Sato, M.: Generating functions for the number of lattice paths between two parallel lines with a fractional incline, Math. Japonica, 24, 1989, 123-137.
• [12] Talbot, J.: A new Bollobás-type inequality and applications to t-intersecting families of sets, Discrete Math., 285, 2004, 349-353.
• [13] Tuza, Zs.: Inequalities for two set systems with prescribed intersections, Graphs Combin., 3, 1987, 75-80.
• [14] Tuza, Zs.: Applications of the set-pair method in extremal hypergraph theory, in: Extremal Prolems for Finite Sets, vol. 3 of Bolyai Soc. Math. Stud., Bolyai János Matematika Társulat, 1994, 479-514.
• [15] Tuza, Zs.: Applications of the set-pair method in extremal problems, in: Combinatorics, Paul Erdös is eighty, vol. 2 of Bolyai Soc. Math. Stud., Bolyai János Matematika Társulat, 1996, 459-490