Combinatorics Probability and Computing

Công bố khoa học tiêu biểu

* Dữ liệu chỉ mang tính chất tham khảo

Sắp xếp:  
The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
Combinatorics Probability and Computing - Tập 3 Số 1 - Trang 97-126 - 1994
Svante Janson
The 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 ≍ n3/2, these numbers are asymptotically log-norma...... hiện toàn bộ
Two Short Proofs Concerning Tree-Decompositions
Combinatorics Probability and Computing - Tập 11 Số 6 - Trang 541-547 - 2002
PATRICK BELLENBAUM, Reinhard Diestel
We 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.
Concentration on the Discrete Torus Using Transportation
Combinatorics Probability and Computing - Tập 18 Số 5 - Trang 835-860 - 2009
Marcus D. Sammer, Prasad Tetali
The 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 ...... hiện toàn bộ
Bootstrap Percolation in High Dimensions
Combinatorics Probability and Computing - Tập 19 Số 5-6 - Trang 643-692 - 2010
József Balogh, Béla Bollobás, Robert Morris
Inr-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... hiện toàn bộ
A Tutte Polynomial for Coloured Graphs
Combinatorics Probability and Computing - Tập 8 Số 1-2 - Trang 45-93 - 1999
Béla Bollobás, Oliver Riordan
We 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...... hiện toàn bộ
Random Regular Graphs: Asymptotic Distributions and Contiguity
Combinatorics Probability and Computing - Tập 4 Số 4 - Trang 369-405 - 1995
Svante Janson
The 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...... hiện toàn bộ
Odd Independent Transversals are Odd
Combinatorics Probability and Computing - Tập 15 Số 1-2 - Trang 193
Penny Haxell, Tibor Szabó
Independent Transversals and Independent Coverings in Sparse Partite Graphs
Combinatorics Probability and Computing - Tập 6 Số 1 - Trang 115-125 - 1997
Raphael Yuster
An [n, k, r]-partite graph is a graph whose vertex set, V, can be partitioned into n pairwise-disjoint independent sets, V1, …, V... hiện toàn bộ
Ramsey Classes and Homogeneous Structures
Combinatorics Probability and Computing - Tập 14 Số 1 - Trang 171-189 - 2005
Jaroslav Nešetřil
Tổng số: 9   
  • 1