An intersecting set-pair system is a set of pairs { (Ai, Bi) | 1 ≤ i ≤ m } with some additional restrictions on how the As and Bs intersect. The classic setup requires Ai ∩ Bi = ∅ for all i but Ai ∩ Bj ≠ ∅ for all i ≠ j.

Here’s an example:

{ ({1,2}, {3,4}),
  ({1,4}, {2,5}),
  ({2,3}, {1,4}) }

How large can an intersecting set-pair system be? With just the restrictions above, Bollobás proved that if |Ai| ≤ a and |Bi| ≤ b for all i, then m ≤ C(a + b, b)1. And that bound is tight because all (a,b) partitions of a set of size a+b form an intersecting set-pair system.

Recently, Füredi, Gyárfás, and Király [2019] explored intersecting set-pair systems with the additional restriction that | Ai ∩ Bj | = 1 for all i ≠ j. Holzman [2021] followed their paper with a proof that m ≤ 29⁄30 C(a + b, b) for such set-pair systems, and Kostochka, McCourt, and Nahvi [2021] have recently proven that m ≤ 5⁄6 C(a + b, b).

I tried to see if 5⁄6 was tight for small a and b using a SAT solver. It doesn’t look like it is, and some of these constructions look interesting, so here they are:

a=2

When a = 2, Füredi, Gyárfás, and Király give a closed-form solution for m when b ≥ 4. So the results in this section are really just an exercise in verifying their results.

For a = b = 2, I was able to verify that m = 5 by generating a system with 5 pairs and proving that a system of size 6 doesn’t exist. The system of size 5 below is actually unique under permutations of the ground set:

{ ({1, 2}, {3, 4}),
  ({1, 4}, {2, 5}),
  ({2, 3}, {1, 5}),
  ({3, 5}, {2, 4}),
  ({4, 5}, {1, 3}) }

For a = 2, b = 3, m = 7. I was again able to generate a system of size 7 and prove no system of size 8 exists:

{ ({1, 2}, {3, 4, 5}),
  ({1, 3}, {2, 6, 7}),
  ({2, 4}, {1, 6, 7}),
  ({3, 6}, {1, 4, 5}),
  ({4, 7}, {2, 3, 5}),
  ({5, 6}, {2, 3, 7}),
  ({5, 7}, {1, 4, 6}) }

This time, there were 9 distinct systems under permutations. I stopped counting distinct solutions after this because it gets a little tedious with a SAT solver (you find a solution, add a clause that blocks that solution, repeat).

At a = 2, b = 4, I could generate a system of size 9 but couldn’t prove a system of size 10 didn’t exist (the SAT solver ran for too long and I killed it):

{ ({1, 2},  {3, 4, 5, 6}),
  ({2, 5},  {1, 3, 4, 6}),
  ({2, 6},  {1, 3, 4, 5}),
  ({3, 10}, {2, 4, 11, 12}),
  ({3, 11}, {2, 4, 10, 12}),
  ({3, 12}, {2, 4, 10, 11}),
  ({4, 7},  {2, 3, 8, 9}),
  ({4, 8},  {2, 3, 7, 9}),
  ({4, 9},  {2, 3, 7, 8}) }

Same story for a = 2, b = 5, 6, and 7: I could generate a system of maximum size pretty easily but didn’t bother trying to prove a larger system doesn’t exist.

a = 2, b = 5 → m = 12:

{ ({1, 2},  {3, 4, 5, 6, 7}),
  ({2, 4},  {1, 3, 5, 6, 7}),
  ({2, 5},  {1, 3, 4, 6, 7}),
  ({3, 11}, {2, 6, 7, 15, 16}),
  ({3, 15}, {2, 6, 7, 11, 16}),
  ({3, 16}, {2, 6, 7, 11, 15}),
  ({6, 10}, {2, 3, 7, 12, 14}),
  ({6, 12}, {2, 3, 7, 10, 14}),
  ({6, 14}, {2, 3, 7, 10, 12}),
  ({7, 8},  {2, 3, 6, 9, 13}),
  ({7, 9},  {2, 3, 6, 8, 13}),
  ({7, 13}, {2, 3, 6, 8, 9}) }

