PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamilton-connected cores and five cycle--wheel Ramsey numbers

Zehui Shao, Hanxin Jiang

arXiv:2609.39508v1math.COcs.DM

TL;DR

The published result for W11 covered n≥16, leaving the boundary cases n=14,15 without located published proofs. This paper uses structural core arguments and critical-coloring analyses to prove those cases and three smaller-wheel values, extending the W11 formula to n≥14.

  • Problem

    The published W11 formula covers n≥16, while the boundary cases n=14,15 were not covered by that theorem and no published proofs were located.

    Source: §1 · pp. 1–2

  • Method

    The proofs use a Hamilton-connected core lemma, with critical-cycle-coloring structure for W7 and local lemmas and cycle-shortening for W9.

    Source: §1 · p. 3, §9 · p. 42

  • Results

    R(C14, W11)=27, R(C15, W11)=29, and R(Cn, W11)=2n−1 for every n≥14; also R(C8, W7)=15, R(C9, W7)=17, and R(C8, W9)=15.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The structural proofs extend the published W11 formula's proved range from n≥16 to n≥14.

    Source: §1 · pp. 1–2

    The arguments do not settle R(Cn, W11) for 10≤n≤13; the remaining difficulty is finding suitable cores or prescribed-endpoint paths.

    Source: §9 · p. 42

Abstract

from arXiv · show

Let $W_s=K_1+C_{s-1}$ denote the wheel on $s$ vertices. We give structural proofs that $R(C_{14},W_{11})=27$ and $R(C_{15},W_{11})=29$. Together with the theorem of Chen et al. for $n\ge16$, these equalities give $R(C_n,W_{11})=2n-1$ for every $n\ge14$. The two boundary values were included in an earlier survey announcement. We also give structural proofs of $R(C_8,W_7)=15$, $R(C_9,W_7)=17$, and $R(C_8,W_9)=15$. The common starting point is a Hamilton-connected core lemma. For the eleven-vertex wheel, bounds on vertex connectivity and on the matching number of a bipartite graph associated with a local cycle yield a vertex cut of order nine. Paths with prescribed endpoints then rule out every possible pair of orders of the two remaining vertex sets. For the smaller wheels, we use the structure of critical cycle colorings and local cycle-shortening arguments. We also give complete structural classifications of the $(C_8,C_6)$- and $(C_9,C_6)$-critical colorings, recovering the previously reported counts 24 and 26. All proofs are combinatorial and use no exhaustive graph enumeration.

1 Introduction

The paper gives structural proofs for the two boundary cases that extend the established W11 Ramsey formula to every n ≥14. It also proves three smaller-wheel values using a common Hamilton-connected core approach and structural analyses of critical colorings.

1 Introduction

  • R(C_n, W_11) = 2n−1 for every n ≥14, extending the published theorem’s range from n ≥16.The boundary cases are R(C_14, W_11) = 27 and R(C_15, W_11) = 29; their numerical values had appeared in an earlier survey announcement.Source: §1 · pp. 1–2
  • For W11, connectivity and local matching bounds yield a vertex cut of order nine, after which prescribed-endpoint paths rule out the remaining set orders.The local matching numbers are at most 4 for n = 14 and 5 for n = 15.Source: §1 · p. 2
  • The reported values are R(C8, W7) = 15, R(C9, W7) = 17, and R(C8, W9) = 15; structural proofs are identified as the contribution only for the first two equalities.Source: §1 · p. 2
  • The common core lemma reduces the Ramsey arguments to finding a Hamilton-connected subgraph of order n−1, while W7 cores come from critical cycle colorings.The defined critical classes need not be edge-maximal; their complete structural classifications have 24 classes for n = 8 and 26 for n = 9.Source: §1 · p. 3
  • For W9, a local lemma and cycle-shortening arguments establish the value using explicit path constructions rather than computer enumeration.The proof finds a monochromatic Hamilton-connected subgraph on seven vertices in every K10 coloring without a monochromatic C8.Source: §1 · p. 3

2 Preliminaries and a core lemma

The core lemma turns a Hamilton-connected subgraph into a cycle-or-wheel alternative under explicit parameter conditions. Supporting preliminaries include a degree criterion for Hamilton-connectedness and restrictions on how vertices can attach to cycles.

