pith. sign in

arxiv: 2604.10229 · v2 · submitted 2026-04-11 · 🧮 math.CO

ErdH{o}s-Gy\'{a}rf\'{a}s problem for partially ordered sets

Gyula O. H. Katona , Yaping Mao This is my paper

Pith reviewed 2026-05-14 21:35 UTC · model grok-4.3

classification 🧮 math.CO
keywords Boolean latticestrong coloringErdős-Gyárfás functionRamsey numberposet embeddingt-chainsLovász local lemma
0
0 comments X

The pith

Every finite poset strongly embeds into a Boolean lattice, proving strong Boolean Ramsey numbers exist for any such poset.

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

The paper defines a strong (p,q,t)-coloring of the Boolean lattice B_n in which the t-chains receive colors so that every induced copy of B_p uses at least q distinct colors on its t-chains, and studies the minimum number f_t^#(n,p,q) of colors needed. It first proves that every finite poset admits a strong embedding into some Boolean lattice. This embedding, when combined with a structural Ramsey theorem for posets equipped with linear extensions, immediately yields the existence of the strong Boolean Ramsey number R^#_k,t(B|Q) for every k at least 1, every t at least 1, and every nonempty finite poset Q. As a direct consequence the function f_t^#(n,p,2) is shown to be well-defined and finite. The paper supplies a probabilistic upper bound via the symmetric Lovász local lemma and combinatorial lower bounds obtained from Turán-type counts on t-chains together with a generalized Lubell framework.

Core claim

Every finite poset strongly embeds into a Boolean lattice. Together with the structural Ramsey theorem for finite posets with linear extensions, this establishes the existence of the strong Boolean Ramsey number R^#_k,t(B|Q) for every integer k≥1, every t≥1, and every nonempty finite poset Q; in particular it settles the existence of f_t^#(n,p,2).

What carries the argument

Strong embedding of an arbitrary finite poset into a Boolean lattice, which preserves the incidence structure of t-chains so that Ramsey-type guarantees on the poset transfer to colorings of the Boolean lattice.

If this is right

  • The strong Boolean Ramsey number R^#_k,t(B|Q) is finite for every k≥1, t≥1 and every nonempty finite poset Q.
  • The minimum color count f_t^#(n,p,2) exists and is finite for all n, p and t.
  • Symmetric Lovász local lemma supplies explicit upper bounds on f_t^#(n,p,q) for general q.
  • Lower bounds on f_t^#(n,p,q) follow from extremal counts of t-chains and double-counting arguments inside the Boolean lattice.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The embedding technique may extend to other graded lattices or to infinite posets under suitable compactness assumptions.
  • Explicit constructions of the embeddings could yield algorithmic methods for producing the colorings whose existence is guaranteed.
  • The same embedding-plus-Ramsey route might apply to other extremal problems on chains in graded posets beyond the Boolean case.

Load-bearing premise

The structural Ramsey theorem for finite posets with linear extensions must hold so that the embedding produces the desired Ramsey numbers.

What would settle it

Exhibit one finite poset that admits no strong embedding into any Boolean lattice, or produce concrete k, t, and Q for which no finite strong Boolean Ramsey number R^#_k,t(B|Q) exists.

read the original abstract

