The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “The Chromatic Number of Random Intersection Graphs”

Ramsey Properties of Random Graphs and Folkman Numbers

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht (2017)

Discussiones Mathematicae Graph Theory

Similarity:

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...

The sizes of components in random circle graphs

Ramin Imany-Nabiyyi (2008)

Discussiones Mathematicae Graph Theory

Similarity:

We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure...

A note on domination parameters in random graphs

Anthony Bonato, Changping Wang (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Domination parameters in random graphs G(n,p), where p is a fixed real number in (0,1), are investigated. We show that with probability tending to 1 as n → ∞, the total and independent domination numbers concentrate on the domination number of G(n,p).

Asymptotic properties of random graphs

Zbigniew Palka

Similarity:

CONTENTS1. Introduction...........................................................................5  1.1. Purpose and scope..........................................................5  1.2. Probability-theoretic preliminaries....................................6  1.3. Graphs............................................................................11  1.4. Random graphs..............................................................132. Vertex-degrees....................................................................15  2.1....

Random procedures for dominating sets in bipartite graphs

Sarah Artmann, Jochen Harant (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.

Infinite paths and cliques in random graphs

Alessandro Berarducci, Pietro Majer, Matteo Novaga (2012)

Fundamenta Mathematicae

Similarity:

We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.