2 Preliminaries and a core lemma

  • A graph Q of order r ≥3 with minimum degree at least (r+1)/2 is Hamilton-connected.Hamilton-connectedness means every pair of distinct vertices can be joined by a spanning path.Source: §2 · p. 3
  • The core lemma adapts spanning-path and wheel constructions to incomplete cross-connections between the core and outside vertices.When no outside vertex has enough blue neighbors outside the core, the proof uses Dirac’s theorem; Hall’s theorem selects distinct core connectors for the alternating blue rim otherwise.Source: §2 · p. 4
  • If a graph of order 2n−1 contains a Hamilton-connected subgraph of order n−1, it contains C_n or K_1 + C_2k when k ≥2 and n ≥max{2k, k+4}.The argument uses the core’s spanning paths: each outside vertex has at most one neighbor in the core if C_n is absent; Hall’s theorem constructs a wheel when an outside vertex has enough blue neighbors, and Dirac’s theorem handles the alternative.Source: §2 · p. 4
  • For W11, the lemma applies at (n, k) = (14, 5) and (15, 5); for W7 it applies at (8, 3) and (9, 3), with two n = 9 bipartite exceptions handled separately.For W9, (n, k) = (8, 4) gives the reduction used in Section 8.Source: §2 · pp. 4–5
  • If adding a vertex to a red cycle cannot create a longer red cycle, its red neighbors on the cycle are independent, and their successors and predecessors each form blue cliques.The restriction follows by inserting the outside vertex between consecutive red neighbors or using a red chord to form a spanning path that closes through it.Source: §2 · p. 5

3 Preliminary structure for the eleven-vertex wheel

For the eleven-vertex wheel, the section establishes structural constraints on putative counterexamples and develops path lemmas for handling vertex separations. These reductions use degree bounds, large red components, Hamilton-connected cores, and prescribed paths.

3.1 Degree and blue separation

  • For n = 14, a counterexample has minimum red degree nine and is nonbipartite and 2-connected; for n = 15, the corresponding degree is ten.The n = 14 conclusion follows from Corollary 3.2, and the n = 15 conclusion from Corollary 3.3.Source: §3.1 · pp. 5–6
  • In an n = 15 counterexample, every vertex of red degree ten has a blue neighborhood of order eighteen containing a red C14.The blue neighborhood has no blue C10, so R(C14, C10) = 18 yields the red cycle.Source: §3.1 · p. 6
  • With all cross-edges blue and no blue W11, a set of five mutually blue-adjacent vertices forces the blue graph on a disjoint set of at least six vertices to have at most one edge.Two blue edges there would allow four disjoint paths to be joined into a blue C10 with a hub among the five vertices.Source: §3.1 · p. 6
  • If the red graph induced by a minimum-degree vertex’s neighborhood is disconnected, one component contains all but at most one of its vertices.This applies for n = 14 and n = 15.Source: §3.1 · p. 6
  • When the other red components contain four vertices, the remaining red graph is nearly complete and Hamilton-connected, contradicting the core lemma.Its minimum red degree is at least |A| − 2, enough for the stated Hamilton-connectedness criterion and Lemma 2.2.Source: §3.1 · p. 7

3.2 Paths through a separation

  • For a four-vertex set B under Lemma 3.7’s degree and neighborhood conditions, every pair in S has red paths with exactly two, three, or four internal vertices in B.The proof handles the possible red graphs on B: C4, K4 minus an edge, and K4.Source: §3.2 · pp. 7–8
  • An eight-vertex set U with the stated red-degree condition yields C14 when s = 7 and G[U] contains a red P3, or C15 when s = 8 and G[U] contains a red edge.The proof joins blocks from U through distinct vertices of S, using Hall’s condition to select the connectors.Source: §3.2 · p. 8
  • Two disjoint 2h-vertex sets of minimum degree at least h, with h + 1 paired attachments through outside vertices, force C2h+4.If a Hamilton path in one set has endpoints whose paired vertices in the other set are adjacent, the paths and attachment edges form the cycle.Source: §3.2 · p. 8

4 Connectivity for the eleven-vertex wheel

