A comparison theorem for permanents and a proof of a conjecture on \((t,m)\)-families (Q1194752)

Let \(N(F)\) denote the number of distinct SDRs of the family \(F=(F_ 1,\dots,F_ m)\). Further let \(t\) be a nonnegative integer. A family \(F\) is called a \((t,m)\)-family if \(|\bigcup_{i\in I}F_ i|\geq| I|+t\) for any nonempty subset \(I\subseteq[1,m]\). The present problem is: What is the value of \(M(t,m)=\min\{N(F):F\) is a \((t,m)\)-family\}? For the family \(F^*_{t,m}=(F^*_ 1,\dots,F^*_ m)\) with \(F^*_ i=\{i,m+1,m+2,\dots,m+t\}\), \(1\leq i\leq m\), it is clear that the value of \(N(F^*_{t,m})\) is \[ U(t,m)=\sum^{\min(t,m)}_{j=0}j!{t\choose j}{m\choose j}. \] In this paper, \(M(t,m)=U(t,m)\) for all \(t>1\) is proved. Furthermore, some refinement of this result is given in terms of permanents of matrices.