On cross-intersecting uniform sub-families of hereditary families (Q976709)

Summary: A family \({\mathcal H}\) of sets is hereditary if any subset of any set in \({\mathcal H}\) is in \({\mathcal H}\). If two families \({\mathcal A}\) and \({\mathcal B}\) are such that any set in \({\mathcal A}\) intersects any set in \({\mathcal B}\), then we say that \(({\mathcal A},{\mathcal B})\) is a cross-intersection pair (cip). We say that a cip \(({\mathcal A},{\mathcal B})\) is simple if at least one of \({\mathcal A}\) and \({\mathcal B}\) contains only one set. For a family \({\mathcal F}\), let \(\mu({\mathcal F})\) denote the size of a smallest set in \({\mathcal F}\) that is not a subset of any other set in \({\mathcal F}\). For any positive integer \(r\), let \([r]:= \{1,2,\dots,r\}\), \(2^{[r]}:= \{A: A\subseteq[r]\}\), \({\mathcal F}^{(r)}:= \{F\in{\mathcal F}:|F|= r\}\). We show that if a hereditary family \({\mathcal H}\subseteq 2^{[n]}\) is compressed, \(\mu({\mathcal H})\geq r+ s\) with \(r\leq s\), and \(({\mathcal A},{\mathcal B})\) is a cip with \(\emptyset\neq{\mathcal A}\subset{\mathcal H}^{(r)}\) and \(\emptyset\neq{\mathcal B}\subset{\mathcal H}^{(s)}\), then \(|{\mathcal A}|+|{\mathcal B}|\) is a maximum if \(({\mathcal A},{\mathcal B})\) is the simple cip \((\{[r]\}\), \(\{B\in{\mathcal H}^{(s)}: B\cap[r]\neq\emptyset\})\); \textit{P. Frankl} and \textit{N. Tokushige} [J. Comb. Theory, Ser. A 61, No. 1, 87--97 (1992; Zbl 0767.05093)] proved this for \({\mathcal H}= 2^{[n]}\). We also show that for any \(2\leq r\leq s\) and \(m\geq r+ s\) there exist (non-compressed) hereditary families \({\mathcal H}\) with \(\mu({\mathcal H})= m\) such that no cip \(({\mathcal A},{\mathcal B})\) with a maximum value of \(|{\mathcal A}|+ |{\mathcal B}|\) under the condition that \(\emptyset\neq{\mathcal A}\subset{\mathcal H}^{(r)}\) and \(\emptyset\neq{\mathcal B}\subset{\mathcal H}^{(s)}\) is simple (we prove that this is not the case for \(r=1\)), and we suggest two conjectures about the extremal structures in general.