Back to Search
Start Over
The size‐Ramsey number of short subdivisions
- Source :
- Random Structures & Algorithms. 59:68-78
- Publication Year :
- 2021
- Publisher :
- Wiley, 2021.
-
Abstract
- The $r$-size-Ramsey number $\hat{R}_r(H)$ of a graph $H$ is the smallest number of edges a graph $G$ can have, such that for every edge-coloring of $G$ with $r$ colors there exists a monochromatic copy of $H$ in $G$. The notion of size-Ramsey numbers has been introduced by Erdős, Faudree, Rousseau and Schelp in 1978, and has attracted a lot of attention ever since. For a graph $H$, we denote by $H^q$ the graph obtained from $H$ by subdividing its edges with $q{-}1$ vertices each. In a recent paper of Kohayakawa, Retter and R{o}dl, it is shown that for all constant integers $q,r\geq 2$ and every graph $H$ on $n$ vertices and of bounded maximum degree, the $r$-size-Ramsey number of $H^q$ is at most $(\log n)^{20(q-1)}n^{1+1/q}$, for $n$ large enough. We improve upon this result using a significantly shorter argument by showing that $\hat{R}_r(H^q)\leq O(n^{1+1/q})$ for any such graph $H$.
- Subjects :
- Random graph
business.industry
Applied Mathematics
General Mathematics
Ramsey theory
0102 computer and information sciences
Binary logarithm
01 natural sciences
Computer Graphics and Computer-Aided Design
Combinatorics
010201 computation theory & mathematics
Bounded function
Graph (abstract data type)
Ramsey's theorem
business
Constant (mathematics)
Software
Subdivision
Mathematics
Subjects
Details
- ISSN :
- 10982418 and 10429832
- Volume :
- 59
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi...........549d3545f01a5a677c773fca825d778f