we-solve (beta)

Math-1132 · mathematics · Graph theory

Simultaneous partition of hypergraphs

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Fix an integer $r\ge2$. Let $H_1=(V,E_1)$ and $H_2=(V,E_2)$ be finite simple $r$-uniform hypergraphs on the same vertex set; each edge is an $r$-element subset and $m_i=|E_i|$. The edge sets may overlap. For a partition $\mathcal P=(V_1,\ldots,V_r)$ of $V$ into $r$ labelled, possibly empty parts, call an edge transversal if it meets every part, necessarily in exactly one vertex. Let $t_i(\mathcal P)$ count transversal edges of $H_i$.

The question asks for the following uniform asymptotic assertion: for every fixed $r$ and every $\varepsilon>0$, is there an integer $M=M(r,\varepsilon)$ such that whenever $m_1,m_2\ge M$, one partition $\mathcal P$ simultaneously satisfies \[ t_i(\mathcal P)\ge \left(\frac{r!}{r^r}-\varepsilon\right)m_i \qquad(i=1,2)? \] This spells out the source's $r!m_i/r^r-o(m_i)$ notation in the regime $\min(m_1,m_2)\to\infty$, with $r$ fixed. No balance condition on the part sizes or hypothesis on vertex degrees and codegrees is imposed.

Independently placing every vertex in one of $r$ parts with equal probability makes a given edge transversal with probability $r!/r^r$: its $r$ vertices must receive all distinct labels. Thus each hypergraph separately has a partition attaining its own expected count. The problem is whether one and the same partition can approach both expectations, even when their edges have very different overlap patterns and their edge counts grow at different rates.

Short English statement

Can one vertex partition simultaneously retain nearly the random-partition proportion of transversal edges in each of two uniform hypergraphs?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1132-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1132

Simultaneous partition of hypergraphs

Definitions and mathematical statement

Fix an integer $r\ge2$. Let $H_1=(V,E_1)$ and $H_2=(V,E_2)$ be finite simple $r$-uniform hypergraphs on the same vertex set; each edge is an $r$-element subset and $m_i=|E_i|$. The edge sets may overlap. For a partition $\mathcal P=(V_1,\ldots,V_r)$ of $V$ into $r$ labelled, possibly empty parts, call an edge transversal if it meets every part, necessarily in exactly one vertex. Let $t_i(\mathcal P)$ count transversal edges of $H_i$.

The question asks for the following uniform asymptotic assertion: for every fixed $r$ and every $\varepsilon>0$, is there an integer $M=M(r,\varepsilon)$ such that whenever $m_1,m_2\ge M$, one partition $\mathcal P$ simultaneously satisfies \[ t_i(\mathcal P)\ge \left(\frac{r!}{r^r}-\varepsilon\right)m_i \qquad(i=1,2)? \] This spells out the source's $r!m_i/r^r-o(m_i)$ notation in the regime $\min(m_1,m_2)\to\infty$, with $r$ fixed. No balance condition on the part sizes or hypothesis on vertex degrees and codegrees is imposed.

Independently placing every vertex in one of $r$ parts with equal probability makes a given edge transversal with probability $r!/r^r$: its $r$ vertices must receive all distinct labels. Thus each hypergraph separately has a partition attaining its own expected count. The problem is whether one and the same partition can approach both expectations, even when their edges have very different overlap patterns and their edge counts grow at different rates.

Short English statement

Can one vertex partition simultaneously retain nearly the random-partition proportion of transversal edges in each of two uniform hypergraphs?

Research attempt

