Maximum clique in intersection graph of $3$-element subsets of a $9$-element set?

Question

How big is the largest collection of $3$-element subsets of $\{1,\ldots,9\}$ such that every pair of sets intersects nontrivially?

I have a hard time visualizing the problem, or getting a grip on it. I have found a few lower and upper bounds in different ways, the tightest I can get is that it is between $28$ and $44$, but every slight sharpening requires increasingly tedious work. Is there a better approach than brute-forcing this with a computer or many hours of paperwork?

Bonus question: Is there any nice construction of such a maximal collection of subsets?

Answer 1

You can solve the problem via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether node $i$ is selected. Let $E$ be the edge set. The problem is to maximize $\sum_i x_i$ subject to linear constraints $x_i + x_j \le 1$ for $i < j$ with $(i,j)\not\in E$.

28 turns out to be optimal:

259 100000011 
261 100000101 
262 100000110 
265 100001001 
266 100001010 
268 100001100 
273 100010001 
274 100010010 
276 100010100 
280 100011000 
289 100100001 
290 100100010 
292 100100100 
296 100101000 
304 100110000 
321 101000001 
322 101000010 
324 101000100 
328 101001000 
336 101010000 
352 101100000 
385 110000001 
386 110000010 
388 110000100 
392 110001000 
400 110010000 
416 110100000 
448 111000000 

Answer 2

The general theorem you are looking for here is the Erdős–Ko–Rado theorem, which states that for $n \geq 2r$, the largest size of an intersecting family of $r$-element subsets of $\{1, \ldots, n\}$ is ${n-1 \choose r-1}$.