Some remarks on Folkman graphs for triangles
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908903703314432 |
|---|---|
| author | Mulrenin, Eion |
| author_facet | Mulrenin, Eion |
| contents | Folkman's theorem asserts the existence of graphs $G$ which are $K_4$-free, but which have the property that every two-coloring of $E(G)$ contains a monochromatic triangle. The quantitative aspects of $f(2,3,4)$, the least $n$ such that there exists an $n$-vertex graph with both properties above, are notoriously difficult; a series of improvements over the span of two decades witnessed the solution to two \$100 Erdős problems, and the current record due to Lange, Radziszowski, and Xu now stands at $f(2,3,4) \leq 786$, the proof of which is computer-assisted.
In this paper, we study Folkman-like properties of a sequence $H_q$ of finite geometric graphs constructed using Hermitian unitals in projective planes, and conjecture that the graph $H_3$, which has 63 vertices, contains a Folkman graph as a proper subgraph. As evidence towards this conjecture, we show that for all prime powers $q \geq 4$, there exists a system $\mathscr{T}_q$ of triangles in $H_q$ such that no four span a $K_4$ in $H_q$, but every two-coloring of $E(H_q)$ induces a monochromatic triangle in $\mathscr{T}_q$, and note that recent adjacent computational work has verified the same property for $H_3$. Moreover, we show that a certain random alteration of $H_q$ which destroys all of its $K_4$'s will, for large $q$, maintain the Ramsey property with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14942 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Some remarks on Folkman graphs for triangles Mulrenin, Eion Combinatorics Folkman's theorem asserts the existence of graphs $G$ which are $K_4$-free, but which have the property that every two-coloring of $E(G)$ contains a monochromatic triangle. The quantitative aspects of $f(2,3,4)$, the least $n$ such that there exists an $n$-vertex graph with both properties above, are notoriously difficult; a series of improvements over the span of two decades witnessed the solution to two \$100 Erdős problems, and the current record due to Lange, Radziszowski, and Xu now stands at $f(2,3,4) \leq 786$, the proof of which is computer-assisted. In this paper, we study Folkman-like properties of a sequence $H_q$ of finite geometric graphs constructed using Hermitian unitals in projective planes, and conjecture that the graph $H_3$, which has 63 vertices, contains a Folkman graph as a proper subgraph. As evidence towards this conjecture, we show that for all prime powers $q \geq 4$, there exists a system $\mathscr{T}_q$ of triangles in $H_q$ such that no four span a $K_4$ in $H_q$, but every two-coloring of $E(H_q)$ induces a monochromatic triangle in $\mathscr{T}_q$, and note that recent adjacent computational work has verified the same property for $H_3$. Moreover, we show that a certain random alteration of $H_q$ which destroys all of its $K_4$'s will, for large $q$, maintain the Ramsey property with high probability. |
| title | Some remarks on Folkman graphs for triangles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.14942 |