Pith. sign in

REVIEW 4 minor 25 references

Computation of small reflective and dihedral Ramsey numbers

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Reflective and dihedral Ramsey numbers for paths, stars, cycles and matchings admit closed formulas and small exact values via SAT.

desk verdict Solid computational extension of the authors’ own permutational framework: a few clean closed formulas plus public SAT tables and dihedral=cyclic conjectures; niche but usable. read the letter →

arxiv 2607.06817 v2 pith:7TIP25F4 submitted 2026-07-07 math.CO cs.DM

Ivan Damnjanović , Irena {DJ}or{j̣ević This is my paper · ORCID
classification math.COcs.DM MSC 05D1005C55
keywords RamseynumbersreflectivedihedralpermutationalorderedgraphsSATencodingalternatingpathsstart-centralstars
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper defines reflective and dihedral Ramsey numbers as special cases of permutational Ramsey numbers, in which the allowed embeddings of a graph may reverse its linear order or rotate and reverse a cyclic order. It shows that these numbers often collapse to already-known ordered or cyclic Ramsey numbers when one argument has reflection symmetry, and it proves exact product-type formulas for any connected graph against a monotone path and for start-central stars against monotone paths, cycles and complete graphs. Using a Boolean-SAT encoding of forbidden monochromatic embeddings and the Kissat solver, the authors compute tables of exact values and lower bounds for alternating paths, start-central stars and nested matchings of small order. The computations support several clean conjectures that dihedral numbers coincide with cyclic numbers whenever one argument is an alternating path. The results give a concrete computational and theoretical bridge between ordered, cyclic and classical Ramsey theory for the same families of graphs.

What carries the argument

Γ-embeddability: a graph H is Γ-embeddable in G when some group element of Γ can be composed with an order-preserving injection to produce a homomorphism into G. The non-existence of monochromatic Γ-embeddings is encoded as a CNF whose clauses forbid every possible increasing image of every group translate of each forbidden edge set; satisfiability of that CNF yields a lower bound and unsatisfiability an upper bound.

What would settle it

Exhibit a concrete 2-edge-coloring of Kn that avoids every reflective (respectively dihedral) embedding of the two claimed graphs for any n equal to a reported exact value, or produce a counter-example pair of alternating-path orders that separates the dihedral number from the cyclic number.

Watch

Extended reading notes

Core claim

For any connected graph H of order a and any permutation group on its vertices, the permutational Ramsey number against a monotone path of order b (with the trivial group) equals 1+(a-1)(b-1); the same closed formula holds for reflective Ramsey numbers of alternating paths and of start-central stars against monotone paths, and for reflective (hence also ordered, cyclic and dihedral) numbers of start-central stars against monotone cycles and complete graphs. Extensive SAT computations supply exact small reflective and dihedral values for the remaining combinations and motivate the conjecture that the dihedral number of an alternating path against any of the listed families equals the correspo

Load-bearing premise

The SAT encoding together with Kissat’s unsatisfiability answers correctly certify that no avoiding 2-edge-coloring exists, and the chosen time limits do not turn an exact value into a mere lower bound.

Editorial extensions

If this is right

  • Any connected graph of order a forces a monochromatic monotone path of length b in every 2-edge-coloring of the complete graph on 1+(a-1)(b-1) vertices once the path is required only to be increasing.
  • Reflective Ramsey numbers of start-central stars against monotone cycles or complete graphs are identical to the corresponding ordered, cyclic and classical numbers, all equal to 1+(a-1)(b-1).
  • If the dihedral-versus-cyclic conjectures hold, every previously computed cyclic Ramsey number involving an alternating path immediately supplies the matching dihedral number.
  • The same SAT pipeline yields systematic lower and upper bounds for any other pair of graphs once their reflection or dihedral groups are substituted into the clause generator.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Tailoring the permutation group to the automorphism group of a graph (for example fixing the apex of a fan) may produce still smaller intermediate Ramsey numbers that interpolate between ordered and classical values.
  • The observed near-equality of reflective and ordered numbers suggests that allowing a single reflection rarely reduces the Ramsey number by more than one for the families studied.
  • Hardness spikes for odd-order alternating paths against start-central stars under the dihedral group may indicate a combinatorial phase transition worth a separate theoretical analysis.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper introduces reflective and dihedral Ramsey numbers as special cases of permutational Ramsey numbers (groups generated by reflection, or by cyclic shift plus reflection). It proves closed formulas for several families, most notably Theorem 4.1: for any connected H of order a and any group Γ on V(H), R(H^Γ,(P_mon_b)^Λ)=1+(a-1)(b-1) when Λ is trivial; Corollaries 4.2–4.3, Propositions 4.10 and 4.12, and Corollaries 4.14–4.16 then give exact reflective (and often dihedral) values for alternating paths or start-central stars versus monotone paths, cycles and complete graphs. The bulk of the work is a SAT encoding (clauses (1)–(2) in §3) solved by Kissat that produces exact small values and lower bounds for the remaining pairs among alternating/monotone paths, monotone cycles, start-central stars, completes and nested matchings (Tables 3–14), together with several conjectures that R_dih coincides with R_cyc for alternating-path arguments.

Significance. The work cleanly fills the two natural intermediate cases between ordered and cyclic Ramsey numbers left open by the authors’ earlier framework. Theorem 4.1 and its corollaries are elementary but useful closed formulas that unify several previously scattered observations; the extensive, fully reproducible SAT tables (source code, Kissat logs and graph6 colorings released) supply concrete data that both confirm known ordered/cyclic values and generate plausible dihedral=cyclic conjectures. The contribution is solid computational combinatorics with a modest theoretical advance, appropriate for a specialized discrete-mathematics journal.

minor comments (4)
  1. Table 2 lists many entries as “—” (no formula known or conjectured). A short remark in §4 explaining why those families resist a simple closed form would help the reader assess the scope of the conjectures that are offered.
  2. The time limits (2 min generation / 3 min Kissat) and order threshold 30 are stated only in the experimental paragraph of §4. Moving them into §3 (Methodology) would make the computational claims self-contained.
  3. A few tables (e.g., Table 3, a=3 row) mix exact integers with “≥30”-style lower bounds; a uniform typographic convention for lower bounds would improve readability.
  4. The heavy dependence on the authors’ prior ordered/cyclic paper [4] and code base [5] is legitimate, but a one-sentence pointer in the introduction to the precise differences in the SAT encoding would clarify novelty for readers unfamiliar with that work.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: closed-form theorems rest on independent inductive/pigeonhole arguments; SAT tables and dihedral=cyclic conjectures are experimental outputs, not definitional fits.

full rationale

The paper's strongest claims (Theorem 4.1 and its corollaries for reflective numbers of alternating paths/start-central stars versus monotone paths, Proposition 4.12 and Corollary 4.16 for stars versus cycles/completes) are proved by elementary induction, pigeonhole, and subgraph monotonicity that do not depend on the SAT pipeline or on any fitted parameter. The SAT encoding (clauses (1)–(2)) and Kissat runs produce external certificates of (un)satisfiability that are released as graph6 colorings and solver logs; they are not parameters fitted to the target Ramsey numbers and then re-presented as predictions. Self-citations to the authors' prior ordered/cyclic paper [4] and code base [5] supply the methodological template and some comparison values, but those citations are not load-bearing uniqueness theorems that force the new reflective/dihedral equalities; the equalities are re-proved or newly conjectured from the present computations. No equation reduces a claimed prediction to an input by construction. Score 1 reflects only the minor, non-load-bearing self-citation of tooling.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The work is pure discrete mathematics plus SAT computation. It inherits classical Ramsey existence, standard graph-homomorphism language, and the permutational framework of [4]. No continuous free parameters are fitted. The main external trust points are SAT-solver soundness and the correctness of the clause encoding. Invented entities are the reflective and dihedral specializations already named in prior work; they are definitional, not physical postulates.

assumptions (4)
  • standard math Ramsey’s theorem guarantees that permutational Ramsey numbers are finite for any finite graphs and permutation groups.
    Invoked in §1 to assert well-definedness of R(H^Γ,...).
  • domain assumption Kissat correctly decides satisfiability of the generated CNF instances within the stated time limits when it returns SAT/UNSAT.
    All computational upper/lower bounds in §4 rest on solver answers; no independent formal certificate checker is claimed.
  • domain assumption The Boolean encoding (1)–(2) in §3 is equisatisfiable with the existence of a 2-edge-coloring of K_n avoiding the forbidden Γ-embeddings.
    Standard Poljak-style encoding extended from ordered/cyclic cases; correctness is argued but not machine-checked.
  • standard math Graphs with reflection symmetry have R_ref = R_ord and R_dih = R_cyc (Corollary 2.5).
    Used to restrict the computational grid to cases that do not collapse to prior ordered/cyclic numbers.
invented entities (2)
  • Reflective Ramsey numbers R_ref independent evidence
    purpose: Specialize permutational Ramsey numbers to the order-2 reflection group so that linear order direction is ignored.
    Named and proposed in prior work [4]; this paper computes them. Definitional specialization, not a new physical object.
  • Dihedral Ramsey numbers R_dih independent evidence
    purpose: Specialize permutational Ramsey numbers to the dihedral group (rotations + reflection) so that cyclic order direction is ignored.
    Same as above; computational target of the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computation of small reflective and dihedral Ramsey numbers." pith.science (2026). https://pith.science/paper/7TIP25F4

@misc{pith2026260706817,
  author       = {Pith},
  title        = {Pith review of: Computation of small reflective and dihedral Ramsey numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7TIP25F4}},
  note         = {Machine review of arXiv:2607.06817}
}
abstract

