Graphs and Combinatorics Дискретная математика и комбинаторика

A note on strongly and totally chain intersecting families

Dániel Gerbner
Springer Nature · 2025-10-30 · DOI 10.1007/s00373-025-02989-4

Аннотация

Abstract Bernáth and Gerbner in 2007 introduced ( p , q )-chain intersecting families of subsets of an n -element underlying set. Those have the property that for any p -chain $$A_1\subsetneq A_2\subsetneq \dots \subsetneq A_p$$ A 1 ⊊ A 2 ⊊ ⋯ ⊊ A p and q -chain $$B_1\subsetneq B_2\subsetneq \dots \subsetneq B_q$$ B 1 ⊊ B 2 ⊊ ⋯ ⊊ B q , we have $$A_p\cap B_q\ne \emptyset $$ A p ∩ B q ≠ ∅ . Bernáth and Gerbner determined the largest cardinality of such families. They also introduced strongly ( p , q )-chain intersecting families, where $$A_p\cap B_1\ne \emptyset $$ A p ∩ B 1 ≠ ∅ and totally ( p , q )-chain intersecting families, where $$A_1\cap B_1\ne \emptyset $$ A 1 ∩ B 1 ≠ ∅ . They obtained some partial results on the maximum cardinality of such families. We extend those results by determining the largest cardinality of strongly ( p , q )-chain intersecting families if n is sufficiently large, and by determining the largest cardinality of totally (2, 2)-chain intersecting families.

Читать у издателя →