Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: random graph

Sortuj według:

Ogranicz wyniki do:

Ramsey Properties of Random Graphs and Folkman Numbers

100%

Rödl V., Ruciński A., Schacht M.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 3

755-776

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 the involved parameters. Here, for r = 2, we provide a self-contained proof of a quantitative version of the Ramsey threshold theorem with only double exponential dependencies between the constants. As a corollary we obtain a double exponential upper bound on the 2-color Folkman numbers. By a different proof technique, a similar result was obtained independently by Conlon and Gowers.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Chvátal's Condition cannot hold for both a graph and its complement

100%

Kostochka A., West D.

Discussiones Mathematicae Graph Theory

2006

tom 26

nr 1

73-76

Chvátal's Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_i > i$ or $d_{n-i} ≥ n-i$. We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

The independent domination number of a random graph

100%

Clark L., Johnson D.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 1

129-142

We prove a two-point concentration for the independent domination number of the random graph $G_{n,p}$ provided p²ln(n) ≥ 64ln((lnn)/p).

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Clark L.

1 Johnson D.

1 Kostochka A.

1 Ruciński A.

1 Rödl V.

1 Schacht M.

1 West D.

1 2017

1 2011

1 2006

Wyniki wyszukiwania

Ramsey Properties of Random Graphs and Folkman Numbers

Chvátal's Condition cannot hold for both a graph and its complement

The independent domination number of a random graph