Graph Blocks and Coset Partition Refinements

Definitions and mathematical statement

The supplied record contains two separate questions. Its graph class, parameter ranges, and meaning of a coset are not fully specified; the qualifications below are therefore part of this draft.

For the graph question, the following makes the stated separation condition explicit under the interpretation that separation means vertex deletion in an undirected graph. For distinct vertices $x,y\in V(G)$, a separating set is a set $S\subseteq V(G)\setminus\{x,y\}$ such that $G-S$ contains no path from $x$ to $y$. For a positive integer $k$, a $k$-block is an inclusion-maximal set $B\subseteq V(G)$ satisfying \[ |B|\ge k,\qquad \forall x,y\in B\ (x\ne y),\quad \forall S\subseteq V(G)\setminus\{x,y\},\quad |S|<k\ \Longrightarrow\ x\text{ and }y\text{ are joined by a path in }G-S. \] Here maximality is with respect to inclusion among sets satisfying these conditions, rather than maximum cardinality. The source writes \[ \beta(G)=\max\{k\in{\mathbb{Z}}_{\ge1}:G\text{ has a }k\text{-block}\}. \] This expression defines a number only when the displayed set has a maximum. The source gives no convention for an empty set of admissible integers or an unbounded set. It also does not specify whether graphs must be finite, simple, or undirected; the vertex-deletion formulation above is conditional on the undirected interpretation.

Graph questions. Which properties of $G$ force the existence of a $k$-block, and how does $\beta(G)$, when defined, relate to other graph invariants? No particular sufficient condition, comparison invariant, bound, or equivalence is specified, so this is a research question rather than a single quantified conjecture.

Separate coset-partition question. Write $S_n$ for the symmetric group on $\{1,\ldots,n\}$, for a positive integer $n$. The record does not define a $t$-coset or specify the intended ranges of $n$ and $t$. To display the logical form without selecting a subgroup or coset convention, let $\mathcal C_t(S_n)$ denote the unspecified family intended by the term $t$-cosets. A partition is a family of nonempty, pairwise disjoint subsets whose union is the underlying set. A partition $\mathcal P$ refines a partition $\mathcal Q$ if every member of $\mathcal P$ is contained in a member of $\mathcal Q$. The source asks whether, for every intended admissible pair $(n,t)$, \[ \begin{gathered} \forall\mathcal P\text{ partition of }S_n,\qquad \mathcal P\subseteq\mathcal C_t(S_n) \ \Longrightarrow\\ \exists\mathcal Q\text{ partition of }S_n:\quad \mathcal Q\subseteq\mathcal C_{t-1}(S_n) \quad\text{and}\quad \forall C\in\mathcal P\ \exists D\in\mathcal Q\ (C\subseteq D). \end{gathered} \] The families $\mathcal C_t(S_n)$, the admissible parameter ranges, and any boundary convention for $t-1$ must be supplied before this becomes a fully specified mathematical assertion. The source's separate literature assessment concerns Hamilton-generation and does not resolve these formulation gaps.

Short English statement

The record asks which graph properties guarantee a $k$-block, how the largest such parameter relates to other graph invariants, and separately whether every partition of $S_n$ into $t$-cosets refines a partition into $(t-1)$-cosets. The graph domain, coset definition, and parameter ranges need clarification. The supplied Hamilton-generation literature assessment concerns a different topic.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $30002469$, title Graph Blocks and Coset Partition Refinements, exact source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. The record gives proposed year 2014 and names no proposer.
• Supplied report citation: Combinatorics (2014), Oberwolfach Reports, pp. 5--90, DOI 10.4171/owr/2014/01. https://doi.org/10.4171/owr/2014/01. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. No precise location within these pages is supplied for either question.
• Supplied literature source, labelled "Oberwolfach combinatorics report": https://ems.press/content/serial-article-files/46491.
• Supplied literature source, labelled "Hou--Yin, Dirac-type condition": https://arxiv.org/abs/2503.15950.
• Literature assessment date: 2026-08-21. This is supplied dated curation, not an independently verified assessment. It labels the record partially solved and asserts that Hou--Yin prove Hamilton-generation for sufficiently large odd $n$ at the Dirac threshold under Hamilton-connectedness, that the minimum-degree hypothesis implies that condition, and that the assertion for every odd $n$ remains unsettled. The background explicitly describes this as dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims. This assessment concerns Hamilton-generation, whereas the supplied statements concern graph blocks and coset partitions; its applicability is unresolved.
• The supplied statement-status label is corrected_verified. Its accompanying verification text reports a manual semantic, typographic, and LaTeX review and describes the cleanup as meaning-preserving, self-contained, and adding no unsupported source-dependent content. These are supplied registry claims, not mathematical or source verification performed for this draft.