Chain Intersecting Families

摘要

Let ${mathcal{F}}$ be a family of subsets of an n-element set. ${mathcal{F}}$ is called (p,q)-chain intersecting if it does not contain chains $A_1subsetneq A_2subsetneqdotssubsetneq A_p$ and $B_1subsetneq B_2subsetneqdotssubsetneq B_q$ with $A_pcap B_q=emptyset$ . The maximum size of these families is determined in this paper. Similarly to the p = q = 1 special case (intersecting families) this depends on the notion of r-complementing-chain-pair-free families, where r = p + q − 1. A family ${mathcal{F}}$ is called r-complementing-chain-pair-free if there is no chain ${mathcal{L}} subseteq {mathcal{F}}$ of length r such that the complement of every set in ${mathcal{L}}$ also belongs to ${mathcal{F}}$ . The maximum size of such families is also determined here and optimal constructions are characterized.