Given integers $p,q,t$ with $1 \le t \le p$ and $1 \le q \le h_p(t)$, a strong $(p,q,t)$-coloring of the Boolean lattice $B_n$ is a coloring of its $t$-chains such that every induced copy of $B_p$ in $B_n$ uses at least $q$ colors on its $t$-chains. Let $f_t^{\sharp}(n,p,q)$ denote the minimum number of colors in such a coloring. We study this Boolean-lattice analogue of the Erd\H{o}s-Gy\'{a}rf\'{a}s function.We first show that every finite poset strongly embeds into a Boolean lattice. Combined with a structural Ramsey theorem for finite posets with linear extensions, this implies the existence of the strong Boolean Ramsey number $\mathrm{R}^{\sharp}_{k,t}(\mathcal{B}\mid Q)$ for every integer $k\ge1$, every $t\ge1$, and every nonempty finite poset $Q$. In particular, this gives an affirmative answer to a problem of Cox and Stolee and yields the existence of $f_t^{\sharp}(n,p,2)$. Next, using the symmetric Lov\'asz local lemma, we obtain a probabilistic upper bound on $f_t^{\sharp}(n,p,q)$. Finally, we prove lower bounds by combining Tur\'an-type extremal estimates for $t$-chains, a double-counting argument, and a generalized Lubell-type framework for $t$-chains.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines a strong (p,q,t)-coloring of the Boolean lattice B_n as a coloring of its t-chains such that every induced B_p uses at least q colors on its t-chains, and studies the minimum number f_t^#(n,p,q) of colors needed. It proves that every finite poset strongly embeds into some Boolean lattice; combined with a structural Ramsey theorem for posets equipped with linear extensions, this yields the existence of the strong Boolean Ramsey number R^#_k,t(B|Q) for all k≥1, t≥1 and nonempty finite Q, in particular answering a question of Cox and Stolee by establishing existence of f_t^#(n,p,2). Probabilistic upper bounds on f_t^#(n,p,q) are obtained via the symmetric Lovász local lemma, while lower bounds follow from Turán-type estimates on t-chains, double counting, and a generalized Lubell framework.

Significance. If the embedding result is shown to be compatible with the linear-extension hypotheses of the invoked structural Ramsey theorem, the existence statements resolve an open question of Cox and Stolee and supply the first general existence proof for these strong Boolean Ramsey numbers. The probabilistic upper bound and the extremal lower-bound machinery are obtained with standard tools of the field and are likely to be of independent interest for quantitative versions of the problem.

major comments (2)
  1. [proof of the strong-embedding theorem (likely §2)] The central existence claim (abstract, final paragraph) rests on the assertion that every finite poset Q strongly embeds into a Boolean lattice B_n and that the image can be equipped with linear extensions so that the structural Ramsey theorem applies directly. The manuscript must supply an explicit definition of 'strongly embeds' together with a verification that the embedding maps (or induces) linear extensions of Q to linear extensions of B_n; without this compatibility argument the implication to R^#_k,t(B|Q) does not follow.
  2. [lower-bound section] § on lower bounds: the generalized Lubell-type framework for t-chains is invoked to obtain the lower bound on f_t^#(n,p,q). The precise statement of the framework (including the weight function on t-chains) should be stated as a self-contained lemma before it is applied, so that the double-counting step can be checked independently of the Turán estimates.
minor comments (2)
  1. [introduction] Notation: the symbol R^#_k,t(B|Q) is introduced without an explicit definition in the abstract; a one-sentence definition should appear at first use in the introduction.
  2. [probabilistic upper bound] The probabilistic upper bound obtained via the Lovász local lemma is stated only asymptotically; an explicit dependence on p,q,t would make the result more usable for small parameters.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive suggestions, which will improve the clarity and self-contained nature of the manuscript. We address each major comment below and will incorporate the requested changes in the revised version.

read point-by-point responses

  1. Referee: [proof of the strong-embedding theorem (likely §2)] The central existence claim (abstract, final paragraph) rests on the assertion that every finite poset Q strongly embeds into a Boolean lattice B_n and that the image can be equipped with linear extensions so that the structural Ramsey theorem applies directly. The manuscript must supply an explicit definition of 'strongly embeds' together with a verification that the embedding maps (or induces) linear extensions of Q to linear extensions of B_n; without this compatibility argument the implication to R^#_k,t(B|Q) does not follow.

    Authors: We agree that an explicit definition of strong embedding and a direct verification of compatibility with linear extensions are needed to make the implication to the structural Ramsey theorem fully transparent. In the revised manuscript we will insert a precise definition of 'strongly embeds' at the beginning of Section 2 and add a short lemma confirming that the embedding induces linear extensions of the image poset that satisfy the hypotheses of the invoked structural Ramsey theorem. revision: yes

  2. Referee: [lower-bound section] § on lower bounds: the generalized Lubell-type framework for t-chains is invoked to obtain the lower bound on f_t^#(n,p,q). The precise statement of the framework (including the weight function on t-chains) should be stated as a self-contained lemma before it is applied, so that the double-counting step can be checked independently of the Turán estimates.

    Authors: We accept this recommendation. In the revised version we will state the generalized Lubell-type framework for t-chains (including the explicit weight function) as a self-contained lemma immediately preceding its application in the lower-bounds section. This will separate the framework from the subsequent Turán estimates and double-counting argument, allowing each step to be verified independently. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper proves a new result that every finite poset strongly embeds into a Boolean lattice, then invokes an external structural Ramsey theorem for finite posets with linear extensions to conclude existence of R^#_k,t(B|Q) and f_t^#(n,p,2). No step reduces by definition or construction to its own inputs, no fitted parameters are relabeled as predictions, and the load-bearing citations are to independent prior work rather than a self-citation chain that collapses the argument. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The existence results rest on two key inputs: a newly established embedding of arbitrary finite posets into Boolean lattices and a pre-existing structural Ramsey theorem for posets with linear extensions. No free parameters or invented entities appear in the abstract.

axioms (2)
  • domain assumption Every finite poset strongly embeds into a Boolean lattice
    Stated as the first result used to reach the Ramsey-number existence.
  • standard math A structural Ramsey theorem holds for finite posets equipped with linear extensions
    Invoked directly to obtain R^#_k,t(B|Q) from the embedding.

