For graphs
Vertex Ramsey properties of randomly perturbed graphs
Given graphs
- NSF-PAR ID:
- 10199267
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 4
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 983-1006
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract G andF , writeif any coloring of the edges of G withcolors yields a monochromatic copy of the graph F . Supposeis obtained from a graph S withs vertices and maximum degreed by subdividing its edgesh times (that is, by replacing the edges ofS by paths of lengthh + 1). We prove that there exists a graphG with no more thanedges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degreed onq vertices with the property that every pair of vertices of degree greater than 2 are distance at leasth + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs. -
more » « less
An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs are
equivalent if there is an isomorphism between them preserving the edge‐ordering. Theedge‐ordered Ramsey number r edge(H ;q ) of an edge‐ordered graphH is the smallestN such that there exists an edge‐ordered graphG onN vertices such that, for everyq ‐coloring of the edges ofG , there is a monochromatic subgraph ofG equivalent toH . Recently, Balko and Vizer proved thatr edge(H ;q ) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constantc such thatfor every edge‐ordered graph H onn vertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering. -
null (Ed.)A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $T$ with $n$~edges, it is conjectured that there exists a labeling $f\colon V(T) \to \{0,1,\ldots,n\}$ such that the set of induced edge labels $\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$ is exactly $\{1,2,\ldots,n\}$. We extend this concept to allow for multigraphs with edge multiplicity at most~$2$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $G$ with $n$~edges is a one-to-one function $f\colon V(G) \to \{0,1,\ldots,n\}$ such that the multiset of induced edge labels is comprised of two copies of each element in $\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$ and, if $n$ is odd, one copy of $\bigl\{ \lceil n/2 \rceil \bigr\}$. When $n$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $n \not\equiv 1 \pmod{4}$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $2$-fold graceful.more » « less
-
more » « less
Abstract Consider the upper tail probability that the homomorphism count of a fixed graph
H within a large sparse random graphG n exceeds its expected value by a fixed factor. Going beyond the Erdős–Rényi model, we establish here explicit, sharp upper tail decay rates for sparse random d n ‐regular graphs (providedH has a regular 2‐core), and for sparse uniform random graphs. We further deal with joint upper tail probabilities for homomorphism counts of multiple graphs(extending the known results for ), and for inhomogeneous graph ensembles (such as the stochastic block model), we bound the upper tail probability by a variational problem analogous to the one that determines its decay rate in the case of sparse Erdős–Rényi graphs. -
more » « less
Abstract We present a refinement of the classical alteration method for constructing ‐free graphs for suitable edge‐probabilities , we show that removing all edges in ‐copies of the binomial random graph does not significantly change the independence number. This differs from earlier alteration approaches of Erdős and Krivelevich, who obtained similar guarantees by removing one edge from each ‐copy (instead of all of them). We demonstrate the usefulness of our refined alternation method via two applications to online graph Ramsey games, where it enables easier analysis.