a = 2, b = 6 → m = 16:

{ ({1, 2},  {3, 4, 5, 6, 7, 8}),
  ({2, 5},  {1, 3, 4, 6, 7, 8}),
  ({2, 6},  {1, 3, 4, 5, 7, 8}),
  ({2, 8},  {1, 3, 4, 5, 6, 7}),
  ({3, 9},  {2, 4, 7, 11, 12, 19}),
  ({3, 11}, {2, 4, 7, 9, 12, 19}),
  ({3, 12}, {2, 4, 7, 9, 11, 19}),
  ({3, 19}, {2, 4, 7, 9, 11, 12}),
  ({4, 15}, {2, 3, 7, 16, 18, 20}),
  ({4, 16}, {2, 3, 7, 15, 18, 20}),
  ({4, 18}, {2, 3, 7, 15, 16, 20}),
  ({4, 20}, {2, 3, 7, 15, 16, 18}),
  ({7, 10}, {2, 3, 4, 13, 14, 17}),
  ({7, 13}, {2, 3, 4, 10, 14, 17}),
  ({7, 14}, {2, 3, 4, 10, 13, 17}),
  ({7, 17}, {2, 3, 4, 10, 13, 14}) }

a = 2, b = 7 → m = 20:

{ ({1, 2},  {3, 4, 5, 6, 7, 8, 9}),
  ({1, 3},  {2, 4, 5, 6, 7, 8, 9}),
  ({1, 4},  {2, 3, 5, 6, 7, 8, 9}),
  ({1, 6},  {2, 3, 4, 5, 7, 8, 9}),
  ({5, 12}, {1, 7, 8, 9, 13, 22, 24}),
  ({5, 13}, {1, 7, 8, 9, 12, 22, 24}),
  ({5, 22}, {1, 7, 8, 9, 12, 13, 24}),
  ({5, 24}, {1, 7, 8, 9, 12, 13, 22}),
  ({7, 10}, {1, 5, 8, 9, 11, 15, 19}),
  ({7, 11}, {1, 5, 8, 9, 10, 15, 19}),
  ({7, 15}, {1, 5, 8, 9, 10, 11, 19}),
  ({7, 19}, {1, 5, 8, 9, 10, 11, 15}),
  ({8, 14}, {1, 5, 7, 9, 17, 21, 25}),
  ({8, 17}, {1, 5, 7, 9, 14, 21, 25}),
  ({8, 21}, {1, 5, 7, 9, 14, 17, 25}),
  ({8, 25}, {1, 5, 7, 9, 14, 17, 21}),
  ({9, 16}, {1, 5, 7, 8, 18, 20, 23}),
  ({9, 18}, {1, 5, 7, 8, 16, 20, 23}),
  ({9, 20}, {1, 5, 7, 8, 16, 18, 23}),
  ({9, 23}, {1, 5, 7, 8, 16, 18, 20}) }

I stopped here because I wanted to move on to a=3 where a closed form for m isn’t known.

a=3

For a=3, we only know the upper bound m ≤ 5⁄6 C(a + b, b) when a,b ≥ 2 from Kostochka, McCourt, and Nahvi’s work.

Here’s what I could find:

For b=1, m=4:

{ ({1, 2, 3}, {4}),
  ({1, 2, 4}, {3}),
  ({1, 3, 4}, {2}),
  ({2, 3, 4}, {1}) }

We already know that m=7 when b=2 by symmetry from the results in the previous section.

When b=3, m ≥ 10:

{ ({1, 2, 3},   {4, 5, 6}),
  ({1, 3, 5},   {2, 9, 10}),
  ({1, 5, 9},   {3, 7, 8}),
  ({2, 3, 6},   {1, 7, 8}),
  ({2, 6, 7},   {3, 9, 10}),
  ({4, 7, 10},  {2, 5, 8}),
  ({4, 8, 9},   {1, 6, 10}),
  ({4, 8, 10},  {3, 7, 9}),
  ({5, 7, 10}), {1, 4, 6}),
  ({6, 8, 9},   {2, 4, 5}) }