This section develops connectivity constraints for counterexamples involving the eleven-vertex wheel by analyzing the components left by small vertex cuts. Matching and path restrictions eliminate possible cuts, establishing 8-connectivity for n = 14 and at least 9-connectivity for the n = 15 red graph under its counterexample assumptions.

4 Connectivity for the eleven-vertex wheel

  • The cut analysis combines component-order bounds with prescribed-path constructions and degree theorems to rule out candidate red cycles.For a cut S, component sizes are bounded below using the minimum degree; small components are addressed with path constructions, while larger cases use cycle and Hamiltonicity criteria.Source: §4 · p. 9

4.1 Eight-connectivity at n = 14

  • For n = 14, a six-vertex cut can leave only components of orders (17, 4), while every seven-vertex cut leaves two components of order ten.The (12, 9) six-cut case and the other seven-cut component orders are excluded using red-cycle and Hamiltonicity arguments.Source: §4.1 · pp. 11, 13, 14
  • For n = 14, the red graph is at least 8-connected.The proof rules out six- and seven-vertex cuts, using component-size bounds, red paths, and matching arguments.Source: §4.1 · pp. 12–14

4.2.1 Excluding cuts of order at most seven

  • For n = 15, the red graph is at least 7-connected: all cuts of order at most six are excluded.Component-size bounds and red minimum-degree arguments reduce candidate cases to graphs where Dirac’s or Chvátal’s theorem yields a red C15.Source: §4.2.1 · pp. 14–15
  • For n = 15, a seven-vertex cut must leave exactly two components, with orders (18, 4), (13, 9), or (11, 11).Three or more components are ruled out using blue-wheel constructions or, in the exceptional case, Hamilton-connectivity.Source: §4.2.1 · p. 16
  • Under the n = 15 counterexample assumptions, the red graph is at least 8-connected, ruling out cuts of order at most seven.After narrowing possible component orders, matching-saturating cuts and a Hamilton path through 11 selected vertices yield a red C15 contradiction.Source: §4.2.1 · p. 17

4.2.2 Excluding eight-vertex cuts

  • The red graph is at least 9-connected: any eight-vertex cut would leave components of orders (18, 3), but that configuration is impossible.The proof uses a matching saturating the cut, a red C14 in the larger component, and forbidden path orders to derive a contradiction.Source: §4.2.2 · pp. 18–19

5 The fourteen-cycle versus the eleven-vertex wheel

The section proves R(C14, W11) = 27 by bounding a local matching, producing a nine-vertex cut, and excluding every possible pair of side sizes with red paths.

5 The fourteen-cycle versus the eleven-vertex wheel

  • A matching of size five between a red C12 and the minimum-degree vertex’s red neighborhood would force a vertex of red degree at most eight, contradicting minimum degree nine.The proof uses forbidden spanning paths to force blue edges incident to one cycle vertex, bounding its red degree.Source: §5 · p. 20
  • R(C14, W11) = 27; K13 ∪ K13 on 26 vertices has no red C14, while its bipartite blue complement has no W11.The upper-bound argument excludes all possible side-size distributions after constructing the cut.Source: §5 · pp. 20–22
  • The matching bound yields a vertex cover of size four; enlarging it and adding five vertices outside the cycle gives a nine-vertex cut with side orders (12, 6), (11, 7), (10, 8), or (9, 9).All edges between the two sides are blue, and each side vertex has at most four blue neighbors within its side.Source: §5 · pp. 19, 21
  • For side orders (12, 6) and (11, 7), matching edges to the cut select endpoints for a Hamilton-connected path that closes through the smaller side to form C14.The larger side contains an eleven-vertex subset with minimum red degree sufficient for Hamilton-connectedness.Source: §5 · p. 21
  • For a ten–eight distribution, if G[L] is not Hamilton-connected, Theorem 3 of Shih et al. gives one of two forms; the second yields a red 14-cycle, excluding the distribution in both orientations.Source: §5 · pp. 21–22

6 The fifteen-cycle versus the eleven-vertex wheel

The section proves R(C15, W11) = 29 by establishing a nine-vertex cut and ruling out all resulting component-size pairs with paths having prescribed endpoints.

