we-solve (beta)

Math-2608 · mathematics · Combinatorics

Graph decomposition at the integral expectation threshold

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
Are there universal constants k and L such that every graph H on at most n vertices has an edge partition into k fixed pieces $H_i$ whose random-graph containment thresholds $p_c(H_i;n)$ are at most L times the integral expectation threshold q(H;n)?

Short English statement

Are there universal constants k and L such that every graph H on at most n vertices has an edge partition into k fixed pieces $H_i$ whose random-graph containment thresholds $p_c(H_i;n)$ are at most L times the integral expectation threshold q(H;n)?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-2608-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2608

Graph pieces at the expectation threshold: The manuscript’s result uses universal k>=2,L>=1 and all H on at most n vertices. Edge pieces may be empty/share vertices and their partition is fixed before the host is sampled. It compares each containment threshold with the integral q(H;n), not merely fractional q_f.

With the hypotheses and conventions above, the claimed result addresses the whole mathematical assertion on this page.

Graph decomposition at the integral expectation threshold

OpenAI's claim

Graph pieces at the expectation threshold: The paper claims a partition of any graph’s edge set into a universally bounded number of pieces whose containment thresholds are controlled by the graph’s integral expectation threshold. The pieces are fixed before host sampling, and their separate embeddings need not be compatible.

Mathematical statement of the claimed result

Mathematical claim 1.
For a finite simple graph $J$ on at most $n$ vertices, let $p_c(J;n)=\min\{p:\mathbb P(G(n,p)\supset J)\ge1/2\}$. Let $q(H;n)$ be the largest $p$ for which the family of edge sets containing $H$ has a containment cover $\mathcal C$ with $\sum_{S\in\mathcal C}p^{|S|}\le1/2$. Both parameters are set to zero for edgeless graphs. The claim gives absolute $k\ge2,L\ge1$ such that every $n\ge2$ and $H$ on at most $n$ vertices admit \[E(H)=E(H_1)\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}E(H_k),\qquad p_c(H_i;n)\le Lq(H;n).\] Pieces may be empty or share vertices; their choice precedes the random-host experiment. The separate copies are not required to identify any vertices common to the pieces.

Outline of the argument

Graph pieces at the expectation threshold: A covering input is converted into uniform neighborhood estimates for random hosts. Direct embedding lemmas handle the resulting structured graph pieces. The edge partition is assembled using those estimates so that a single universal number of pieces suffices, without requiring the piece embeddings to agree on their common vertices.

Formal verification

Family 175 describes Lean coverage for the integral/fractional threshold comparison and the discrete-convexity statement; graph decomposition is a later separate consequence.

Graph pieces at the expectation threshold: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →