Equivalence of Graphs in Strong Ramsey Games

Definitions and mathematical statement

The supplied record does not define $q$-equivalence or the graph sum $+$. The following is a conditional formulation using the conventional Ramsey interpretation; these conventions require confirmation against the cited report.

Work with finite simple undirected graphs. For an integer $q\ge 2$, write $G\to_q H$ if every edge-colouring $c:E(G)\to\{1,\ldots,q\}$ contains a monochromatic subgraph isomorphic to $H$. Copies are not required to be induced, and the colouring need not use every colour. Define \[ H\sim_q H'\quad\Longleftrightarrow\quad \text{for every finite simple graph }G,\quad (G\to_q H\iff G\to_q H'). \] Let $K_k$ denote the complete graph on $k$ vertices, let $K_{1,t}$ denote the star with $t$ leaves and hence $t+1$ vertices, and interpret $H+H'$ as the disjoint union of $H$ and $H'$. A tree is a nonempty connected graph with no cycle.

For a positive integer $k$, define the candidate sets \[ \begin{aligned} \mathcal S_k&=\{t\in{\mathbb{Z}}_{\ge1}:K_k\sim_2(K_k+K_{1,t})\},\\ \mathcal T_k&=\{t\in{\mathbb{Z}}_{\ge1}:\text{there exists a tree }T\text{ with }|V(T)|=t \text{ and }K_k\sim_2(K_k+T)\}. \end{aligned} \] Determine the largest elements of $\mathcal S_k$ and $\mathcal T_k$, as functions of $k$, wherever such largest elements exist. The two functions requested by the source are separate functions, although the source denotes both by $t(k)$. If either set is empty or unbounded, its requested largest element does not exist; the supplied record does not specify a convention for those cases.

Furthermore, determine whether \[ \forall q\in{\mathbb{Z}}_{\ge2}\ \exists H,H'\quad \left(H,H'\text{ are connected finite simple graphs},\quad H\not\cong H',\quad H\sim_q H'\right). \] Here the graphs may depend on $q$.

The positive-integer ranges above specify a provisional rendering: the source gives no lower bound on $k$, does not state whether $t=0$ is allowed for the star question, and does not address degenerate cases. Its title refers to strong Ramsey games, whereas its statement supplies no game rules or game-based definition of equivalence. Consequently, the edge-colouring formulation above must be reviewed before it is treated as the intended statement.

Short English statement

Under the provisional interpretation of equivalence as having exactly the same $q$-colour Ramsey graphs, determine how large a disjoint star, or some disjoint tree, can be added to $K_k$ without changing its two-colour Ramsey graphs. Also ask whether, for every integer $q\ge2$, two non-isomorphic connected graphs can have exactly the same $q$-colour Ramsey graphs. The equivalence convention and parameter boundaries require source confirmation.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003972$, source problem code catalogue entry, title: Equivalence of Graphs in Strong Ramsey Games. Collection: Oberwolfach Reports Open Problems. No individual proposer is supplied; the proposed year is recorded as 2018.
• Supplied report citation: Mini-Workshop: Positional Games (2019), Oberwolfach Reports, pp. 2715--2738, DOI 10.4171/owr/2018/44. https://doi.org/10.4171/owr/2018/44. The background describes these reports as records of mathematical workshops and their open-problem discussions. The supplied workshop year and the year appearing in the DOI differ; this draft retains both without resolving the discrepancy.
• Supplied literature reference, labelled "Ramsey equivalence": https://arxiv.org/abs/1809.09232. No authors or fuller bibliographic information are supplied.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that known Ramsey equivalence results provide partial restrictions and examples, while the requested connected graph classification and largest $t$ values remain open. This is supplied dated curation, not an independently verified literature assessment. Its reference to a connected graph classification is broader than the explicit connected-pair existence question in the statement. The background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports a manual semantic, typographic, and LaTeX review. These are supplied editorial labels and do not establish mathematical correctness or resolve the formulation issues recorded here. The cited external sources have not been independently consulted for this draft.