Currently displaying 1 – 20 of 31

Showing per page

Order by Relevance | Title | Year of publication

Metric spaces with point character equal to their size

C. AvartP. KomjathVojtěch Rödl — 2010

Commentationes Mathematicae Universitatis Carolinae

In this paper we consider the point character of metric spaces. This parameter which is a uniform version of dimension, was introduced in the context of uniform spaces in the late seventies by Jan Pelant, Cardinal reflections and point-character of uniformities, Seminar Uniform Spaces (Prague, 1973–1974), Math. Inst. Czech. Acad. Sci., Prague, 1975, pp. 149–158. Here we prove for each cardinal κ , the existence of a metric space of cardinality and point character κ . Since the point character can...

Ramsey Properties of Random Graphs and Folkman Numbers

Vojtěch RödlAndrzej RucińskiMathias Schacht — 2017

Discussiones Mathematicae Graph Theory

For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies between...

On generalized shift graphs

Christian AvartTomasz ŁuczakVojtěch Rödl — 2014

Fundamenta Mathematicae

In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets A = a , . . . , a k and B = b , . . . , b k joined if a < a = b < a = b < < a k = b k - 1 < b k . They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting...

Page 1 Next

Download Results (CSV)