Intersecting SetPair Systems
An intersecting setpair system is a set of pairs { (A_{i}, B_{i})  1 ≤ i ≤ m } with some additional restrictions on how the As and Bs intersect. The classic setup requires A_{i} ∩ B_{i} = ∅ for all i but A_{i} ∩ B_{j} ≠ ∅ 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 setpair system be? With just the restrictions above, Bollobás proved that if A_{i} ≤ a and B_{i} ≤ 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 setpair system.
Recently, Füredi, Gyárfás, and Király [2019] explored intersecting setpair
systems with the additional restriction that  A_{i} ∩ B_{j}  = 1 for all i ≠ j.
Holzman [2021] followed their paper with a proof that
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 closedform 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
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 12element 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
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.

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