Un modéle d'lnspections optimales

We consider the following model: we inspect the motion of a Markov process with which an “evolution cost” is associated. We inspect the process at times T ₁…, T _n ,…. If when we inspect, its value is in a given set A, it continues its evolution, otherwise we kill it. At each inspection we associate an "inspection cost" and a "killing cost". The problem consists of finding a sequence of optimal inspections. After the modelization we construct the value function by an iterative procedure as in impulse control theory, by using the theory of analytic functions and theorems of section. Thanks to the criteria of optimality we get a sequence of optimal inspections under very general hypotheses.     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Gröbner bases for the Hilbert ideal and coinvariants of the dihedral group D2p

We consider a finite dimensional representation of the dihedral group D_2p over a field of characteristic two where p is an odd integer and study the corresponding Hilbert ideal I_H. We show that I_H has a universal Gröbner basis consisting of invariants and monomials only. We provide sharp bounds for the degree of an element in this basis and in a minimal generating set for I_H. We also compute the top degree of coinvariants when p is prime.     

Generating uniformly distributed random latin squares

By simulating an ergodic Markov chain whose stationary distribution is uniform over the space of n × n Latin squares, we can obtain squares that are (approximately) uniformly distributed; we offer two such chains. The central issue is the construction of “moves” that connect the squares. Our first approach uses the fact that an n × n Latin square is equivalent to an n × n × n contingency table in which each line sum equals 1. We relax the nonnegativity condition on the table's cells, allowing “improper” tables that have a single—1-cell. A simple set of moves connects this expanded space of tables [the diameter of the associated graph is bounded by 2(n − 1)³], and suggests a Markov chain whose subchain of proper tables has the desired uniform stationary distribution (with an average of approximately n steps between proper tables). By grouping these moves appropriately, we derive a class of moves that stay within the space of proper Latin squares [with graph diameter bounded by 4(n − 1)²]; these may also be used to form a suitable Markov chain. © 1996 John Wiley & Sons, Inc.     

A multi-dimensional Markov chain and the Meixner ensemble

We show that the transition probability of the Markov chain (G(i,1),...,G(i,n)) _i≥1, where the G(i,j)’s are certain directed last-passage times, is given by a determinant of a special form. An analogous formula has recently been obtained by Warren in a Brownian motion model. Furthermore we demonstrate that this formula leads to the Meixner ensemble when we compute the distribution function for G(m,n). We also obtain the Fredholm determinant representation of this distribution, where the kernel has a double contour integral representation.     

On the Commuting Graph of Dihedral Group

Let Γ be a non-abelian group and Ω ? Γ. We define the commuting graph G = 𝒞(Γ, Ω) with vertex set Ω and two distinct elements of Ω are joined by an edge when they commute in Γ. In this article, among some properties of commuting graphs, we investigate distant properties as well as detour distant properties of commuting graph on D_2n. We also study the metric dimension of commuting graph on D_2n and compute its resolving polynomial.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Orthogonal one-factorization graphs

An orthogonal one-factorization graph (OOFG) is a graph in which the vertices are one-factorizations of some underlying graph H, and two vertices are adjacent if and only if the one-factorizations are orthogonal. An arbitrary finite graph, G, is realizable if there is an OOFG isomorphic to G. We show that every finite graph is realizable as an OOFG with underlying graph K_n for some n. We also discuss some special cases.     

Continuum limits for classical sequential growth models

A random graph order, also known as a transitive percolation process, is defined by taking a random graph on the vertex set {0,…,n ? 1} and putting i below j if there is a path i = i₁…i_k = j in the graph with i₁ < … < i_k. Rideout and Sorkin 14 provide computational evidence that suitably normalized sequences of random graph orders have a “continuum limit.” We confirm that this is the case and show that the continuum limit is always a semiorder. Transitive percolation processes are a special case of a more general class called classical sequential growth models. We give a number of results describing the large‐scale structure of a general classical sequential growth model. We show that for any sufficiently large n, and any classical sequential growth model, there is a semiorder S on {0,…,n ‐ 1} such that the random partial order on {0,…,n ‐ 1} generated according to the model differs from S on an arbitrarily small proportion of pairs. We also show that, if any sequence of classical sequential growth models has a continuum limit, then this limit is (essentially) a semiorder. We give some examples of continuum limits that can occur. Classical sequential growth models were introduced as the only models satisfying certain properties making them suitable as discrete models for spacetime. Our results indicate that this class of models does not contain any that are good approximations to Minkowski space in any dimension ≥ 2. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Torpid mixing of the Wang–Swendsen–Kotecký algorithm for sampling colorings

We study the problem of sampling uniformly at random from the set of k-colorings of a graph with maximum degree Δ. We focus attention on the Markov chain Monte Carlo method, particularly on a popular Markov chain for this problem, the Wang–Swendsen–Kotecký (WSK) algorithm. The second author recently proved that the WSK algorithm quickly converges to the desired distribution when k11Δ/6. We study how far these positive results can be extended in general. In this note we prove the first non-trivial results on when the WSK algorithm takes exponentially long to reach the stationary distribution and is thus called torpidly mixing. In particular, we show that the WSK algorithm is torpidly mixing on a family of bipartite graphs when 3k<Δ/(20logΔ), and on a family of planar graphs for any number of colors. We also give a family of graphs for which, despite their small chromatic number, the WSK algorithm is not ergodic when kΔ/2, provided k is larger than some absolute constant k₀.     

Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = (V,E). The dynamics is conjectured to converge to equilibrium in O(|V|^1/4) steps at any (inverse) temperature β, yet there are few results providing o(|V|) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite d‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics, for which we obtain new tight mixing time bounds.     

Note on a conjecture of toft

A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK ₄. We show that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK ₄. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK ₄. (A graph is 3-degenerate if every subgraph has some node of degree at most three.)     

A graphical characterization of the largest chain graphs

The paper presents a graphical characterization of the largest chain graphs which serve as unique representatives of classes of Markov equivalent chain graphs. The characterization is a basis for an algorithm constructing, for a given chain graph, the largest chain graph equivalent to it. The algorithm was used to generate a catalog of the largest chain graphs with at most five vertices. Every item of the catalog contains the largest chain graph of a class of Markov equivalent chain graphs and an economical record of the induced independency model.     

Nash inequalities for finite Markov chains

This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds onl ₂-norms in terms of Dirichlet forms andl ₁-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.     

Is every cycle basis fundamental?

A collection of (simple) cycles in a graph is called fundamental if they form a basis for the cycle space and if they can be ordered such that C_j(C₁ U … U C_j-1) ≠ Ø for all j. We characterize by excluded minors those graphs for which every cycle basis is fundamental. We also give a constructive characterization that leads to a (polynomial) algorithm for recognizing these graphs. In addition, this algorithm can be used to determine if a graph has a cycle basis that covers every edge two or more times. An equivalent dual characterization for the cutset space is also given.     

Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes

We consider the Hamiltonian cycle problem (HCP) embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We also consider two quadratic functionals over the same space. We show that when the perturbation parameter, ? is sufficiently small the Hamiltonian cycles of the given directed graph are precisely the maximizers of one of these quadratic functionals over the frequency space intersected with an appropriate (single) contour of the second quadratic functional. In particular, all these maximizers have a known Euclidean distance of z _m (?) from the origin. Geometrically, this means that Hamiltonian cycles, if any, are the points in the frequency polytope where the circle of radius z _m (?) intersects a certain ellipsoid.     

The Growth of Limits of Vertex Replacement Rules

In this article, we give conditions to distinguish whether a vertex replacement rule given by a single graph H yields a limit graph having polynomial or exponential growth. In the case of polynomial growth, we compute the growth degree of the limit graph.     

Bounds on the cover time

Consider a particle that moves on a connected, undirected graphG withn vertices. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. Tocover time is the first time when the particle has visited all the vertices in the graph starting from a given vertex. In this paper, we present upper and lower bounds that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the random walk above. An interesting consequence is that regular expander graphs have expected cover time (n logn).This research was done while this author was a postdoctoral fellow in the Department of Computer Science, Princeton University, and it was supported in part by DNR grant N00014-87-K-0467.     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic

We investigate the definability in monadic ∑₁¹ and monadic Π₁¹ of the problems REG_k, of whether there is a regular subgraph of degree k in some given graph, and XREG_k, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REG_k^k and XREG_k^k, respectively, for k ≥ 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REG_k^k and XREG_k^k are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑₁¹ games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑₁¹ and monadic Π₁¹, and we compare the definability of these problems (in monadic ∑₁¹ and monadic Π₁¹ with their computational complexity (which varies from solvable using logspace to NP - complete).