Throughout, all graphs are simple, finite and have vertex sets of the form $\{ 0, 1, 2, \ldots, n - 1 \}$ for some $n \in \mathbb{N}$. For graphs $G$ and $H$, and a permutation group $\Gamma$ on the vertex set of $H$, we say that $H$ is $\Gamma$-embeddable in $G$ if there exists a graph homomorphism from $H$ to $G$ of the form $\psi \circ \varphi$, where $\varphi \in \Gamma$ and $\psi$ is an increasing injection. Recently, standard and ordered Ramsey numbers of graphs were unified through the introduction of permutational Ramsey numbers, defined as follows. For graphs $H_1, H_2, \ldots, H_k$ and permutation groups $\Gamma_1, \Gamma_2, \ldots, \Gamma_k$ on their respective vertex sets, the permutational Ramsey number $R(H_1^{\Gamma_1}, H_2^{\Gamma_2}, \ldots, H_k^{\Gamma_k})$ is the minimum $n \in \mathbb{N}$ such that for every $k$-edge-coloring of a complete graph on $n$ vertices, there exists some $j \in \{1, 2, \ldots, k\}$ for which $H_j$ is $\Gamma_j$-embeddable in the spanning subgraph of the complete graph comprising the edges of color $j$. Here, we consider reflective (resp. dihedral) Ramsey numbers, which are a specific class of permutational Ramsey numbers in which each group $\Gamma_j$ is the reflection group (resp. dihedral group) on the naturally ordered vertex set of $H_j$. Focusing on the two-color case, we apply the SAT-based approach originally proposed by Poljak for ordered Ramsey numbers and recently extended to cyclic Ramsey numbers. We utilize the Kissat SAT solver to obtain exact values and lower bounds for small reflective and dihedral Ramsey numbers whose two arguments belong to the following graph classes: monotone and alternating paths, monotone cycles, start-central stars, complete graphs and nested matchings. We also derive several general results and formulate conjectures based on the computational findings.

