Umeå University's logo

Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

Our point of departure is Fleischner and Haggkvist (2014, Theorem 2). We first generalize this theorem. Then we apply it to cubic graphs whose vertex set can be decomposed into two classes, one class inducing a circuit and the other class inducing a (subdivision of a) caterpillar. (C) 2014 Elsevier B.V. All rights reserved.

In the first part of this article, we employ Thomason's Lollipop Lemma [25] to prove that bridgeless cubic graphs containing a spanning lollipop admit a cycle double cover (CDC) containing the circuit in the lollipop; this implies, in particular, that bridgeless cubic graphs with a 2-factor F having two components admit CDCs containing any of the components in the 2-factor, although it need not have a CDC containing all of F. As another example consider a cubic bridgeless graph containing a 2-factor with three components, all induced circuits. In this case, two of the components may separately be used to start a CDC although it is uncertain whether the third component may be part of some CDC. Numerous other corollaries shall be given as well. In the second part of the article, we consider special types of bridgeless cubic graphs for which a prominent circuit can be shown to be included in a CDC. The interest here is the proof technique and therefore we only give the simplest case of the theorem. Notably, we show that a cubic graph that consists of an induced 2k-circuit C together with an induced 4k-circuit T and an independent set of 2k vertices, each joined by one edge to C and two edges to T, has a CDC starting with T.

Let P be an n x n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbols. Assume further that s is the symbol of cell (r, c) in P. We prove that P is completable to a Latin square if n >= 8 and n is divisible by 4, or n <= 7 and n is not an element of {3, 4, 5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square. (C) 2013 Elsevier B.V. All rights reserved.

Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers.

We use a greedy probabilistic method to prove that, for every epsilon > 0, every m x n Latin rectangle on n symbols has an orthogonal mate, where m = (1 - epsilon)n. That is, we show the existence of a second Latin rectangle such that no pair of the mn cells receives the same pair of symbols in the two rectangles.

The Ising model was introduced in 1920 to describe a uniaxial system of magnetic moments, localized on a lattice, interacting via nearest-neighbour exchange interaction. It is the generic model for a continuous phase transition and arguably the most studied model in theoretical physics. Since it was solved for a two-dimensional lattice by Onsager in 1944, thereby representing one of the very few exactly solvable models in dimensions higher than one, it has served as a testing ground for new developments in analytic treatment and numerical algorithms. Only series expansions and numerical approaches, such as Monte Carlo simulations, are available in three dimensions. This review focuses on Monte Carlo simulation. We build upon a data set of unprecedented size. A great number of quantities of the model are estimated near the critical coupling. We present both a conventional analysis and an analysis in terms of a Puiseux series for the critical exponents. The former gives distinct values of the high- and low-temperature exponents; by means of the latter we can get these exponents to be equal at the cost of having true asymptotic behaviour being found only extremely close to the critical point. The consequences of this for simulations of lattice systems are discussed at length.

Define a graph to be a Kotzig graph if it is $m$-regular and has an $m$-edge colouring in which each pair of colours form a Hamiltonian cycle. We show that every cubic graph with spanning subgraph consisting of a subdivision of a Kotzig graph together with even cycles has a cycle double cover, in fact a 6-CDC. We prove this for two other families of graphs similar to Kotzig graphs as well. In particular, let $F$ be a 2-factor in a cubic graph $G$ and denote by $G_{F}$ the pseudograph obtained by contracting each component in $F$. We show that if there exist a cycle in $G_{F}$ through all vertices of odd degree, then $G$ has a CDC. We conjecture that every 3-connected cubic graph contains a spanning subgraph homeomorphic to a Kotzig graph. In a sequel we show that every cubic graph with a spanning homeomorph of a 2-connected cubic graph on at most 10 vertices has a CDC.

In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].

In this paper we describe a Monte Carlo sampling scheme for the Ising model and similar discrete-state models. The scheme does not involve any particular method of state generation but rather focuses on a new way of measuring and using the Monte Carlo data. We show how to reconstruct the entropy S of the model, from which, e.g., the free energy can be obtained. Furthermore we discuss how this scheme allows us to more or less completely remove the effects of critical fluctuations near the critical temperature and likewise how it reduces critical slowing down. This makes it possible to use simple state generation methods like the Metropolis algorithm also for large lattices.