Search

The induced size-Ramsey number r ^ ind k (H) of a graph H is the smallest number of edges a (host) graph G can have such that for any k-coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., r ^ ind k (C n) ≤ C n for some C = C (k) . The constant C comes from the use of the regularity lemma, and has a tower type dependence on k. In this paper we significantly improve these bounds, showing that r ^ ind k (C n) ≤ O (k 102) n when n is even, thus obtaining only a polynomial dependence of C on k. We also prove r ^ ind k (C n) ≤ e O (k log k) n for odd n, which almost matches the lower bound of e Ω (k) n . Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies r ^ k (C n) = e O (k) n for odd n. This substantially improves the best previous result of e O (k 2) n , and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity. [ABSTRACT FROM AUTHOR]

A mathematical procedure enabling the transformation of an arbitrary tessellation of a surface into a bi-colored, complete graph is introduced. Polygons constituting the tessellation are represented by vertices of the graphs. Vertices of the graphs are connected by two kinds of links/edges, namely, by a green link, when polygons have the same number of sides, and by a red link, when the polygons have a different number of sides. This procedure gives rise to a semi-transitive, complete, bi-colored Ramsey graph. The Ramsey semi-transitive number was established as R t r a n s (3 , 3) = 5 Shannon entropies of the tessellation and graphs are introduced. Ramsey graphs emerging from random Voronoi and Poisson Line tessellations were investigated. The limits ζ = lim N → ∞ N g N r , where N is the total number of green and red seeds, N g and N r , were found ζ = 0.272 ± 0.001 (Voronoi) and ζ = 0.47 ± 0.02 (Poisson Line). The Shannon Entropy for the random Voronoi tessellation was calculated as S = 1.690 ± 0.001 and for the Poisson line tessellation as S = 1.265 ± 0.015. The main contribution of the paper is the calculation of the Shannon entropy of the random point process and the establishment of the new bi-colored Ramsey graph on top of the tessellations. [ABSTRACT FROM AUTHOR]

In this paper we prove several results on Ramsey numbers R(H,F) for a fixed graph H and a large graph F, in particular for F = Kn. These results extend earlier work of Erd\H os, Faudree, Rousseau, and Schelp and of Balister, Schelp, and Simonovits on so-called Ramsey sizelinear graphs. Among other results, we show that if H is a subdivision of K4 with at least six vertices, then R(H,F) =O(v(F)+e(F)) for every graph F. We also conjecture that if H is a connected graph with e(H) v(H) (k+1/2)2, then R(H,Kn) = O(nk). The case k = 2 was proved by Erd\H os, Faudree, Rousseau, and Schelp. We prove the case k = 3. [ABSTRACT FROM AUTHOR]

A graph F is Ramsey for a pair of graphs (G,H) if any red/blue-coloring of the edges of F yields a copy of G with all edges colored red or a copy of H with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case G = H, received considerable attention. This led to the open question whether there are connected graphs G and G\prime such that (G,G) and (G' ,G') are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T,Kt), where T is a tree and Kt is a complete graph. We show that if T belongs to a certain family of trees, including all nontrivial stars, then (T,Kt) is Ramsey equivalent to a family of pairs of the form (T,H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T,H) to be Ramsey equivalent to (T,Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T,Kt) is not equivalent to any such pair, not even to the pair (T,Kt K2), where Kt K2 is a complete graph Kt with a single edge attached. [ABSTRACT FROM AUTHOR]

A graph G is q-Ramsey for a q -tuple of graphs (H 1 , ... , H q) if for every q -coloring of the edges of G there exists a monochromatic copy of H i in color i for some i ∈ [ q ]. Over the last few decades, researchers have investigated a number of questions related to this notion, aiming to understand the properties of graphs that are q -Ramsey for a fixed tuple. Among the tools developed while studying questions of this type are gadget graphs, called signal senders and determiners, which have proven invaluable for building Ramsey graphs with certain properties. However, until now these gadgets have been shown to exist and used mainly in the two-color setting or in the symmetric multicolor setting, and our knowledge about their existence for multicolor asymmetric tuples is extremely limited. In this paper, we construct such gadgets for any tuple of cliques. We then use these gadgets to generalize three classical theorems in this area to the asymmetric multicolor setting. [ABSTRACT FROM AUTHOR]

AbstractIn 1994, Bergelson and Hindman established a remarkable result for IP* sets: for any IP* set A and any sequence l in ℕ, there exists a sum subsystem l′ of l such that all finite sums and finite products of l′ are contained in A. There are many studies about this result, where Hindman and Strauss extended it to general weak rings. In this paper, we introduce two algebraic structures - adequate partial weak rings and adequate poor rings, which are more general than weak rings. And we establish that result in both structures. Moreover, we also obtain Hindman theorem with two operations in these two structures. [ABSTRACT FROM AUTHOR]

Let G, H be two non-empty graphs and k be a positive integer. The Gallai-Ramsey number gr k (G : H) is defined as the minimum positive integer N such that for all n ≥ N , every k-edge-coloring of K n contains either a rainbow subgraph G or a monochromatic subgraph H. The Gallai-Ramsey multiplicity GM k (G : H) is defined as the minimum total number of rainbow subgraphs G and monochromatic subgraphs H for all k-edge-colored K gr k (G : H) . In this paper, we get some exact values of the Gallai-Ramsey multiplicity for rainbow small trees versus general monochromatic graphs under a sufficiently large number of colors. We also study the bipartite Gallai-Ramsey multiplicity. [ABSTRACT FROM AUTHOR]

Let n , k and t be non-negative integers. The generalized Johnson graph G (n , k , t) is the graph whose vertices are the k -subsets of the set { 1 , 2 , ... , n } , and two vertices are adjacent if and only if they intersect with t elements. Special cases of generalized Johnson graph include the Kneser graph G (n , k , 0) and the Johnson graph G (n , k , k − 1). These graphs play an important role in coding theory, Ramsey theory, combinatorial geometry and hypergraphs theory. In this paper, we discuss the connectivity properties of the Kneser graph G (n , k , 0) and G (n , k , 1) by their symmetric properties. Specifically, with the help of some properties of vertex/edge-transitive graphs we prove that G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) and G (n , k , 1) (4 ≤ 2 k ≤ n) are super restricted edge-connected. Besides, we obtain the exact value of the restricted edge-connectivity and the cyclic edge-connectivity of the Kneser graph G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) and G (n , k , 1) (4 ≤ 2 k ≤ n) , and further show that the Kneser graph G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) is super vertex-connected and super cyclically edge-connected. [ABSTRACT FROM AUTHOR]

We prove that any strongly mixing action of a countable abelian group on a probability space has higher-order mixing properties. This is achieved via the utilization of $\mathcal R$ -limits, a notion of convergence which is based on the classical Ramsey theorem. $\mathcal R$ -limits are intrinsically connected with a new combinatorial notion of largeness which is similar to but has stronger properties than the classical notions of uniform density one and IP $^*$. While the main goal of this paper is to establish a universal property of strongly mixing actions of countable abelian groups, our results, when applied to ${\mathbb {Z}}$ -actions, offer a new way of dealing with strongly mixing transformations. In particular, we obtain several new characterizations of strong mixing for ${\mathbb {Z}}$ -actions, including a result which can be viewed as the analogue of the weak mixing of all orders property established by Furstenberg in the course of his proof of Szemerédi's theorem. We also demonstrate the versatility of $\mathcal R$ -limits by obtaining new characterizations of higher-order weak and mild mixing for actions of countable abelian groups. [ABSTRACT FROM AUTHOR]

In [2], Bergelson, Furstenberg, and McCutcheon established the following far reaching extension of Khintchine's recurrence theorem:For any invertible probability preserving system $ (X,\mathcal{A},\mu,T) $, any non- constant polynomial $ p\in \mathbb{Z}[x] $ with $ p(0) = 0 $, any $ A\in\mathcal{A} $, and any $ \epsilon>0 $, the set $ R_\epsilon^p(A) = \{n\in \mathbb{N}\,|\,\mu(A\cap T^{-p(n)}A)>\mu^2(A)-\epsilon\} $ is $ {\rm{IP}}^* $, meaning that for any increasing sequence $ (n_k)_{k\in \mathbb{N}} $ in $ \mathbb{N} $, $ \text{FS}((n_k)_{k\in \mathbb{N}})\cap R_\epsilon^p(A)\neq \emptyset, $ where$ \begin{array}{l} \text{FS}((n_k)_{k\in \mathbb{N}}) = \{\sum\limits_{j\in F}n_j\,|\,F\subseteq \mathbb{N}\,\text{ is finite}\text{ and }F\neq\emptyset\}\\ \qquad \qquad \qquad \qquad \qquad = \{n_{k_1}+\cdots+n_{k_t}\,|\,k_1<\cdots1 $ and $ p(0) = 0 $ there is an invertible probability preserving system $ (X,\mathcal{A},\mu,T) $, a set $ A\in\mathcal{A} $, and an $ \epsilon>0 $ for which the set $ R_\epsilon^p(A) $ is not $ {\rm{IP}}_0^* $. [ABSTRACT FROM AUTHOR]

Motivated by bipartite Gallai–Ramsey type problems, we consider edge-colorings of complete bipartite graphs without rainbow tree and matching. Given two graphs G and H , and a positive integer k , define the bipartite Gallai–Ramsey number bgr k (G : H) as the minimum number of vertices n such that n 2 ≥ k and for every N ≥ n , any coloring (using all k colors) of the complete bipartite graph K N , N contains a rainbow copy of G or a monochromatic copy of H. In this paper, we first describe the structures of a complete bipartite graph K n , n without rainbow P 4 + and 3 K 2 , respectively, where P 4 + is the graph consisting of a P 4 with one extra edge incident with an interior vertex. Furthermore, we determine the exact values or upper and lower bounds on bgr k (G : H) when G is a 3-matching or a 4-path or P 4 + , and H is a bipartite graph. [ABSTRACT FROM AUTHOR]

A new area of graph theory emerged in the last few decades is the calculation of star critical Ramsey numbers related to different classes of graphs. Formally, we will say that Kn → (G, 77) if given any coloring of κn there is a copy of G in the first color, red, or a copy of H in the second color, blue. The Ramsey number r(G, H) is defined as the smallest positive integer n such that Kn → (G, 77). AcloselyrelatedconceptofRamseynumberisthestar-CriticalRamseynumber r*(G,77) defined as the largest value of k such that Tfr(G1H)-I u κι,k → (G, 77). A two-coloring of Kr(G,ιt)-ι such that Kr(G,jr)-ι A (G, H) is called a Ramsey critical coloring. A Ramsey critical r (G, 77) graph is a graph induced by the first color of a Ramsey critical coloring. Lower bounds for star critical Ramsey numbers are usually found with the aid on Ramsey critical graphs. The particular problem we handle in this paper, on star critical Ramsey numbers, is based on a conjecture posed in 1973 by Bondy and Erdos relating to Ramsey numbers for large cycles versus complete graphs. Based on certain lemmas we present with proof, Iiirthermore we show that there exist exactly sixty eight non-isomorphic Ramsey critical r(Cn, Tf6) graphs, when n > 15. [ABSTRACT FROM AUTHOR]

This paper deals with the minimum number m H (r) of edges in an H-free hypergraph with the chromatic number more than r. We show how bounds on Ramsey and Turán numbers imply bounds on m H (r) . [ABSTRACT FROM AUTHOR]

The following Ramsey-type question is one of the central problems in combinatorial geometry. Given a collection of certain geometric objects in the plane (e.g. segments, rectangles, convex sets, arcwise connected sets) of size n, what is the size of the largest subcollection in which either any two elements have a nonempty intersection, or any two elements are disjoint? We prove that there exists an absolute constant c>0 such that if C is a collection of n curves in the plane, then C contains at least nc elements that are pairwise intersecting, or n c elements that are pairwise disjoint. This resolves a problem raised by Alon, Pach, Pinchasi, Radoičić and Sharir, and Fox and Pach. Furthermore, as any geometric object can be arbitrarily closely approximated by a curve, this shows that the answer to the aforementioned question is at least nc for any collection of n geometric objects. [ABSTRACT FROM AUTHOR]

Let f r (k) be the smallest positive integer n such that every r -coloring of { 1 , 2 , ... , n } has a monochromatic solution to the nonlinear equation 1 / x 1 + ⋯ + 1 / x k = 1 / y , where x 1 , ... , x k are not necessarily distinct. Brown and Rödl [3] proved that f 2 (k) = O (k 6). In this paper, we prove that f 2 (k) = O (k 3). The main ingredient in our proof is a finite set A ⊆ N such that every 2-coloring of A has a monochromatic solution to the linear equation x 1 + ⋯ + x k = y and the least common multiple of A is sufficiently small. This approach can also be used to study f r (k) with r > 2. For example, a recent result of Boza et al. [2] implies that f 3 (k) = O (k 43). [ABSTRACT FROM AUTHOR]

We applied the Ramsey analysis to the sets of points belonging to Riemannian manifolds. The points are connected with two kinds of lines: geodesic and non-geodesic. This interconnection between the points is mapped into the bi-colored, complete Ramsey graph. The selected points correspond to the vertices of the graph, which are connected with the bi-colored links. The complete bi-colored graph containing six vertices inevitably contains at least one mono-colored triangle; hence, a mono-colored triangle, built of the green or red links, i.e., non-geodesic or geodesic lines, consequently appears in the graph. We also considered the bi-colored, complete Ramsey graphs emerging from the intersection of two Riemannian manifolds. Two Riemannian manifolds, namely (M 1 , g 1) and (M 2 , g 2) , represented by the Riemann surfaces which intersect along the curve (M 1 , g 1) ∩ (M 2 , g 2) = ℒ were addressed. Curve ℒ does not contain geodesic lines in either of the manifolds   (M 1 , g 1) and (M 2 , g 2) . Consider six points located on the ℒ :   { 1 , ... 6 } ⊂ ℒ . The points { 1 , ... 6 } ⊂ ℒ are connected with two distinguishable kinds of the geodesic lines, namely with the geodesic lines belonging to the Riemannian manifold (M 1 , g 1) /red links, and, alternatively, with the geodesic lines belonging to the manifold (M 2 , g 2) /green links. Points { 1 , ... 6 } ⊂ ℒ form the vertices of the complete graph, connected with two kinds of links. The emerging graph contains at least one closed geodesic line. The extension of the theorem to the Riemann surfaces of various Euler characteristics is presented. [ABSTRACT FROM AUTHOR]

Based on the literature on pollution tax on capital and labor, we have analyzed the impact of an optimal fiscal policy (tax) on the Iran economy based on the Ramsey solution. To achieve this, we created a dynamic economic-climatic model for the Iranian economy by adding externalities to a simple general equilibrium model without a foreign sector. Thus first we developed a dynamic model in two cases with and without side effects. Findings indicate that in the conditions of no pollution of the production sector, the model reaches equilibrium with zero capital tax. When we take into account the pollution in the model, in order to have a unique optimal point and keep the economy on the saddle path and it converged towards an optimal point, so capital-based pollution tax became essential. In our model, endogenous labor plays an important role as it indicates an increase in household environmental awareness, the supply of working hours, consumption, production, and environmental quality. In the models with exogenous labor, low household awareness of environmental quality leads to more severe degradation of environmental quality. According to our results considering the Ramsey solution on the economy, in a situation where: labor is endogenous, capital-based pollution tax is implemented, with a dynamic general economic-climatic equilibrium model, two environmental parameters are vital to be taken care of, “the weight of environmental quality” and “the polluting technology”. In an environment where we use increasingly polluting technology, in the absence of an increasing pollution tax regime, the quality of the environment and society’s welfare will diminish subsequently [ABSTRACT FROM AUTHOR]

We prove that any proof of a ∀ Σ 2 0 sentence in the theory WKL 0 + RT 2 2 can be translated into a proof in RCA 0 at the cost of a polynomial increase in size. In fact, the proof in RCA 0 can be obtained by a polynomial-time algorithm. On the other hand, RT 2 2 has nonelementary speedup over the weaker base theory RCA 0 * for proofs of Σ 1 sentences. We also show that for n ≥ 0 , proofs of Π n + 2 sentences in B Σ n + 1 + exp can be translated into proofs in I Σ n + exp at a polynomial cost in size. Moreover, the Π n + 2 -conservativity of B Σ n + 1 + exp over I Σ n + exp can be proved in PV , a fragment of bounded arithmetic corresponding to polynomial-time computation. For n ≥ 1 , this answers a question of Clote, Hájek and Paris. [ABSTRACT FROM AUTHOR]

For A ⊆ ω , the coarse similarity class of A, denoted by [ A ] , is the set of all B ⊆ ω such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric δ on the space of coarse similarity classes defined by letting δ ([ A ] , [ B ]) be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form { [ A ] : A ∈ } where is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of . We then define a distance between Turing degrees based on Hausdorff distance in the metric space (, δ). We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, 1 / 2 , and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance 1 / 2 from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of (, δ) from the perspectives of computability theory and reverse mathematics. [ABSTRACT FROM AUTHOR]

Colour the edges of the complete graph with vertex set { 1 , 2 , ⋯ , n } with an arbitrary number of colours. What is the smallest integer f(l, k) such that if n > f (l , k) then there must exist a monotone monochromatic path of length l or a monotone rainbow path of length k? Lefmann, Rödl, and Thomas conjectured in 1992 that f (l , k) = l k - 1 and proved this for l ⩾ (3 k) 2 k . We prove the conjecture for l ⩾ k 3 (log k) 1 + o (1) and establish the general upper bound f (l , k) ⩽ k (log k) 1 + o (1) · l k - 1 . This reduces the gap between the best lower and upper bounds from exponential to polynomial in k. We also generalise some of these results to the tournament setting. [ABSTRACT FROM AUTHOR]

Given a metric space M that contains at least two points, the chromatic number χ R ∞ n , M is defined as the minimum number of colours needed to colour all points of an n -dimensional space R ∞ n with the max-norm such that no isometric copy of M is monochromatic. The last two authors have recently shown that the value χ R ∞ n , M grows exponentially for all finite M. In the present paper we refine this result by giving the exact value χ M such that χ R ∞ n , M = (χ M + o (1)) n for all 'one-dimensional' M and for some of their Cartesian products. We also study this question for infinite M. In particular, we construct an infinite M such that the chromatic number χ R ∞ n , M tends to infinity as n → ∞. [ABSTRACT FROM AUTHOR]

A famous result of D. Walkup is that an m × n rectangle may be tiled by T-tetrominos if and only if both m and n are multiples of 4. The "if" portion may be proved by tiling a 4 × 4 block, and then copying that block to fill the rectangle; but this leads to regular, periodic tilings. In this paper we investigate how much "order" must be present in every tiling of a rectangle by T-tetrominos, where we measure order by length of arithmetic progressions of tiles. [ABSTRACT FROM AUTHOR]

We prove that, for every graph F with at least one edge, there is a constant c F such that there are graphs of arbitrarily large chromatic number and the same clique number as F in which every F-free induced subgraph has chromatic number at most c F . This generalises recent theorems of Briański, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every r ⩾ 3 the class of K r -free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth. [ABSTRACT FROM AUTHOR]

We present a short ultrafilter proof of the existence of monochromatic exponential triples \{a, b, b^a\} in any finite coloring of the natural numbers. We then generalize the construction and prove a new result on the existence of infinite monochromatic exponential patterns. [ABSTRACT FROM AUTHOR]

We investigate the origins of modern growth theory using Ramsey's seminal A Mathematical Theory of Saving (1928) by dividing Ramsey's optimal savings problem into two principal components, (1) the relationship between personal savings and the formation of capital, and (2) the optimal intertemporal balance between consumption and savings. The first component serves as a philosophical conduit for surveying classical and early neoclassical perspectives on savings and capital formation. The second details early neoclassicists' consideration of mathematical methods and intergenerational welfare. Taken together, we create a pathway between early discussions of savings and capital formation, and the origins of growth theory. [ABSTRACT FROM AUTHOR]

A mathematical procedure enabling the transformation of an arbitrary tessellation of a surface into a bi-colored, complete graph is introduced. Polygons constituting the tessellation are represented by vertices of the graphs. Vertices of the graphs are connected by two kinds of links/edges, namely, by a green link, when polygons have the same number of sides, and by a red link, when the polygons have a different number of sides. This procedure gives rise to a semi-transitive, complete, bi-colored Ramsey graph. The Ramsey semi-transitive number was established as Rtrans(3,3)=5 Shannon entropies of the tessellation and graphs are introduced. Ramsey graphs emerging from random Voronoi and Poisson Line tessellations were investigated. The limits ζ=limN→∞NgNr, where N is the total number of green and red seeds, Ng and Nr, were found ζ= 0.272 ± 0.001 (Voronoi) and ζ= 0.47 ± 0.02 (Poisson Line). The Shannon Entropy for the random Voronoi tessellation was calculated as S= 1.690 ± 0.001 and for the Poisson line tessellation as S = 1.265 ± 0.015. The main contribution of the paper is the calculation of the Shannon entropy of the random point process and the establishment of the new bi-colored Ramsey graph on top of the tessellations.