6 The fifteen-cycle versus the eleven-vertex wheel

  • A red C14 in the red neighborhood yields a vertex cut of order nine, leaving two components whose orders, up to exchange, are (13, 7), (12, 8), (11, 9), or (10, 10).The matching number between the local cycle and the red neighborhood is five, giving a minimum vertex cover of size five.Source: §6 · p. 22, §6.1 · p. 25, §6.2 · p. 26

6.1 Edges between the local cycle and the red neighborhood

  • In the same-parity case, the seven odd-indexed vertices form a blue clique with restricted blue connections to an eleven-vertex set, and Lemma 6.1 forces a red C15.The lemma assumes no blue C10, a blue clique of seven vertices, at most two blue neighbors in the other set per vertex, and at most two vertices with more than one such neighbor.Source: §6.1 · pp. 23–24
  • For mixed-parity endpoint configurations, forced blue edges give a vertex red degree at most nine, contradicting the required minimum degree ten.The argument also establishes that the cut leaves two red components, with each vertex having at most four blue neighbors within its component.Source: §6.1 · pp. 24–25
  • For each red C14 in the neighborhood, the matching number between its vertices and the red neighborhood is exactly five, using connectivity for the lower bound and forbidden paths for the upper bound.The upper-bound argument separates same-parity and mixed-parity endpoint configurations.Source: §6.1 · pp. 23, 25

6 The fifteen-cycle versus the eleven-vertex wheel

  • R(C15, W11) = 29; K14 ∪ K14 on 28 vertices has no red C15, and its bipartite blue complement contains no wheel.The upper-bound proof excludes each of the four possible component-size pairs.Source: §6.2 · pp. 25–27

6.2 The final nine-vertex cut

  • For component pairs (13, 7), (12, 8), and (11, 9), Hamilton-connected paths on the larger side close through the smaller side and cut vertices to form C15.In the (10, 10) case, the proof rules out non-Hamilton-connected structures using prescribed-endpoint paths and the constraints between the components.Source: §6.2 · pp. 26–27

7 The seven-vertex wheel

The section identifies Hamilton-connected cores in the critical cycle colorings for the seven-vertex wheel and uses them to prove the two Ramsey equalities. For the nine-vertex graphs, the core result has two explicitly classified bipartite exceptions, which are handled separately.

7.1 The critical graphs for (C8, C6)

  • Every graph in H8 contains a Hamilton-connected induced subgraph on seven vertices.A red C7 is found, each of the two outside vertices has at most one red neighbor on it, and the resulting core has red minimum degree at least four.Source: §7.1 · pp. 27–28

7.2 The critical graphs for (C9, C6)

  • Every nonbipartite graph in H9 contains a Hamilton-connected induced subgraph on eight vertices; the bipartite graphs are exactly K5,5 and K5,5 − e.The two bipartite cases are treated separately in the Ramsey argument.Source: §7.2 · p. 30, §7.3 · pp. 30–31

7.3 The two Ramsey equalities

  • For n = 8 and n = 9, the red graph 2K_(n−1) and its bipartite complement give the lower bound 2n − 1; both Ramsey numbers equal these bounds, 15 and 17, respectively.Source: §7.3 · pp. 30–31
  • For n = 8 or 9, a graph on 2n − 1 vertices avoiding red Cn and blue W7 has minimum red degree n − 3, yielding a critical graph in Hn.The degree bound δ(G) ≤ n − 3 is used to obtain a vertex whose red neighborhood has order n + 1 and belongs to Hn.Source: §7.3 · p. 30

8 The nine-vertex wheel

This section proves R(C8, W9) = 15 through structural analysis of the coloring and local neighborhoods, including a Hamilton-connected subgraph result and cycle-forcing arguments.

8 The nine-vertex wheel

  • R(C8, W9) = 15; red graph 2K7 gives the lower bound, and the upper-bound argument establishes minimum degree five.The proof assumes a coloring of K15 with neither a red C8 nor a blue W9, then restricts its red graph.Source: §8 · p. 31

8.1 Basic structural reductions

  • Every eight-vertex set spans at least three red edges, and the red graph is 2-connected.The first property rules out a blue K8; the second is established by excluding disconnected and cut-vertex cases.Source: §8.1 · p. 31

8.2 Hamilton-connected subgraphs in blue neighborhoods

  • In a red–blue coloring of K10, a red K6 guarantees that the graph contains a red C8, a blue C8, or a red Hamilton-connected subgraph on seven vertices.If |X| = 7 and |Y| = 3 in a red–blue coloring of a complete graph, each vertex of Y has at most one blue neighbor in X, and no red C8 exists, then the red graph on X has at most two edges.Source: §8.2 · pp. 32–33
  • A vertex of red degree four has a ten-vertex blue neighborhood with no seven-vertex Hamilton-connected subgraph in either color, no monochromatic K6, and no cycle longer than seven.The blue-neighborhood constraints combine Corollary 8.1, Lemma 8.7, and the exclusion of monochromatic cycles of lengths nine and ten.Source: §8.2 · p. 34

8.3 The ten-vertex local dichotomy

  • For k = 8, the bound pairs at n = 8, 9, 10 are (19, 19), (21, 22), and (23, 25); any color graph with at least 23 edges in the specified coloring is 2-connected.Also, a seven-vertex graph with minimum degree at least three and at least seventeen edges is Hamilton-connected.Source: §8.3 · pp. 34–35
  • At the threshold of 23 edges, a 2-connected ten-vertex graph with circumference seven lies in a spanning-subgraph family Gi, i ∈ {1, 2, 3, 5, 6, 7, 8}, or has a seven-cycle with three independent degree-two outside vertices; in the latter case e(F) = 23 and e(F[V(C)]) = 17.This structural statement uses the published stability analysis of Füredi et al. [9].Source: §8.3 · p. 36
  • Every red–blue coloring of K10 with no monochromatic C8 contains a monochromatic Hamilton-connected subgraph on seven vertices.The proof uses a 10-vertex local dichotomy for graphs with at least 23 edges and circumference at most seven.Source: §8.3 · p. 37
  • Every 15-vertex graph with no red C8 and no blue W9 has minimum red degree exactly five.The degree-four case would contradict the K10 Hamilton-connected-subgraph result on a vertex’s blue neighborhood.Source: §8.3 · p. 38

8.4 Nine-cycles and ten-cycles

  • A 15-vertex graph with minimum degree at least five that contains C9 also contains C8.Source: §8.4 · p. 38
  • In the Ramsey argument, a red cycle of length 9 or 10 must occur, and the ten-cycle-only case is impossible, so a red C9 exists.Source: §8.4 · p. 40
  • The cycle results, together with minimum red degree five, yield R(C8, W9) = 15.A hypothetical counterexample has minimum red degree five, contains a red C9, and therefore contains a red C8.Source: §8.4 · pp. 38, 40, 41, §8.3 · p. 38

9 Concluding remarks

The paper extends the established W11 Ramsey formula to n = 14 and 15 using a common Hamilton-connected core approach. It also proves three smaller-wheel values and identifies unresolved cases and possible extensions.

9 Concluding remarks

  • The W11 formula extends from n ≥16 to n ≥14 through a vertex cut of order nine and paths with prescribed endpoints.The proof combines vertex-connectivity bounds and a small vertex cover of a bipartite graph associated with a local cycle.Source: §9 · pp. 41–42
  • The common core lemma also proves the three smaller-wheel values, using critical cycle colorings for W7 and local lemmas with cycle-shortening for W9.The Appendix A classifications account for the previously reported counts of critical colorings.Source: §9 · p. 42
  • The arguments do not settle R(Cn, W11) for 10 ≤n ≤13, because the available lower bounds do not provide the connectivity and path structure used in the proofs.Lemma 2.2 covers these parameter values, but forcing a suitable core or constructing paths of the required orders remains difficult.Source: §9 · p. 42
  • Possible extensions include classifying relevant blue neighborhoods and replacing full Hamilton-connectedness with specified endpoint-pair path conditions.The corresponding structural statements for the four remaining parameters are not proved.Source: §9 · p. 42

A The complete critical classifications

The appendix gives complete structural classifications of the critical families H8 and H9. A local restriction on blue core edges and a necessity-and-sufficiency argument underpin the classifications and their orbit counts.

A The complete critical classifications

Loading 2609.39508v1…