On the non-existence of pair covering designs with at least as many points as blocks (Q2428629): Difference between revisions

A pair covering with parameters \(v\), \(k\) and \(\lambda\), denoted \((v,k,\lambda)\)-covering, is a pair \((V,B)\) where \(V\) is a set of \(v\) points and \(B\) is a collection of \(k\)-subsets of \(V\), called blocks, such that each pair of elements of \(V\) occurs in at least \(\lambda\) blocks of \(B\). The covering number \(C_\lambda (v,k)\) is the minimum number of blocks in any \((v,k,\lambda)\)-covering. The authors establish new lower bounds on the pair covering number \(C_\lambda (v,k)\) for infinitely many values of \(v\), \(k\) and \(\lambda\), especially infinitely many values of \(v\) and \(k\) for \(\lambda =1\). Here, \(C_\lambda (v,k)\) denotes the minimum number of \(k\)-subsets of a \(v\)-set of points such that each pair of points occurs in at least \(\lambda\) of the \(k\)-subsets. The results are used to prove simple numerical conditions which are both necessary and sufficient for the existence of \((K_k -e)\)-designs, where \(K_k -e\) denotes the graph obtained by the removal of an edge from the complete graph of order \(k\) (which is denoted by \(K_k\)).