Testing LaTeX Math Rendering After Migrating to Astro

This post is a test of LaTeX and MathJax rendering after migrating this blog from Hugo to Astro. As part of the migration I updated the math rendering pipeline, and I wanted to put it through its paces with something genuinely complex. As source material I used a transcript of GPT-5.4 Pro working through a hard combinatorics problem — the hypergraph extremal function — originally posted to Epoch AI’s open problems list and shared on Hacker News post Epoch confirms GPT5.4 Pro solved a frontier math open problem. I don’t claim to follow the math, but it makes for a thorough stress-test: display equations, aligned blocks, cases, tables with math symbols, inline variables, and Python code all in one post.

USER:

don’t search the internet. This is a test to see how well you can craft non-trivial, novel and creative solutions given a “combinatorics” math problem. Provide a full solution to the problem.

Problem:
“A hypergraph has a partition of size if there exist and such that and every vertex of lies in exactly one edge of . Let be the maximum over all hypergraphs with no isolated vertices and no partition of size greater than . It is known that

Show that for some constant , with the improvement already valid for (it may fail for small ). Give an algorithm that, for input , outputs a hypergraph witnessing this bound.

Output: a Python function solution(n: int) -> str returning the hypergraph as a string, with vertices labeled and edges written like

Constraint: for all , the algorithm must run within 10 minutes on a typical laptop.”

REMEMBER - this unconditional argument may require non-trivial, creative and novel elements.

ASSISTANT:

Let

for a hypergraph and . Then has no partition larger than exactly when

So the problem is to build hypergraphs with many vertices but with uniformly bounded.

1. A substitution lemma

It is convenient to work with a tiny “outer” hypergraph on meta-edges .

Call a hypergraph on meta-edges an -frame if:

1. has exactly singleton vertices on meta-edge ;
2. for every , if denotes the induced subhypergraph obtained by keeping only vertices contained in , then

Now suppose is any hypergraph with no partition larger than , for each . Replace the -th singleton block of the frame by the whole hypergraph , and for every non-singleton meta-vertex of , add one actual vertex lying in all edges of the blocks with .

This gives a new hypergraph .

Lemma

If is an -frame and each has no partition larger than , then

has no partition larger than .

Proof

Take any chosen set of actual edges. Write for the part of inside block .

Let

If , then inside we get at most uniquely-covered vertices, and any outer vertex using block cannot be uniquely covered because it already meets at least two chosen edges there. So all blocks outside contribute at most .

Inside , let

The contribution from the blocks in , together with all outer vertices supported inside , is bounded by the exactly-once count of the frame on the chosen meta-edge set , hence by .

So altogether

That is exactly the claim. ∎

The union of two frames on the same meta-edge set is again a frame, with the capacities added coordinatewise, because all exactly-once counts add.

2. Two useful frames

Binary frame

For capacities , take meta-edges , with singleton vertices on , singleton vertices on , and copies of .

This is an -frame, so

Choosing , gives the classical -recurrence.

Four-way frame

Now the improvement. Work on meta-edges .

The core gadget is:

• one copy of every 2-subset of ,
• one copy of every 3-subset,
• three copies of .

So . A direct check shows is a -frame.

For the 12 residue classes mod , use the following small residual gadgets on :

Each is a valid residual frame for the corresponding residual capacities

a finite check on the 4 meta-edges.

Hence, for , the union

is a valid 4-way frame for the balanced 4-part split of . Writing with , this yields the four-part recurrence

where

Define , and for ,

By the substitution lemma, for every .

For , we have , so

Since , the improvement already starts at .

3. A constant factor

Take

A direct computation of the recurrence for gives

and the minimum ratio in that range is attained at

Now let , write with . Then , so by induction

Also,

and each floor term is much larger than the extra -fraction needed for . So

Finally,

Combining these formulas with the 4-way recurrence gives

Together with the finite check , we get

So one may take .

4. The algorithm

The function below implements exactly the recurrence above and then recursively expands the chosen construction into an actual hypergraph. It always uses exactly edges. Its running time is linear in the output size, and for it is tiny.

from functools import lru_cache

def solution(n: int) -> str:
    if n < 1:
        raise ValueError("n must be positive")

    # Sizes of the residual 4-block gadgets R_t for t = n mod 12.
    residual_sizes = [0, 0, 1, 2, 4, 4, 6, 6, 8, 9, 10, 10]

    # Core gadget C on 4 meta-edges, valid for residual capacities (3,3,3,3).
    core_gadget = [
        (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3),
        (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3),
        (0, 1, 2, 3), (0, 1, 2, 3), (0, 1, 2, 3),
    ]

    # Residual gadgets R_t on meta-edges 0,1,2,3.
    residual_gadgets = {
        0: [],
        1: [],
        2: [(2, 3)],
        3: [(1, 2, 3), (1, 2, 3)],
        4: [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)],
        5: [(0, 1, 2)] + [(0, 1, 2, 3)] * 3,
        6: [(0, 1), (2, 3), (0, 1, 2), (0, 1, 3)] + [(0, 1, 2, 3)] * 2,
        7: [(1, 2), (1, 3), (2, 3), (0, 1, 2)] + [(0, 1, 2, 3)] * 2,
        8: [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)] * 2,
        9: [(0, 1), (0, 2), (1, 2),
            (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)] + [(0, 1, 2, 3)] * 2,
        10: [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
            + [(0, 1), (2, 3), (0, 1, 2), (0, 1, 3)]
            + [(0, 1, 2, 3)] * 2,
        11: [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
            + [(1, 2), (1, 3), (2, 3), (0, 1, 2)]
            + [(0, 1, 2, 3)] * 2,
    }

    # DP for the guaranteed sizes A(n).
    A = [0] * (n + 1)
    choice = [None] * (n + 1)
    A[1] = 1
    choice[1] = ("base",)

    for m in range(2, n + 1):
        a = m // 2
        b = (m + 1) // 2

        # Binary construction.
        best = a + A[a] + A[b]
        best_choice = ("bin", a, b)

        # Balanced 4-way construction.
        if m >= 4:
            q = m // 12
            t = m % 12

            parts = [m // 4] * 4
            for i in range(m % 4):
                parts[3 - i] += 1  # keep parts nondecreasing

            val4 = sum(A[p] for p in parts) + 13 * q + residual_sizes[t]
            if val4 > best:
                best = val4
                best_choice = ("quad", tuple(parts), q, t)

        A[m] = best
        choice[m] = best_choice

    @lru_cache(maxsize=None)
    def build(m: int):
        """
        Returns (vertex_incidence_sets, number_of_edges).
        Each vertex is represented by the set of edge indices containing it.
        """
        ch = choice[m]
        kind = ch[0]

        if kind == "base":
            return ( (frozenset([0]),), 1 )

        if kind == "bin":
            _, a, b = ch
            V1, e1 = build(a)
            V2, e2 = build(b)

            vertices = list(V1)
            vertices.extend(frozenset(x + e1 for x in S) for S in V2)

            all_edges = frozenset(range(e1 + e2))
            vertices.extend([all_edges] * a)  # a = min(a,b)

            return tuple(vertices), e1 + e2

        # 4-way case
        _, parts, q, t = ch
        vertices = []
        block_ranges = []
        offset = 0

        for p in parts:
            W, e = build(p)
            vertices.extend(frozenset(x + offset for x in S) for S in W)
            block_ranges.append(list(range(offset, offset + e)))
            offset += e

        gadget = core_gadget * q + residual_gadgets[t]
        for subset in gadget:
            incidence = []
            for i in subset:
                incidence.extend(block_ranges[i])
            vertices.append(frozenset(incidence))

        return tuple(vertices), offset

    vertex_sets, m_edges = build(n)

    # Transpose from "vertex -> incident edges" to "edge -> incident vertices".
    edges = [[] for _ in range(m_edges)]
    for v_label, S in enumerate(vertex_sets, start=1):
        for e in S:
            edges[e].append(v_label)

    return ",".join("{" + ",".join(map(str, edge)) + "}" for edge in edges)

For this construction,

and in particular

when .

USER:

Great! What are the overall asymptotics of this new lower bound construction?

ASSISTANT:

Let be the vertex count produced by the recursive construction I gave. Then the asymptotics are

So, as a lower bound on ,

The order of growth is still ; the improvement is in the leading constant.

Here is the quick way to see it. The 4-way part of the construction has the form

where the are the balanced quarter-sizes, so each and . Because of that balance,

Now plug in an ansatz . Then

so the -terms must cancel, giving

That is the dominant coefficient.

For comparison, the classical binary recurrence for gives

Therefore this construction is asymptotically

and hence

So the real asymptotic gain is about (8.33%), even though the explicit uniform constant I extracted earlier was only . That was just a conservative “valid for all ” guarantee; asymptotically the construction is stronger.

A nice sanity check is along powers of four. If you recurse purely through the 4-way branch on , then in fact

which makes the coefficient completely explicit.

So the headline asymptotic is:

The lower-order term is linear and likely carries residue/digital fluctuations, so I would not expect a clean universal term for all .

USER:

Take a look at this paper, which introduces the k_n construction: https://arxiv.org/abs/1908.10914

Note that it’s conjectured that we can do even better with the constant here. How far up can you push the constant?

ASSISTANT:

You can push it essentially all the way to the paper’s conjectured leading constant.

Brian–Larson define as the largest number of vertices in a hypergraph with no isolated vertices and no partition larger than . Their lower construction is the binary recurrence

and Corollary 4.4 gives

On the other hand, Corollary 3.8 proves

and the paper explicitly conjectures that this upper coefficient is the right one, i.e.

(arXiv)

The right generalization of the gadget is not just “split into more parts,” but “split into parts and use every support size with harmonic weights.” Fix , and let

Take recursive blocks, each with partition budget . For every subset of size , add

new vertices supported on exactly the blocks in .

Why these weights? Suppose a chosen edge-set uses exactly one edge in the blocks indexed by , at most one edge in the blocks indexed by , and at least two edges in the other blocks. Then the new vertices counted exactly once are precisely those whose support satisfies . Their number is

Using the telescoping identity

with and , this becomes

So the outer vertices use up at most the slack left after paying for the active recursive blocks. That makes the substitution valid.

The total number of added vertices is