pith-pipeline@v0.9.0 · 5590 in / 1543 out tokens · 61174 ms · 2026-05-14T21:35:18.527808+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    Arman and V

    A. Arman and V. R¨ odl, Note on a Ramsey theorem for posets with linear extensions,Electron. J. Combin.24(4) (2017), P4.36

    work page 2017

  2. [2]

    Axenovich and C

    M. Axenovich and C. Winter, Poset Ramsey numbers: large Boolean lattice versus a fixed poset, Combin. Probab. Comput.32(4) (2023), 638–653

    work page 2023

  3. [3]

    Axenovich and S

    M. Axenovich and S. Walzer, Boolean lattices: Ramsey properties and embeddings,Order34 (2017), 287–298

    work page 2017

  4. [4]

    Balko, V

    M. Balko, V. Jel´ ınek, and P. Valtr, On ordered Ramsey numbers of bounded-degree graphs,J. Combin. Theory, Ser. B134 (2019), 179–202

    work page 2019

  5. [5]

    Balogh, S

    J. Balogh, S. English, E. Heath, and R. A. Krueger, Lower bounds on the Erd˝ os-Gy´ arf´ as problem via color energy graphs,J. Graph Theory103(2) (2023), 378–409

    work page 2023

  6. [6]

    Bohman and F

    T. Bohman and F. Peng, A construction for Boolean cube Ramsey numbers,Order40 (2023), 327–333

    work page 2023

  7. [7]

    Cameron and E

    A. Cameron and E. Heath, New upper bounds for the Erd˝ os-Gy´ arf´ as problem on generalized Ramsey numbers,Combin. Probab. Comput.32 (2023), 349–362

    work page 2023

  8. [8]

    Chang, D

    F.-H. Chang, D. Gerbner, W.-T. Li, A. Methuku, D. Nagy, B. Patk´ os, and M. Vizer, Rainbow Ramsey problems for the Boolean lattice,Order39 (2022), 453–463. 19

    work page 2022

  9. [9]

    Chen, Y.-J

    H.-B. Chen, Y.-J. Cheng, W.-T. Li, and C.-A. Liu, The Boolean rainbow Ramsey number of antichains, Boolean posets, and chains,Electronic J. Combin.27(4) (2020), #P4

    work page 2020

  10. [10]

    Conlon, J

    D. Conlon, J. Fox, C. Lee, B. Sudakov, Ordered Ramsey numbers,J. Combin. Theory, Ser. B 122 (2017), 353–383

    work page 2017

  11. [11]

    Conlon, J

    D. Conlon, J. Fox, C. Lee, and B. Sudakov, The Erd˝ os-Gy´ arf´ as problem on generalized Ramsey numbers,Proc. Lond. Math. Soc.110(1) (2015), 1–18

    work page 2015

  12. [12]

    Cox and D

    C. Cox and D. Stolee, Ramsey numbers for partially-ordered sets,Order35 (2018), 557–579

    work page 2018

  13. [13]

    Duffus, H

    D. Duffus, H. A. Kierstead, and W. T. Trotter, Fibres and ordered set coloring,J. Combin. Theory, Ser. A58(1) (1991), 158–164

    work page 1991

  14. [14]

    Eichhorn and D

    D. Eichhorn and D. Mubayi, The Erd˝ os-Gy´ arf´ as problem for complete graphs,J. Combin. Theory, Ser. B78(2) (2000), 243–254

    work page 2000

  15. [15]

    Erd˝ os, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc

    P. Erd˝ os, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 1975, pp. 183–192

    work page 1974

  16. [16]

    Erd˝ os, Solved and unsolved problems in combinatorics and combinatorial number theory, Eur

    P. Erd˝ os, Solved and unsolved problems in combinatorics and combinatorial number theory, Eur. J. Combin.2 (1981), 1–11

    work page 1981

  17. [17]

    Erd˝ os and A

    P. Erd˝ os and A. Gy´ arf´ as, Ramsey-type theorems for graphs,Discrete Math.165/166 (1997), 347–358

    work page 1997

  18. [18]

    Gerbner and B

    D. Gerbner and B. Patk´ os,Extremal Finite Set Theory, CRC Press, Taylor & Francis Group, Boca Raton, 2019

    work page 2019

  19. [19]

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

    work page 1990

  20. [20]

    J. R. Griggs, S. Stahl, and W. T. Trotter Jr., A Sperner theorem on unrelated chains of subsets, J. Combin. Theory, Ser. A36 (1984), 124–127

    work page 1984

  21. [21]

    J. R. Griggs and W.-T. Li, Progress on poset-free families of subsets, The IMA Volumes in Mathematics and its Applications, 159 (2015), 317–338

    work page 2015

  22. [22]

    Gr´ osz, A

    D. Gr´ osz, A. Methuku, and C. Tompkins, Ramsey numbers of Boolean lattices,Bull. Lond. Math. Soc.55(3) (2023), 1073–1086

    work page 2023

  23. [23]

    R. Gu, G. O. H. Katona, and Y. Mao, Ramsey properties of random posets, submitted. 20

    work page

  24. [24]

    D. S. Gunderson, V. R¨ odl, and A. Sidorenko, Extremal problems for sets forming boolean algebras and complete partite hypergraphs,J. Combin. Theory, Ser. A88(2) (1999), 342–367

    work page 1999

  25. [25]

    Johnston, L

    T. Johnston, L. Lu, and K. G. Milans, Boolean algebras and Lubell functions,J. Combin. Theory, Ser. A136 (2015), 174–183

    work page 2015

  26. [26]

    G. O.H. Katona, Y. Mao, K. Ozeki, Z. Wang, Ramsey numbers for ordered partially sets, arXiv:2512.14638 [math.CO], 2025

    work page arXiv 2025

  27. [27]

    G. O. H. Katona and T. G. Tarj´ an, Extremal problems with excluded subgraphs in then-cube, in: Graph Theory, Springer, Berlin, 1983, pp. 84–93

    work page 1983

  28. [28]

    H. A. Kierstead and W. T. Trotter, A Ramsey theoretic problem for finite ordered sets,Discrete Math.63(2) (1987), 217–223

    work page 1987

  29. [29]

    Kleitman and G

    D. Kleitman and G. Markowsky, On Dedekind’s problem: the number of isotone Boolean func- tions,Trans. Amer. Math. Soc.213 (1975), 373–390

    work page 1975

  30. [30]

    Lu and J

    L. Lu and J. C. Thompson, Poset Ramsey numbers for Boolean lattices,Order39 (2022), 171–185

    work page 2022

  31. [31]

    G. L. McColm, A Ramseyian theorem on products of trees,J. Combin. Theory, Ser. A57(1) (1991), 68–75

    work page 1991

  32. [32]

    Mubayi, A note on the Erd˝ os-Gy´ arf´ as problem,J

    D. Mubayi, A note on the Erd˝ os-Gy´ arf´ as problem,J. Combin. Theory, Ser. B73(2) (1998), 221–226

    work page 1998

  33. [33]

    Neˇ setˇ ril and V

    J. Neˇ setˇ ril and V. R¨ odl, Combinatorial partitions of finite posets and lattices–Ramsey lattices, Algebra Universalis19 (1984), 106–119

    work page 1984

  34. [34]

    Patk´ os, On colorings of the Boolean lattice avoiding a rainbow copy of a poset,Discrete Appl

    B. Patk´ os, On colorings of the Boolean lattice avoiding a rainbow copy of a poset,Discrete Appl. Math.276 (2020), 108–114

    work page 2020

  35. [35]

    F. P. Ramsey, On a problem of formal logic,Proc. Lond. Math. Soc.30 (1930), 264–286

    work page 1930

  36. [36]

    Rosta, Ramsey theory applications,Electron

    V. Rosta, Ramsey theory applications,Electron. J. Combin.11(1) (2004), #A8

    work page 2004

  37. [37]

    Spencer, Asymptotic lower bounds for Ramsey functions,Discrete Math.20 (1977), 69–76

    J. Spencer, Asymptotic lower bounds for Ramsey functions,Discrete Math.20 (1977), 69–76

    work page 1977

  38. [38]

    W. T. Trotter, Ramsey theory and partially ordered sets, in: Contemporary Trends in Dis- crete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 49, Amer. Math. Soc., Providence, 1999, pp. 337–347. 21

    work page 1999

  39. [39]

    Walzer,Ramsey variant of the2-dimension of posets, Master’s Thesis, Karlsruhe Institute of Technology, 2015

    S. Walzer,Ramsey variant of the2-dimension of posets, Master’s Thesis, Karlsruhe Institute of Technology, 2015

    work page 2015

  40. [40]

    Winter, Erd˝ os-Hajnal problems for posets,Order42 (2025), 509–527

    C. Winter, Erd˝ os-Hajnal problems for posets,Order42 (2025), 509–527

    work page 2025

  41. [41]

    Winter, Poset Ramsey numberR(P, Q n)

    C. Winter, Poset Ramsey numberR(P, Q n). I. Complete multipartite posets,Order41 (2024), 391–399

    work page 2024

  42. [42]

    Winter, Poset Ramsey numberR(P, Q n)

    C. Winter, Poset Ramsey numberR(P, Q n). II.N-shaped poset,Order41 (2024), 401–418

    work page 2024

  43. [43]

    Winter, Poset Ramsey numberR(P, Q n)

    C. Winter, Poset Ramsey numberR(P, Q n). III. Chain compositions and antichains,Discrete Math.347(7) (2024), 114031

    work page 2024

  44. [44]

    Yip, A variant of the Erd˝ os-Gy´ arf´ as problem forK8,Eur

    F. Yip, A variant of the Erd˝ os-Gy´ arf´ as problem forK8,Eur. J. Combin.112 (2026), 104267. 22

    work page 2026