0
$\begingroup$

My question is one from my graph & set theory class that I'm not sure how to solve. Any help would be greatly appreciated.

Let $\{(A_i, B_i) \mid 1 \leq i \leq h\}$ be a family of pairs of sets satisfying

  • $A_i \cap B_i = \varnothing$ for $i = 1, \ldots, h$;
  • $\left|A_i\right| + \left|B_i\right|=k$ for $i=1, \ldots , h$; and
  • for $i\neq j$, at least one of $A_i \cap B_j$ or $A_j \cap B_i$ is nonempty.

Show that $h\leq 2^k$.

Is $h = 2^k$ always attainable?

I tried to use the following theorem: If $A_1, . . . , A_m$ and $B_1, . . . , B_m$ are two sequences of sets such that $A_i \cap B_j = \varnothing$ if and only if $i = j$, then $$ \sum_{i=1}^m{\binom{|A_i|+|B_i|}{|A_i|}}^{-1}\le 1. $$

$\endgroup$
5
  • $\begingroup$ You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. Regarding your edit, this page should give you a start at learning how to typeset mathematics here. $\endgroup$
    – Brian61354270
    Mar 24, 2019 at 21:32
  • $\begingroup$ Can you describe the theorem you were thinking about using in words? $\endgroup$
    – Mike Earnest
    Mar 24, 2019 at 21:41
  • 1
    $\begingroup$ Of course, $h = 2^k$ is attainable: Just let the $A_i$ be all $2^k$ subsets of $\left\{1,2,\ldots,k\right\}$, and let $B_i$ be their complements. $\endgroup$
    – darij grinberg
    Mar 25, 2019 at 5:02
  • 1
    $\begingroup$ Note that this looks like a version of Bollobas's skew two families theorem. But not sure if the same approach works. $\endgroup$
    – darij grinberg
    Mar 25, 2019 at 5:14
  • $\begingroup$ These look like Chris Fraser's Math 5707 [2019] problems. You can prove it similarly to this proof of Sperner's theorem. Construct a bipartite graph with indices $1,\ldots,h$ as the left part, and subsets of $\bigcup_{i=1}^h (A_i \cup B_i)$ as the right part. $\endgroup$
    – Air Conditioner
    Apr 26, 2019 at 19:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .