Ramsey theory for graph connectivity

r_c(k) Denotes the smallest integer such that any c-edge-coloring of the r_c(k) vertex complete graph has a monochromatic k-connected subgraph. For any c, k ≧ 2, we show 2c(k – 1) + 1 ≦ r_c(k) < 10/3 c(k – 1) + 1, and further that 4(k – 1) + 1 ≧ r₂(k) < (3 + √ (k – 1) + 1. Some exact values for various Ramsey connectivity numbers are also computed.     

On some extremal problems in graph theory

The author proves that ifC is a sufficiently large constant then every graph ofn vertices and [Cn ^3/2] edges contains a hexagonX ₁,X ₂,X ₃,X ₄,X ₅,X ₆ and a seventh vertexY joined toX ₁,X ₃ andX ₅. The problem is left open whether our graph contains the edges of a cube, (i.e. an eight vertexZ joined toX ₂,X ₄ andX ₆).     

On two problems in extension theory

In this note we introduce the concept of a quasi-finite complex. Next, we show that for a given countable simplicial complex L the following conditions are equivalent:

•

L is quasi-finite.

•

There exists a [L]-invertible mapping of a metrizable compactum X with e-dimX?[L] onto the Hilbert cube.Finally, we construct an example of a quasi-finite complex L such that its extension type [L] does not contain a finitely dominated complex.

     

Extremal problems in graph theory

The aim of this note is to give an account of some recent results and state a number of conjectures concerning extremal properties of graphs.     

Two problems in extremal graph theory

Graphs and Combinatorics -     

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.     

关于图论课教学的思考

在科学技术迅猛发展的今天，尤其是网络和信息产业的兴起，图论课越来越受到广泛的重视,本文总结了多年的图论课教学改革的一些经验．     

On zero sum Ramsey numbers: Multiple copies of a graph

As a consequence of our main result, a theorem of Schrijver and Seymour that determines the zero sum Ramsey numbers for the family of all r-hypertrees on m edges and a theorem of Bialostocki and Dierker that determines the zero sum Ramsey numbers for r-hypermatchings are combined into a single theorem. Another consequence is the determination of zero sum Ramsey numbers of multiple copies of some small graphs.     

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.     

A Ramsey property for graph invariants

We consider the problem of which graph invariants have a certain property relating to Ramsey's theorem. Invariants which have this property are called Ramsey functions. We examine properties of chains of graphs associated with Ramsey functions. Methods are developed which enable one to prove that a given invariant is not a Ramsey function. Results for several familiar invariants are presented.     

Schreier sets in Ramsey theory

We show that Ramsey theory, a domain presently conceived to guarantee the existence of large homogeneous sets for partitions on -tuples of words (for every natural number ) over a finite alphabet, can be extended to one for partitions on Schreier-type sets of words (of every countable ordinal). Indeed, we establish an extension of the partition theorem of Carlson about words and of the (more general) partition theorem of Furstenberg-Katznelson about combinatorial subspaces of the set of words (generated from -tuples of words for any fixed natural number ) into a partition theorem about combinatorial subspaces (generated from Schreier-type sets of words of order any fixed countable ordinal). Furthermore, as a result we obtain a strengthening of Carlson's infinitary Nash-Williams type (and Ellentuck type) partition theorem about infinite sequences of variable words into a theorem, in which an infinite sequence of variable words and a binary partition of all the finite sequences of words, one of whose components is, in addition, a tree, are assumed, concluding that all the Schreier-type finite reductions of an infinite reduction of the given sequence have a behavior determined by the Cantor-Bendixson ordinal index of the tree-component of the partition, falling in the tree-component above that index and in its complement below it.

     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .