Near perfect coverings in graphs and hypergraphs (Q1092067): Difference between revisions

Suppose we are given a bipartite graph with vertex set X, Y, \(| X| =n\), \(| Y| =N\), each point in X(Y) has degree D(d) fixed, respectively, moreover, each pair of points x,x'\(\in X\) has at most D/(log n)\({}^ 3\) (common) neighbours. Let t(X,Y) denote the minimum number of vertices of Y needed to cover all vertices of X. We prove (Theorem 1.1) that t(X,Y)d/n tends to 1 as n tends to infinity. This result has many applications. Theorem [the second author, Eur. J. Comb. 6, 69-78 (1985; Zbl 0565.05016)]. Suppose \(k>r>1\) are fixed, \(n\to \infty\). Then there exists a collection of \((1+o(1))\times \left( \begin{matrix} n\\ r\end{matrix} \right)/\left( \begin{matrix} k\\ r\end{matrix} \right)\) k-subsets of an n-set so that each r-subset is contained in at least one member of the collection. Analogues and strengthenings of this result are deduced. E.g. for vector spaces, orthogonal or simplectic geometries, random collections of k-sets with constant probabilities, etc. Theorem 3.3. Suppose \({\mathcal G}\) is a graph on v vertices and e edges and \({\mathcal R}\) is a random graph on n vertices and edge probability \(e/\left(\begin{matrix} v\\ 2\end{matrix} \right)\). Then there exists a collection of \((1+o(1))\left( \begin{matrix} n\\ 2\end{matrix} \right)/\left( \begin{matrix} v\\ 2\end{matrix} \right)\) induced subgraphs of \({\mathcal R}\) on v vertices, isomorphic to \({\mathcal G}\) and such that each edge (non-edge) of \({\mathcal R}\) is covered by an edge (non-edge) of a graph in the collection.