Proving that $81$ $K_4^3$'s cannot be packed in a doubled $K_{11}^3$

127 Views Asked by At

The sequence $T_{2,m}$ in Guy's 1967 paper A problem of Zarankiewicz describes the maximum size of a collection of $4$-subsets of $\{1,\dots,m\}$ such that every $3$-subset is in at most two of the $4$-subsets. It had not been added to the OEIS until the time of my work on Zarankiewicz's problem, so I added it as A351100; to have a good number of terms I needed to compute the $m=11$ term.

That term turns out to be $80$, but my present proof is quite involved. There are $2\binom{11}3=330$ $3$-subsets (faces in the terminology of Guy) to be covered with $4$-subsets (tetrahedra, or tets for short), yet each tet has $4$ faces, so there must be $4k+2$ unused faces. Now every member (vertex) of $\{1,\dots,m\}$ is incident to $2\binom{10}2=90$ faces and each tetrahedron uses $3$ such faces, so the number of unused faces at each vertex is a multiple of $3$.

There is a collection satisfying the conditions with $80$ tets, or $10$ unused faces, so the number I am looking for is between $80$ and $\lfloor330/4\rfloor=82$ inclusive. It clearly cannot be $82$ since the two unused faces in that case cannot be arranged such that each vertex has a multiple of $3$ unused faces incident to it. Now suppose there is an admissible collection with $81$ tets or $6$ unused faces; there are $8$ non-isomorphic $3$-uniform hypergraphs with $6$ hyperedges where every vertex is incident to a positive multiple-of-$3$ number of hyperedges and no hyperedge is repeated thrice. For each such graph I showed using Gurobi that it is impossible to pack $81$ tets and leave that hypergraph of unused faces, thus ruling $81$ out outright.

Is there a shorter/cleaner way to prove that $81$ tets cannot be packed?

1

There are 1 best solutions below

7
On

For fixed $m$, you can solve the problem directly via integer linear programming as follows. For each $4$-subset $S\subset \{1,\dots,m\}$, let binary decision variable $x_S$ indicate whether $S$ is selected. The problem is to maximize $\sum_S x_S$ subject to $$\sum_{S: T \subset S} x_S \le 2 \quad \text{for all $3$-subsets $T \subset \{1,\dots,m\}$}.$$ Note that summing all the constraints yields $$\binom{4}{3}\sum_S x_S \le 2 \binom{m}{3},$$ which implies an upper bound of $$\left\lfloor\frac{1}{2}\binom{m}{3}\right\rfloor.$$


It looks like your OEIS sequence is not yet published, but the maximum values for $m\in\{12,\dots,17\}$ are $108$, $143$, $182$, $225$, $280$, and $340$.


Here's a feasible solution for $m=19$ with $480$ subsets (in binary encoding, so $15$ corresponds to $\{1,2,3,4\}$):

15 39 83 92 106 153 180 198 240 267 306 325 360 389 549 556 568 652 658 674 705 774 833 848 904 1037 1066 1073 1122 1158 1224 1283 1298 1313 1352 1424 1554 1556 1696 1920 2086 2089 2100 2117 2179 2256 2321 2434 2464 2584 2594 2632 2640 2692 2848 3096 3140 3201 3332 3336 4131 4152 4170 4193 4233 4258 4292 4362 4376 4418 4420 4611 4614 4704 4737 4752 5129 5140 5200 5256 5408 5696 6156 6161 6162 6216 6404 6912 7170 8242 8276 8289 8338 8360 8392 8454 8468 8488 8592 8640 8709 8721 8770 8776 9219 9226 9240 9252 9281 9984 10249 10250 10273 10372 10560 11296 11328 12300 12305 12324 12418 12576 12816 13440 13824 16398 16405 16406 16409 16457 16472 16517 16578 16608 16652 16688 16929 16964 17168 17444 17537 17668 17728 17922 17928 18435 18498 18568 18592 18696 18945 19472 20498 20516 20737 20864 21024 21505 22592 23040 24624 24672 24708 24833 24834 25096 25216 26628 26640 28736 32787 32809 32844 32849 32850 32916 32929 32936 33036 33060 33090 33153 33154 33290 33300 33328 33472 33537 33797 33888 34305 34368 34822 34826 34912 35088 35332 35968 36996 37008 37136 37384 37920 38913 39936 40969 40984 40994 41474 42112 42240 43136 43520 45057 45120 49217 49220 49282 49288 49440 49920 50184 50192 51232 53250 53252 65585 65636 65667 65676 65688 65729 65801 65812 65816 65826 65952 66058 66144 66572 66577 66626 66628 66690 67073 67080 67602 67604 67624 67649 67650 68097 68224 68640 69638 69672 69680 69824 69889 70148 70400 71808 73731 73733 73808 73888 74244 74496 76032 79872 81930 81953 82000 82064 82240 82304 82434 84992 87040 90120 94208 98309 98340 98624 98848 99344 100360 100608 102402 102408 106512 106560 115200 131094 131098 131100 131139 131172 131184 131210 131217 131236 131345 131361 131520 131587 131593 131650 131844 131872 132136 132161 132240 132256 132612 133125 133168 133256 133312 133378 133440 134146 134656 135173 135248 135552 135688 136196 136448 137248 139276 139332 139393 139528 139808 140304 141824 143362 145408 147490 147496 147714 147984 148096 148544 149508 151560 151680 155649 156672 163846 163912 164104 164480 164866 165889 165904 167968 168000 172064 172288 180225 180240 196617 196642 196680 196868 197136 197184 197888 200705 200720 204802 204928 212996 215040 229504 230400 262165 262170 262188 262214 262217 262282 262305 262436 262480 262496 262532 262536 262665 262673 262724 262914 262920 263174 263216 263248 263360 263712 264204 264288 264336 264449 264706 265217 265728 266245 266260 266305 266400 267266 268320 268416 270402 270465 270593 270880 270976 271364 272386 272400 274440 274688 278531 278562 278568 278672 279044 279104 279680 280832 282632 282640 287744 294915 294936 294946 294960 295104 295944 296192 297024 299264 299520 303108 313344 319488 327698 327752 327938 328208 328320 328960 329732 331840 332800 335880 335904 344065 344068 360449 360576 393249 393346 393348 393488 394241 394248 395272 397314 397824 401424 401472 409664 409856 425988 426496 458784 460800