I couldn’t prove that there’s no system with a = b = 3 and m = 11. One thing that I could prove (in about 2 hours with a SAT solver) is that no system with a = b = 3 and m = 11 and a ground set of cardinality 10 or 11 exists. So that’s good evidence that the system above is the largest possible, since any larger system would have to use at least a 12-element ground set.

When b=4, m >= 15:

{ ({1, 2, 3},   {4, 5, 6, 7}),
  ({1, 2, 5},   {3, 6, 7, 12}),
  ({2, 3, 4},   {1, 6, 7, 12}),
  ({2, 4, 12},  {3, 5, 6, 7}),
  ({2, 5, 12},  {1, 4, 6, 7}),
  ({6, 11, 14}, {2, 7, 13, 16}),
  ({6, 11, 16}, {2, 7, 14, 18}),
  ({6, 13, 14}, {2, 7, 11, 18}),
  ({6, 13, 18}, {2, 7, 14, 16}),
  ({6, 16, 18}, {2, 7, 11, 13}),
  ({7, 8, 10},  {2, 6, 15, 17}),
  ({7, 8, 17},  {2, 6, 9, 10}),
  ({7, 9, 15},  {2, 6, 10, 17}),
  ({7, 9, 17},  {2, 6, 8, 15}),
  ({7, 10, 15}, {2, 6, 8, 9}) }

I couldn’t prove any more partial results after this, even by restricting the size of the ground set.

Finally, when b = 5, m >= 20:

{ ({1, 2, 3},   {4, 5, 6, 7, 8}),
  ({1, 2, 8},   {3, 5, 6, 7, 17}),
  ({2, 3, 4},   {1, 5, 6, 7, 17}),
  ({2, 4, 17},  {3, 5, 6, 7, 8}),
  ({2, 8, 17},  {1, 4, 5, 6, 7}),
  ({5, 9, 11},  {2, 6, 7, 13, 18}),
  ({5, 9, 13},  {2, 6, 7, 11, 14}),
  ({5, 11, 18}, {2, 6, 7, 9, 14}),
  ({5, 13, 14}, {2, 6, 7, 9, 18}),
  ({5, 14, 18}, {2, 6, 7, 11, 13}),
  ({6, 12, 16}, {2, 5, 7, 15, 23}),
  ({6, 12, 23}, {2, 5, 7, 16, 22}),
  ({6, 15, 16}, {2, 5, 7, 12, 22}),
  ({6, 15, 22}, {2, 5, 7, 16, 23}),
  ({6, 22, 23}, {2, 5, 7, 12, 15}),
  ({7, 10, 21}, {2, 5, 6, 19, 24}),
  ({7, 10, 24}, {2, 5, 6, 20, 21}),
  ({7, 19, 20}, {2, 5, 6, 21, 24}),
  ({7, 19, 21}, {2, 5, 6, 10, 20}),
  ({7, 20, 24}, {2, 5, 6, 10, 19}) }

To wrap up, here’s a table summarizing the lower bounds for m when a=3 implied by the constructions above compared to the current best upper bounds from the formula m ≤ 5⁄6 C(a + b, b)

  a     b     m ≥ ?     m ≤ ?  
3 1 4 4
3 2 7 8.33…
3 3 10 16.666…
3 4 15 29.1666…
3 5 20 46.666…


The closed form for the upper bound only applies for a, b ≥ 2 so I just put “4” in the first row for the upper bound since that’s clearly exact.

I think my lower bounds are pretty tight because there was a noticable threshold between the results I could find (which the SAT solver could find in seconds or minutes) and the proofs I couldn’t find (which made the SAT solver just hang for hours or days).

I’ve put the script I used to generate SAT instances and the decoder I used to take SAT solutions and generate canonical set systems online. You just need Python 3 to run both scripts. I used mainly kissat and cadical to find these results.

  1. C(n,r) is the number of ways to choose r items from an n-element set: C(n,r) = n!/(r!(n-r)!)). ↩