Let be the graph obtained from a given graph by subdividing each edge times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph , there exist graphs with edges that are Ramsey with respect to .
Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.
A geometric progression of length k and integer ratio is a set of numbers of the form for some positive real number a and integer r ≥ 2. For each integer k ≥ 3, a greedy algorithm is used to construct a strictly decreasing sequence of positive real numbers with a₁ = 1 such that the set contains no geometric progression of length k and integer ratio. Moreover, is a maximal subset of (0,1] that contains no geometric progression of length k and integer ratio. It is also proved that there is...
If n, t are natural numbers, μ is an infinite cardinal, G is an n-chromatic graph of cardinality at most μ, then there is a graph X with , |X| = μ⁺, such that every subgraph of X of cardinality < t is n-colorable.
It is consistent that there exists a graph X of cardinality such that every graph has an edge coloring with colors in which the induced copies of X (if there are any) are totally multicolored (get all possible colors).
The aim of this paper is to generalize several basic results from transversal theory, primarily the theorem of Edmonds and Fulkerson.
The purpose of this article is to connect the notion of the amenability of a discrete group with a new form of structural Ramsey theory. The Ramsey-theoretic reformulation of amenability constitutes a considerable weakening of the Følner criterion. As a by-product, it will be shown that in any non-amenable group G, there is a subset E of G such that no finitely additive probability measure on G measures all translates of E equally. The analysis of discrete groups will be generalized to the setting...
Moore [Fund. Math. 220 (2013)] characterizes the amenability of the automorphism groups of countable ultrahomogeneous structures by a Ramsey-type property. We extend this result to the automorphism groups of metric Fraïssé structures, which encompass all Polish groups. As an application, we prove that amenability is a condition.