Combinatorics Probability and Computing
SCIE-ISI SCOPUS (1992-2023)
0963-5483
1469-2163
Anh Quốc
Cơ quản chủ quản: CAMBRIDGE UNIV PRESS , Cambridge University Press
Lĩnh vực:
Statistics and ProbabilityTheoretical Computer ScienceApplied MathematicsComputational Theory and Mathematics
Phân tích ảnh hưởng
Các bài báo tiêu biểu
Random Regular Graphs: Asymptotic Distributions and ContiguityThe asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose logarithm can be written as an infinite linear combination of independent Poisson variables, and thus the logarithm has an infinitely divisible distribution with a certain discrete Lévy measure. Simila... ...
Tập 4 Số 4 - Trang 369-405 - 1995
A Tutte Polynomial for Coloured GraphsWe define a polynomial W on graphs with colours on the edges, by generalizing the
spanning tree expansion of the Tutte polynomial as far as possible: we give necessary and
sufficient conditions on the edge weights for this expansion not to depend on the order used.
We give a contraction-deletion formula for W analogous to that for th... ...
Tập 8 Số 1-2 - Trang 45-93 - 1999
Bootstrap Percolation in High DimensionsInr -neighbour bootstrap percolation on a graphG , a set of initially infected verticesA ⊂V (G ) is chosen independently at random, with densityp , and new vertices are subsequently infected if they have at leastr...
Tập 19 Số 5-6 - Trang 643-692 - 2010
The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random GraphThe numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lowest limit m ≍ n 3/2 , these numbers are asymptotically log-norma... ...
Tập 3 Số 1 - Trang 97-126 - 1994
Two Short Proofs Concerning Tree-DecompositionsWe give short proofs of the following two results: Thomas's theorem that every finite graph
has a linked tree-decomposition of width no greater than its tree-width; and the ‘tree-width
duality theorem’ of Seymour and Thomas, that the tree-width of a finite graph is exactly
one less than the largest order of its brambles.
Tập 11 Số 6 - Trang 541-547 - 2002
Concentration on the Discrete Torus Using TransportationThe sub-Gaussian constant of a graph arises naturally in bounding the moment-generating function of Lipschitz functions on the graph, with a given probability measure on the set of vertices. The closely related spread constant of a graph measures the maximal variance over all Lipschitz functions on the graph. As such they are both useful (as demonstrated in the works of Bobkov, Houdré and ... ...
Tập 18 Số 5 - Trang 835-860 - 2009
Independent Transversals and Independent Coverings in Sparse Partite GraphsAn [n , k , r ]-partite graph
is a graph whose vertex set, V , can be partitioned into n
pairwise-disjoint independent sets,
V 1 , …, V ...
Tập 6 Số 1 - Trang 115-125 - 1997