Scope and process.
GPT-6 Astra Ultra, 2 October 2026. The canonical formulation above is retained. This attempt uses a primary-source literature audit, independent restricted proofs, and adversarial checks. Reproved results are not claimed as new. Numerical tests below are reproducible in scripts/check_attempt_batch03_extremal_2026_10_02.py.
Literature and attack.
Section 2 of Kühn--Osthus [S3] states the hypergraph conjecture and observes that it holds when each maximum pair codegree is $o(m_i)$, omitting details. We give an explicit covariance calculation for that restricted claim, including constants for linear hypergraphs, and exhibit why concentration alone does not remove the codegree assumption. The number of hypergraphs is two, $r$ is fixed, and both edge counts tend to infinity as required above.
Exact covariance by intersection size.
Colour every vertex independently and uniformly with one of the $r$ labelled colours. The colour classes are the desired parts. For an edge $e$, let $I_e$ indicate that its vertices have all different colours, and put $p=r!/r^r$. Then $\mathbb E I_e=p$. If distinct edges $e,f$ intersect in $j$ vertices, conditioning on the colours of $e$ gives \[ \mathbb E(I_eI_f)=\frac{r!(r-j)!}{r^{2r-j}}. \] Indeed, there are $r!$ favourable assignments on $e$, and exactly $(r-j)!$ assignments of the unused colours to $f\setminus e$. For $j=0$ or $1$, the expression equals $p^2$. Thus edges sharing only one vertex have zero covariance despite not being supported on disjoint vertex sets.

Let $T$ count transversal edges in one hypergraph with $m$ edges, and let $B$ count unordered pairs of distinct edges intersecting in at least two vertices. Using the trivial upper bound one for each remaining covariance yields \[ \operatorname{Var}(T)\le mp(1-p)+2B\le m/4+2B. \] For a linear hypergraph, $B=0$. Chebyshev and a union bound consequently give \[ \Pr\left[\text{some }T_i<(p-\varepsilon)m_i\right] \le\frac{1}{4\varepsilon^2m_1}+\frac{1}{4\varepsilon^2m_2}. \] If both $m_i>1/(2\varepsilon^2)$, the right side is less than one, proving existence of a simultaneous partition. For $r=2$, every simple graph is linear, so this proves that entire boundary case of the catalogue problem, consistently with the graph results in [S3].

A quantitative codegree extension.
Write $d_{xy}$ for the number of edges containing the pair $\{x,y\}$, and $D=\max d_{xy}$. Counting each intersecting edge pair once or more gives \[ B\le\sum_{\{x,y\}}\binom{d_{xy}}2 \le\frac{D-1}{2}\sum_{\{x,y\}}d_{xy} =\frac{D-1}{2}\binom r2m. \] Consequently \[ \Pr[T<(p-\varepsilon)m] \le\frac{1/4+\binom r2(D-1)}{\varepsilon^2m}. \] In particular, if $D_i=o(m_i)$ for both hypergraphs, the two failure probabilities tend to zero. This proves the stated asymptotic restricted result without any maximum vertex-degree bound. For an explicit sufficient regime, take $C=\binom r2$, assume $D_i\le\varepsilon^2m_i/(8C)$ and $m_i\ge2/\varepsilon^2$. Each failure probability is at most $1/4$, so some common partition works.
Why large codegree is a real obstruction to this method.
For $r\ge3$, let every edge consist of a common $(r-1)$-vertex core and one private vertex. If two core vertices receive the same colour, there are no transversal edges at all. This event has a positive probability depending only on $r$, independently of $m$. Hence relative concentration around $pm$ cannot hold for all hypergraphs in this distribution. Yet this sunflower is not a counterexample to the existence statement: give the core distinct colours and all private vertices the remaining colour, obtaining $T=m$. The calculation isolates the missing step as coordinated treatment of large common cores in both hypergraphs, rather than insufficient sample size.
Verification and final status.
The script enumerates colourings for $r=2,3,4$ and all possible intersection sizes of two distinct edges, verifying the exact probability formula with rational arithmetic. It also checks the sunflower failure event. Empty colour classes are permitted throughout; no balance condition has entered. The graph case, linear case, and sublinear pair-codegree case are established, but arbitrary large pair codegrees are untreated. The unrestricted simultaneous hypergraph claim is UNRESOLVED by this attempt.

Sources

Go to contribution →