On a generalization of a result of Kleitman
Preprint
Abstract
A classical result of Kleitman determines the maximum number $f(n,s)$ of subsets in a family $\mathcal{F}\subseteq 2^{[n]}$ of sets that do not contain distinct sets $F_1,F_2,\dots,F_s$ that are pairwise disjoint in the case $n\equiv 0,-1$ (mod $s$). Katona and Nagy determined the maximum size of a family of subsets of an $n$-element set that does not contain $A_1,A_2,\dots,A_t,B_1,B_2,\dots,B_t$ with $\bigcup_{i=1}^t A_i$ and $\bigcup_{i=1}^t B_i$ being disjoint. In this paper, we consider the problem of finding the maximum number $vex(n,K_{s\times t})$ in a family $\mathcal{F}\subseteq 2^{[n]}$ without sets $F^1_1,\dots,F^1_t,\dots,F^s_1,\dots,F^s_t$ such that $G_j=\bigcup_{i=1}^tF^j_i$ $j=1,2,\dots,s$ are pairwise disjoint. We determine the asymptotics of $2^n-vex(n,K_{s\times t})$ if $n\equiv -1$ (mod $s$) for all $t$, and if $n\equiv 0$ (mod $s$), $t\ge 3$ and show that in this latter case the asymptotics of the $t=2$ subcase is different from both the $t=1$ and $t\ge 3$ subcases.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Towards the Chen-Raspaud conjectureDiscrete Mathematics, 2023
- Families of sets with no matchings of sizes 3 and 4European Journal of Combinatorics, 2019
- Extremal G-free induced subgraphs of Kneser graphsJournal of Combinatorial Theory, Series A, 2018
- Union-Intersecting Set SystemsGraphs and Combinatorics, 2014
- Homomorphisms from sparse graphs to the Petersen graphDiscrete Mathematics, 2010
- The Odd Girth of the Generalised Kneser GraphEuropean Journal of Combinatorics, 1997
- A note on induced cycles in Kneser graphsCombinatorica, 1991
- Largest induced subgraphs of the n-cube that contain no 4-cyclesJournal of Combinatorial Theory, Series B, 1989
- Maximum bipartite subgraphs of Kneser graphsGraphs and Combinatorics, 1987
- Maximal number of subsets of a finite set No k of which are pairwise disjointJournal of Combinatorial Theory, 1968