Monotone paths in ordered graphs

LetV _fin andE _fin resp. denote the classes of graphsG with the property that no matter how we label the vertices (edges, resp.) ofG by members of a linearly ordered set, there will exist paths of arbitrary finite lengths with monotonically increasing labels. The classesV _inf andE _inf are defined similarly by requiring the existence of an infinite path with increasing labels. We proveE _inf ⫋V _inf ⫋V _fin ⫋E _fin. Finally we consider labellings by positive integers and characterize the class corresponding toV _inf.     

On restricted colourings ofK n

Given a sample graphH and two integers,n andr, we colourK _n byr colours and are interested in the following problem. Which colourings of the subgraphs isomorphic to H in K _n must always occur (and which types of colourings can occur whenK _n is coloured in an appropriate way)? These types of problems include theRamsey theory, where we ask: for whichn andr must a monochromaticH occur. They also include theanti-Ramsey type problems, where we are trying to ensure a totally multicoloured copy ofH, that is, anH each edge of which has different colour.     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

The Ramsey number for a cycle of length five vs. a complete graph of order six

It has been conjectured that r(C_m, K_n) = (m − 1)(n − 1) + 1 for all m ≥ n ≥ 4. This has been proved recently for n = 4 and n = 5. In this paper, we prove that r(C₅, K₆) = 21. This raises the possibility that r(C_m, K₆) = 5m − 4 for all m ≥ 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 99–108, 2000     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

Riemann-Roch and Abel-Jacobi theory on a finite graph

It is well known that a finite graph can be viewed, in many respects, as a discrete analogue of a Riemann surface. In this paper, we pursue this analogy further in the context of linear equivalence of divisors. In particular, we formulate and prove a graph-theoretic analogue of the classical Riemann-Roch theorem. We also prove several results, analogous to classical facts about Riemann surfaces, concerning the Abel-Jacobi map from a graph to its Jacobian. As an application of our results, we characterize the existence or non-existence of a winning strategy for a certain chip-firing game played on the vertices of a graph.     

Perfect matchings in hexagonal systems

A simple algorithm is developed which allows to decide whether or not a given hexagonal system has a perfect matching (and to find such a matching). This decision is also of chemical relevance since a hexagonal system is the skeleton of a benzenoid hydrocarbon molecule if and only if it has a perfect matching. Dedicated to Paul Erdős on his seventieth birthday     

Coloring arcs of convex sets

In this note we consider Ramsey-type problems on graphs whose vertices are represented by the vertices of a convex polygon in the Euclidean plane. The edges of the graph are represented by the segments between the points of the polygon. The edges are arbitrarily colored by a fixed number of colors and the problem is to decide whether there exist monochromatic subgraphs of certain types satisfying some geometric conditions. We will give lower and upper bounds for these geometric Ramsey numbers for certain paths and cycles and also some exact values. It turns out that the particular type of the embedding is crucial for the growth rate of the corresponding geometric Ramsey numbers. In particular, the Ramsey numbers for crossing 4-cycles and t colors grow quadratically in t, while for convex 4-cycles they grow at least exponentially.     

On the sum of the reciprocals of cycle lengths in sparse graphs

For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)⁻¹ for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths.     

Simple proof of the existence of restricted ramsey graphs by means of a partite construction

By means of a partite construction we present a short proof of the Galvin Ramsey property of the class of all finite graphs and of its strengthening proved in [5]. We also establish a generalization of those results. Further we show that for every positive integerm there exists a graphH which is Ramsey forK _m and does not contain two copies ofK _m with more than two vertices in common.     

A canonical restricted version of van der waerden’s theorem

It is shown that there is a subsetS of integers containing no (k+1)-term arithmetic progression such that if the elements ofS are arbitrarily colored (any number of colors),S will contain ak-term arithmetic progression for which all of its terms have the same color, or all have distinct colors.     

A multiplicative inequality for vertex Folkman numbers

Let G be a graph and a₁,…,a_r be positive integers. The symbol G→(a₁,…,a_r) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic a_i-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a₁,…,a_r;q)=min{|V(G)|:G→(a₁,…,a_r) and K_q?G} are considered. Let a_i, b_i, c_i, i∈{1,…,r}, s, t be positive integers and c_i=a_ib_i, 1?a_i?s,1?b_i?t. Then we prove that

F(c₁,c₂,…,c_r;st+1)?F(a₁,a₂,…,a_r;s+1)F(b₁,b₂,…,b_r;t+1).     

Multipartite graph—Sparse graph Ramsey numbers

The Ramsey numberr(F, G) is determined in the case whereF is an arbitrary fixed graph andG is a sufficiently large sparse connected graph with a restriction on the maximum degree of its vertices. An asymptotically correct upper bound is obtained forr(F, T) whereT is a sufficiently large, but otherwise arbitrary, tree.     

ASYMPTOTIC BOUNDS FOR IRREDUNDANT RAMSEY NUMBERS

Abstract

The irredundant Ramsey number s(m,n) is the smallest N such that in every red-blue colouring of the edges of K_N , either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We prove an asymptotic lower bound for s(m, n).     

Ramsey families which exclude a graph

For graphsA andB the relationA(B) _r ¹ means that for everyr-coloring of the vertices ofA there is a monochromatic copy ofB inA. Forb (G) is the family of graphs which do not embedG. A familyof graphs is Ramsey if for all graphsBthere is a graphAsuch thatA(B) _r ¹ . The only graphsG for which it is not known whether Forb (G) is Ramsey are graphs which have a cutpoint adjacent to every other vertex except one. In this paper we prove for a large subclass of those graphsG, that Forb (G) does not have the Ramsey property.This research has been supported in part by NSERC grant 69-1325.     

Unavoidable subgraphs of colored graphs

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let S_k be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K_k/2's or simply one K_k/2. Bollobás conjectured that for all k and ε>0, there exists an n(k,ε) such that if n?n(k,ε) then every two-edge-coloring of K_n, in which the density of each color is at least ε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε) for different ranges of ε. In particular, if ε is sufficiently close to , the gap between our upper and lower bounds for n(k,ε) is smaller than those for the classical Ramsey number R(k,k).