Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Journals
  3. Combinatorics, Probability and Computing
  4. Volume 2
Journal Home
Refine listing

Refine listing

Access:
Publication date:

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×
< Back to all issues

Volume 2 - December 1993

Contents

Page 2 of 3

Research Article

  • Minimization Problems for Infinite n-Connected Graphs

  • R. Halin
  • Published online by Cambridge University Press:
    12 September 2008, pp. 417-436

  • A graph G is called n-minimizable if it can be reduced, by deleting a set of its edges, to a minimally n-connected graph. It is shown that, if n-connected graphs G and H differ only by finitely many vertices and edges, then G is n-minimizable if and only if H is n-minimizable (Theorem 4.12). In the main result, conditions are given that a tree decomposition of an n-connected graph G must satisfy in order to guarantee that the n-minimizability of each of the members of this decomposition implies the n-minimizability of the graph G (Theorem 6.5).

  • Optimally Reliable Graphs for Both Vertex and Edge Failures

  • D. H. Smith
  • Published online by Cambridge University Press:
    12 September 2008, pp. 93-100

  • We consider networks in which both the nodes and the links may fail. We represent the network by an undirected graph G. Vertices of the graph fail with probability p and edges of the graph fail with probability q, where all failures are assumed independent. We shall be concerned with minimising the probability P(G) that G is disconnected for graphs with given numbers of vertices and edges. We show how to construct these optimal graphs in many cases when p and q are ‘small’.

  • Factorization in Fq[x] and Brownian Motion

  • Jennie C. Hansen
  • Published online by Cambridge University Press:
    12 September 2008, pp. 285-299

  • We consider the set of polynomials of degree n over a finite field and put the uniform probability measure on this set. Any such polynomial factors uniquely into a product of its irreducible factors. To each polynomial we associate a step function on the interval [0,1] such that the size of each jump corresponds to the number of factors of a certain degree in the factorization of the random polynomial. We normalize these random functions and show that the resulting random process converges weakly to Brownian motion as n → ∞. This result complements earlier work by the author on the order statistics of the degree sequence of the factors of a random polynomial.

Front matter

  • CPC volume 2 issue 1 Cover and Front matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Research Article

  • Image Partition Regularity of Matrices

  • Neil Hindman, Imre Leader
  • Published online by Cambridge University Press:
    12 September 2008, pp. 437-463

  • Many of the classical results of Ramsey Theory, including those of Hilbert, Schur, and van der Waerden, are naturally stated as instances of the following problem: given a u × ν matrix A with rational entries, is it true, that whenever the set ℕ of positive integers is finitely coloured, there must exist some x∈ℕν such that all entries of Ax are the same colour? While the theorems cited are all consequences of Rado's theorem, the general problem had remained open. We provide here several solutions for the alternate problem, which asks that x∈ℕν. Based on this, we solve the general problem, giving various equivalent characterizations.

  • A Discrete Analogue of a Theorem of Makarov

  • Gregory F. Lawler
  • Published online by Cambridge University Press:
    12 September 2008, pp. 181-199

  • A theorem of Makarov states that the harmonic measure of a connected subset of ℝ2 is supported on a set of Hausdorff dimension one. This paper gives an analogue of this theorem for discrete harmonic measure, i.e., the hitting measure of simple random walk. It is proved that for any 1/2 < α < 1, β < α − 1/2, there is a constant k such that for any connected subset A ⊂ ℤ2 of radius n,

    where HA denotes discrete harmonic measure.

  • Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains

  • Salvatore Ingrassia
  • Published online by Cambridge University Press:
    12 September 2008, pp. 301-323

  • In this paper we consider the problem of estimating the spectral gap of a reversible Markov chain in terms of geometric quantities associated with the underlying graph. This quantity provides a bound on the rate of convergence of a Markov chain towards its stationary distribution. We give a critical and systematic treatment of this subject, summarizing and comparing the results of the two main approaches in the literature, algebraic and functional. The usefulness and drawbacks of these bounds are also discussed here.

Back matter

  • CPC volume 2 issue 1 Cover and Back matter

  • Published online by Cambridge University Press:
    12 September 2008, p. b1
    • Article
      • You have access
    • PDF
    • Export citation

Research Article

  • Linear-Time Approximation Algorithms for the Max Cut Problem

  • Nguyen van Ngoc, Zsolt Tuza
  • Published online by Cambridge University Press:
    12 September 2008, pp. 201-210

  • Let G be a connected graph with n vertices and m edges (multiple edges allowed), and let k ≥ 2 be an integer. There is an algorithm with (optimal) running time of O(m) that finds

    (i) a bipartite subgraph of G with ≥ m/2 + (n − 1)/4 edges,

    (ii) a bipartite subgraph of G with ≥ m/2 + 3(n−1)/8 edges if G is triangle-free,

    (iii) a k-colourable subgraph of G with ≥ m − m/k + (n−1)/k + (k − 3)/2 edges if k ≥ 3 and G is not k-colorable.

    Infinite families of graphs show that each of those lower bounds on the worst-case performance are best possible (for every algorithm). Moreover, even if short cycles are excluded, the general lower bound of m − m/k cannot be replaced by m − m/k + εm for any fixed ε > 0; and it is NP-complete to decide whether a graph with m edges contains a k-colorable subgraph with more than m − m/k + εm edges, for any k ≥ 2 and ε> 0, ε < 1/k.

Front matter

  • CPC volume 2 issue 2 Cover and Front matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Research Article

  • Local-Global Phenomena in Graphs

  • Nathan Linial
  • Published online by Cambridge University Press:
    12 September 2008, pp. 491-503

  • This is a survey of a number of recent papers dealing with graphs from a geometric perspective. The main theme of these studies is the relationship between graph properties that are local in nature, and global graph parameters. Connections with the theory of distributed computing are pointed out and many open problems are presented.

  • Threshold Channel Graphs

  • Miro Kraetzl, Charles J. Colbourn
  • Published online by Cambridge University Press:
    12 September 2008, pp. 337-349

  • A transformation that increases the blocking probability of the channel graphs arising in interconnection networks is developed. This provides the basis for eminently computing a bound on the blocking probability by applying the transformation to reduce an arbitrary four-stage channel graph to a threshold channel graph. The four-stage channel graph that is most likely to block, given links that are equally likely to block, is characterized. Partial results are proved concerning the threshold channel graphs that are least likely to block.

Back matter

  • CPC volume 2 issue 2 Cover and Back matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. b1-b2
    • Article
      • You have access
    • PDF
    • Export citation

Research Article

  • On Random Generation of the Symmetric Group

  • Tomasz Łuczak, László Pyber
  • Published online by Cambridge University Press:
    12 September 2008, pp. 505-512

  • We prove that the probability i(n, k) that a random permutation of an n element set has an invariant subset of precisely k elements decreases as a power of k, for k ≤ n/2. Using this fact, we prove that the fraction of elements of Sn belong to transitive subgroups other than Sn or An tends to 0 when n → ∞, as conjectured by Cameron. Finally, we show that for every ∈ > 0 there exists a constant C such that C elements of the symmetric group Sn, chosen randomly and independently, generate invariably Sn with probability at least 1 − ∈. This confirms a conjecture of McKay.

Page 2 of 3