Figures

Figures reproduced from arXiv: 2607.06817 by the authors.

Figure 1
Figure 1. The alternating paths of orders five and six. Source: [ [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The nested matchings of orders four and eight. Source: [ [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 2 linked inside Pith

  1. [4]

    Bašić, I

    N. Bašić, I. Damnjanović, D. Stevanović and I. Stošić, Some results on small ordered and cyclic Ramsey numbers, 2026,arXiv:2604.16188 [math.CO]

    arXiv 2026

  2. [1]

    Balko, A survey on ordered Ramsey numbers, 2025,arXiv:2502.02155 [math.CO]

    M. Balko, A survey on ordered Ramsey numbers, 2025,arXiv:2502.02155 [math.CO]

    arXiv 2025

  3. [2]

    Balko, J

    M. Balko, J. Cibulka, K. Král and J. Kynčl, Ramsey numbers of ordered graphs,Electron. Notes Discrete Math.49(2015), 419–424,https://doi.org/10.1016/j.endm.2015.06.059

    doi:10.1016/j.endm.2015.06.059 2015

  4. [3]

    Balko, J

    M. Balko, J. Cibulka, K. Král and J. Kynčl, Ramsey numbers of ordered graphs,Electron. J. Comb.27 (2020), #P1.16,https://doi.org/10.37236/7816

    doi:10.37236/7816 2020

  5. [5]

    Bašić, I

    N. Bašić, I. Damnjanović, D. Stevanović and I. Stošić, Some results on small ordered and cyclic Ramsey numbers (GitHub repository),https://github.com/Ivan-Damnjanovic/ord-ram-num

  6. [6]

    Biere, T

    A. Biere, T. Faller, K. Fazekas, M. Fleury, N. Froleyks and F. Pollitt, CaDiCaL, Gimsatul, IsaSAT and Kissat entering the SAT competition 2024, in: M. J. H. Heule, M. Iser, M. Järvisalo and M. Suda (eds.), Proceedings of SAT Competition 2024: Solver, Benchmark and Proof Checker Descriptions, vol. B-2024-1 of Department of Computer Science Report Series B,...

    2024

  7. [7]

    Biere, T

    A. Biere, T. Faller, K. Fazekas, M. Fleury, N. Froleyks and F. Pollitt, CaDiCaL, Gimsatul, IsaSAT and Kissat entering the SAT competition 2024 (GitHub repository),https://github.com/arminbiere/ kissat

    2024

  8. [8]

    S. A. Burr and J. A. Roberts, On Ramsey numbers for stars,Util. Math.4(1973), 217–220

    1973

Show all 25 references
  1. [9]

    Chvátal, Tree-complete graph Ramsey numbers,J

    V. Chvátal, Tree-complete graph Ramsey numbers,J. Graph Theory1(1977), 93,https://doi.org/10. 1002/jgt.3190010118. 16

    1977

  2. [10]

    Conlon, J

    D. Conlon, J. Fox, C. Lee and B. Sudakov, Ordered Ramsey numbers,J. Comb. Theory Ser. B122(2017), 353–383,https://doi.org/10.1016/j.jctb.2016.06.007

    2017 doi

  3. [11]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, in: A. Czumaj, A. Geor- gakopoulos, D. Kráľ, V. Lozin and O. Pikhurko (eds.),Surveys in Combinatorics 2015, vol. 424 ofLondon Mathematical Society Lecture Note Series, Cambridge University Press, Cam...

    2015 doi

  4. [12]

    Damnjanović and I

    I. Damnjanović and I. Ðorđević, Computation of small reflective and dihedral Ramsey numbers: Supple- mentary material (GitHub repository),https://github.com/IrenaDJ/ref-dih-ram-num

  5. [13]

    Erdős and Gy

    P. Erdős and Gy. Szekeres, A combinatorial problem in geometry,Compos. Math.2(1935), 463–470, http://eudml.org/doc/88611

    1935

  6. [14]

    Frankl, J

    P. Frankl, J. Pach, C. Reiher and V. Rödl, Borsuk and Ramsey type questions in Euclidean space, in: S. Butler, J. Cooper and G. Hurlbert (eds.),Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham, Cambridge University Press, Cambridge, UK, 2018, pp. 25...

    2018 doi

  7. [15]

    R. L. Graham, B. L. Rothschild and J. H. Spencer,Ramsey Theory, 2nd edition, John Wiley & Sons, Inc., New York, NY, 1990

    1990

  8. [16]

    Károlyi, J

    Gy. Károlyi, J. Pach and G. Tóth, Ramsey-type results for geometric graphs, I,Discrete Comput. Geom. 18(1997), 247–255,https://doi.org/10.1007/PL00009317

    1997 doi

  9. [17]

    Li and Q

    Y. Li and Q. Lin,Elementary Methods of Graph Ramsey Theory, vol. 211 ofApplied Mathematical Sciences, Springer, Cham, Switzerland, 2022,https://doi.org/10.1007/978-3-031-12762-5

    2022 doi

  10. [18]

    B. D. McKay, Description of graph6, sparse6 and digraph6 encodings, 2022,https://users.cecs.anu. edu.au/~bdm/data/formats.txt

    2022

  11. [19]

    B. D. McKay and A. Piperno, Practical graph isomorphism, II,J. Symb. Comput.60(2014), 94–112, https://doi.org/10.1016/j.jsc.2013.09.003

    2014 doi

  12. [20]

    Morris, Some recent results in Ramsey theory, 2026,arXiv:2601.05221 [math.CO]

    R. Morris, Some recent results in Ramsey theory, 2026,arXiv:2601.05221 [math.CO]

    2026

  13. [21]

    Nešetřil and V

    J. Nešetřil and V. Rödl (eds.),Mathematics of Ramsey Theory, vol. 5 ofAlgorithms and Combinatorics, Springer, Berlin, Heidelberg, Germany, 1990,https://doi.org/10.1007/978-3-642-72905-8

    1990 doi

  14. [22]

    Nguyen Van Thé, A survey on structural Ramsey theory and topological dynamics with the Kechris– Pestov–Todorcevic correspondence in mind,Zb

    L. Nguyen Van Thé, A survey on structural Ramsey theory and topological dynamics with the Kechris– Pestov–Todorcevic correspondence in mind,Zb. Rad. (Beogr.)17(25)(2015), 189–207

    2015

  15. [23]

    M. Poljak,Computing and estimating ordered Ramsey numbers, Bachelor’s thesis, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic, 2020,http://hdl.handle.net/20.500.11956/ 119412

    2020

  16. [24]

    S. P. Radziszowski, Small Ramsey numbers,Electron. J. Comb.(2026), DS1.18,https://doi.org/10. 37236/21

    2026

  17. [25]

    F. P. Ramsey, On a problem of formal logic,Proc. Lond. Math. Soc. (2)30(1930), 264–286,https: //doi.org/10.1112/plms/s2-30.1.264. 17

    1930 doi

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.