Upper bounds on the non-3-colourability threshold of random graphs.
Fountoulakis, Nikolaos, McDiarmid, Colin (2002)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Fountoulakis, Nikolaos, McDiarmid, Colin (2002)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
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...
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).
Subramanian, C.R. (2001)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
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....
Beer, Elizabeth, Fill, James Allen, Janson, Svante, Scheinerman, Edward R. (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Zbigniew Pałka (1982)
Colloquium Mathematicae
Similarity:
Ove Frank, Krzysztof Nowicki (1989)
Banach Center Publications
Similarity:
Aiello, William, Chung, Fan, Lu, Linyuan (2001)
Experimental Mathematics
Similarity:
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.
G. Trybuś (1974)
Applicationes Mathematicae
Similarity:
Katarzyna Rybarczyk (2017)
Discussiones Mathematicae Graph Theory
Similarity:
We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.
Wojciech Kordecki (1996)
Discussiones Mathematicae Graph Theory
Similarity:
The asymptotic distributions of the number of vertices of a given degree in random graphs, where the probabilities of edges may not be the same, are given. Using the method of Poisson convergence, distributions in a general and particular cases (complete, almost regular and bipartite graphs) are obtained.
W. Dziubdziela (1976)
Applicationes Mathematicae
Similarity:
R. Kaufman (1970)
Studia Mathematica
Similarity:
Omer Angel, Alexander S. Kechris, Russell Lyons (2014)
Journal of the European Mathematical Society
Similarity:
We show that the only random orderings of finite graphs that are invariant under isomorphism and induced subgraph are the uniform random orderings. We show how this implies the unique ergodicity of the automorphism group of the random graph. We give similar theorems for other structures, including, for example, metric spaces. These give the first examples of uniquely ergodic groups, other than compact groups and extremely amenable groups, after Glasner andWeiss’s example of the group...
Mustafa, Ghulam, Nosh, Nusrat Anjum, Rashid, Abdur (2005)
Lobachevskii Journal of Mathematics
Similarity:
Nguyen, Quy Hy, Nguyen, Ngoc Cuong (2015-12-08T12:59:38Z)
Acta Universitatis Lodziensis. Folia Mathematica
Similarity:
Rybarczyk, Katarzyna (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity: