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:
Bootstrap Percolation in High Dimensions
Combinatorics Probability and Computing - Tập 19 Số 5-6 - Trang 643-692 - 2010
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 leastrinfected neighbours.
The setAis said to percolate if eventually all vertices are infected. Our aim is
to understand this process on the grid, [n]d, for arbitrary
functionsn=n(t),d=d(t) andr=r(t...
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
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-normal. For Gnp, the numbers are asymptotically log-normal for a wide range
of p, including p constant. The same results are obtained for random directed
graphs an...
A Tutte Polynomial for Coloured Graphs
Combinatorics Probability and Computing - Tập 8 Số 1-2 - Trang 45-93 - 1999
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 the Tutte polynomial, and show that any coloured graph
invariant sa...
Random Regular Graphs: Asymptotic Distributions and Contiguity
Combinatorics Probability and Computing - Tập 4 Số 4 - Trang 369-405 - 1995
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. Similar
result...
Two Short Proofs Concerning Tree-Decompositions
Combinatorics Probability and Computing - Tập 11 Số 6 - Trang 541-547 - 2002
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.
Odd Independent Transversals are Odd
Combinatorics Probability and Computing - Tập 15 Số 1-2 - Trang 193
Independent Transversals and Independent Coverings in Sparse Partite Graphs
Combinatorics Probability and Computing - Tập 6 Số 1 - Trang 115-125 - 1997
An [n, k, r]-partite graph is a graph whose vertex set, V, can be partitioned
into n pairwise-disjoint independent sets, V1, …, Vn, each containing exactly k
vertices, and the subgraph induced by Vi ∪ Vj contains exactly r independent
edges, for 1 [les ] i < j [les ] n. An independent transversal in an [n, k,
r]-partite graph is an independent set, T, consisting of n vertices, one from
each Vi. An...
Concentration on the Discrete Torus Using Transportation
Combinatorics Probability and Computing - Tập 18 Số 5 - Trang 835-860 - 2009
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 Tetali a...
Ramsey Classes and Homogeneous Structures
Combinatorics Probability and Computing - Tập 14 Số 1 - Trang 171-189 - 2005
Tổng số: 9
- 1