This problem is about improving lower bounds on the values of a sequence, \(H(n)\), that arises in the study of simultaneous convergence of sets of infinite series, defined as follows.
A hypergraph \((V,\mathcal H)\) is said to contain a partition of size \(n\) if there is some \(D \subseteq V\) and \(\mathcal P \subseteq \mathcal H\) such that \(\|D\| = n\) and every member of \(D\) is contained in exactly one member of \(\mathcal P\). \(H(n)\) is the greatest \(k \in \mathbb{N}\) such that there is a hypergraph \((V,\mathcal H)\) with \(\|V\| = k\) having no isolated vertices and containing no partitions of size greater than \(n\).
It is believed that the best-known lower bounds for \(H(n)\) are suboptimal, even asymptotically, and that they can be improved by finding new constructions of hypergraphs. The goal of this problem is to find such a construction.
Warm-up: we ask for a value of \(n\) where constructions are already known.
Single Challenge: we ask for a value of \(n\) for which no construction is known, and which is probably too hard to brute-force.
Full Problem: we ask for a general algorithm for all \(n\).
Attempts by AI
We have evaluated the following models on this problem. “Warm-up” refers to an easier variant of the problem with a known solution.
AI Prompts
Warm-up
A hypergraph (V, H) is said to contain a partition of size n if there is some D ⊆ V and P ⊆ H such that |D| = n and every member of D is contained in exactly one member of P. Find a hypergraph (V, H) with no isolated vertices such that |V| ≥ 64, |H| ≤ 20, and (V, H) contains no partitions of size > 20.
Output the hypergraph as a string where vertices are labeled, 1, ..., |V|, and edges are denoted with curly braces. Example: {1,2,3},{2,4},{3,4,5},{1,5} Single challenge
A hypergraph (V, H) is said to contain a partition of size n if there is some D ⊆ V and P ⊆ H such that |D| = n and every member of D is contained in exactly one member of P. Find a hypergraph (V, H) with no isolated vertices such that |V| ≥ 66, |H| ≤ 20, and (V, H) contains no partitions of size > 20.
Output the hypergraph as a string where vertices are labeled, 1, ..., |V|, and edges are denoted with curly braces. Example: {1,2,3},{2,4},{3,4,5},{1,5} Full problem
A hypergraph (V, H) is said to contain a partition of size n if there is some D ⊆ V and P ⊆ H such that |D| = n and every member of D is contained in exactly one member of P. Define H(n) to be the largest integer k such that there is a hypergraph (V, H) with |V| = k having no isolated vertices and containing no partitions of size greater than n.
It is known that H(n) ≥ k_n, where k_n is defined recursively by the formula k_1 = 1 and k_n = ⌊n/2⌋ + k_⌊n/2⌋ + k_⌊(n+1)/2⌋.
Your task is to improve this lower bound by a constant factor, i.e. show that H(n) ≥ c*k_n for some c > 1. It is acceptable if this improvement does not work for small n, but it must already be "in effect" for n=15. You must demonstrate this improvement by providing an algorithm that takes n as input and produces a hypergraph witnessing H(n) ≥ c * k_n.
Please provide an algorithm that takes n as input and outputs the witness hypergraph as a string where vertices are labeled, 1, ..., |V|, and edges are denoted with curly braces. Example: {1,2,3},{2,4},{3,4,5},{1,5}
Solution format:
* Write a Python script defining a function `solution(n: int) -> str`.
* Do not include any code at the file level. You may include a `main` block for testing, but it will not be executed by the verifier.
* For n ≤ 100, the algorithm must complete within 10 minutes when run on a typical laptop. Mathematician survey
The author assessed the problem as follows.
Number of mathematicians highly familiar with the problem:
a majority of those working on a specialized topic (≈10)
Number of mathematicians who have made a serious attempt to solve the problem:
5–10
Rough guess of how long it would take an expert human to solve the problem:
1–3 months
Notability of a solution:
moderately interesting
A solution would be published:
in a standard specialty journal
Likelihood of a solution generating more interesting math:
fairly likely: the problem is rich enough that most solutions should open new avenues
Probability that the problem is solvable as stated:
95-99%