ARTICLE
TITLE

A Generalization of the Bollobás Set Pairs Inequality

SUMMARY

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for n?n \geqslant k \geqslant t \geqslant 2, we consider a collection of kk families \mathcal{A}_i: 1 \leq i \leqslant k\mathcal{A}_i: 1 \leq i \leqslant k where \mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \} so that A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \varnothingA_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \varnothing if and only if there are at least tt distinct indices i_1,i_2,\dots,i_ki_1,i_2,\dots,i_k. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size \beta_{k,t}(n)\beta_{k,t}(n) of the families with ground set [n][n].

 Articles related

Christos Pelekis, Israel Rocha    

Let H=(V,E)\mathcal{H}=(V,\mathcal{E}) be an rr-uniform hypergraph on nn vertices and fix a positive integer kk such that 1=k=r1\le k\le r. A kk-matching of H\mathcal{H} is a collection of edges M?E\mathcal{M}\subset \mathcal{E} such that every subset of... see more


Bennet Goeckner, Fran Herr, Legrand Jones II, Rowan Rowlands    

The matching complex M(G)M(G) of a graph G is the set of all matchings in G. A Buchsbaum simplicial complex is a generalization of both a homology manifold and a Cohen–Macaulay complex. We give a complete characterization of the graphs G for which M(G)M(... see more


Peter Bradshaw    

A bipartite graph is called bipancyclic if it contains cycles of every even length from four up to the number of vertices in the graph. A theorem of Schmeichel and Mitchem states that for n?n \geqslant 4, every balanced bipartite graph on 2n2n vertices i... see more


Kenneth Barrese    

Two boards are rook equivalent if they have the same number of non-attacking rook placements for any number of rooks. Define a rook equivalence graph on an equivalence class of Ferrers boards by specifying that two boards are connected by an edge if you ... see more


Adam Doliwa    

We introduce a coloured generalization  NSymA\mathrm{NSym}_A of the Hopf algebra of non-commutative symmetric functions  described as a subalgebra of the of rooted ordered coloured trees Hopf algebra. Its natural basis can be identified with th... see more