Tunneling of the hard‐core model on finite triangular lattices

We consider the hard‐core model on finite triangular lattices with Metropolis dynamics. Under suitable conditions on the triangular lattice sizes, this interacting particle system has 3 maximum‐occupancy configurations and we investigate its high‐fugacity behavior by studying tunneling times, that is, the first hitting times between these maximum‐occupancy configurations, and the mixing time. The proof method relies on the analysis of the corresponding state space using geometrical and combinatorial properties of the hard‐core configurations on finite triangular lattices, in combination with known results for first hitting times of Metropolis Markov chains in the equivalent zero‐temperature limit. In particular, we show how the order of magnitude of the expected tunneling times depends on the triangular lattice sizes in the low‐temperature regime and prove the asymptotic exponentiality of the rescaled tunneling time leveraging the intrinsic symmetry of the state space.     

Colouring Steiner systems with specified block colour patterns

We consider colourings of Steiner systems S(2,3,v) and S(2,4,v) in which blocks have prescribed colour patterns, as a refinement of the classical weak colourings. The main question studied is, given an integer k, does there exist a colouring of given type using exactly k colours? For several types of colourings, a complete answer to this question is obtained while for other types, partial results are presented. We also discuss the question of the existence of uncolourable systems.     

Sampling Eulerian orientations of triangular lattice graphs

We consider the problem of sampling from the uniform distribution on the set of Eulerian orientations of subgraphs of the triangular lattice. Although Mihail and Winkler (1989) showed that this can be achieved in polynomial time for any graph, the algorithm studied here is more natural in the context of planar Eulerian graphs. We analyse the mixing time of a Markov chain on the Eulerian orientations of a planar graph which moves between orientations by reversing the edges of directed faces. Using path coupling and the comparison method we obtain a polynomial upper bound on the mixing time of this chain for any solid subgraph of the triangular lattice. By considering the conductance of the chain we show that there exist non-solid subgraphs (subgraphs with holes) for which the chain will always take an exponential amount of time to converge. Finally, we show that the problem of counting Eulerian orientations remains #P-complete when restricted to planar graphs (Mihail and Winkler had already established this for general graphs).     

Recolouring-resistant colourings

We study colourings of graphs with the property that the number of used colours cannot be reduced by applying some recolouring operation. A well-studied example of such colourings are b-colourings, which were introduced by Irving and Manlove [R.W. Irving, D.F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127-141]. Given a graph and a colouring, a recolouring operation specifies a set of vertices of the graph on which the colouring can be changed. We consider two such operations: One which allows the recolouring of all vertices within some given distance of some colour class, and another which allows the recolouring of all vertices that belong to one of a given number of colour classes. Our results extend known results concerning b-colourings and the associated b-chromatic number.     

Colouring prime distance graphs

Four colours are necessary and sufficient to colour all the integers so that any two with difference equal to a prime have different colours. We investigate the corresponding problem when the setD of prescribed differences is a proper subset of the primes. In particular, we prove that ifD contains {2, 3} and also contains a pair of twin primes (one of which may be 3), then four colours are necessary. Numerous results regarding periodic colourings are also obtained. However, the problem of characterizing those setsD which necessitate four colours remains open.     

Obstructions to locally injective oriented improper colourings

Oriented colourings that are injective on in-neighbourhoods, but which need not be proper colourings, are considered. We first find some bounds on the number of colours needed, and determine the complexity of the associated decision problem. We then consider the polynomial cases, and describe efficient algorithms, based on colouring extensions, which produce either a colouring with the given number of colours or a forbidden substructure.     

Perfect colourings of cyclotomic integers

Perfect colourings of the rings of cyclotomic integers of class number one are studied. It is shown that all colourings induced by ideals (q) are chirally perfect, and vice versa. A necessary and sufficient condition for a colouring to be perfect is obtained, depending on the factorisation of q. This result yields the colour symmetry group H in general. Furthermore, the colour preserving group K is determined in all but finitely many cases. An application to colourings of quasicrystals is given.     

Frugal, acyclic and star colourings of graphs

Given a graph G=(V,E), a vertex colouring of V is t-frugal if no colour appears more than t times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind et al. (1997) [14] studied proper t-frugal colourings and Yuster (1998) [22] studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study.     

Upper triangular matrix walk: Cutoff for finitely many columns

We consider random walk on the space of all upper triangular matrices with entries in which forms an important example of a nilpotent group. Peres and Sly proved tight bounds on the mixing time of this walk up to constants. It is well known that the column projection of this chain is the one dimensional East process. In this article we complement the Peres‐Sly result by proving a cutoff result for the mixing of finitely many columns in the upper triangular matrix walk at the same location as the East process of the same dimension. The proof is based on a recursive argument which uses a local version of a dual process appearing in a previous study, various combinatorial consequences of mixing and concentration results for the movement of the front in the one dimensional East process.     

Acyclic improper colourings of graphs with bounded maximum degree

For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t.We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182].     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

Lattice geometry and pythagorean triangles

By drawing a Pythagorean triangle in a quadratic lattice and attaching a congruent lattice at the hypotenuse there will occur a Moiré effect with a new quadratic lattice of enlarged scale in the superposition. This new lattice is related to the parameterization of the Pythagorean triangle. A similar effect occurs with triangles with integer side lengths and an angle of 120° in a regular triangular lattice. We work with dot lattices on transparencies to visualize the optical effects.     

Symmetry Groups of Coloured Graphs

A perfect colouring Φ of a simple undirected connected graph G is an edge colouring such that each vertex is incident with exactly one edge of each colour. This paper concerns the problem of representing groups by graphs with perfect colourings. We define groups of graph automorphisms, which preserve the structure of the colouring, and characterize these groups up to isomorphism. Our considerations are based on the fact that every perfectly coloured graph is isomorphic to a Schreier coset graph on a group generated by involutions.     

On the class of proper linear differential systems with unbounded coefficients

Proper linear differential systems (whose coefficients are not necessarily bounded on the half-line) are defined as systems for which there exists a generalized Lyapunov transformation reducing them to a diagonal system with constant coefficients (Basov). We prove that Lyapunov’s original definition of a proper system and the Perron and Vinograd criteria hold for the class of proper systems as well as for the class of proper systems with uniformly bounded coefficients. We show that the Lyapunov properness criterion for a triangular system fails for systems with unbounded coefficients; namely, we construct an improper system with the following properties: the Lyapunov exponents of all nonzero solutions of that system are finite and exact, and for an arbitrary reduction of this system by a generalized Lyapunov transformation to triangular form, its diagonal coefficients have finite exact mean values, whose set with regard of multiplicities is independent of the choice of the transformation. In addition, we show that the main property of proper systems with uniformly bounded coefficients (preservation of conditional exponential stability as well as the dimension of the exponentially stable manifold and the exponent of the asymptotic behavior of solutions under perturbations of higher-order smallness) holds for proper systems with unbounded coefficients as well.     

A new class of Kadison-Singer algebras

We show that the projection lattice generated by a maximal nest and a rank one projection in a separable infinite-dimensional Hilbert space is in general reflexive. Moreover we show that the corresponding reflexive algebra has a maximal triangular property, equivalently, it is a Kadison-Singer algebra. Similar results are also obtained for the lattice generated by a finite nest and a projection in a finite factor.     

Singularity of full scaling limits of planar nearcritical percolation

We consider full scaling limits of planar nearcritical percolation in the Quad-Crossing-Topology introduced by Schramm and Smirnov. We show that two nearcritical scaling limits with different parameters are singular with respect to each other. The results hold for percolation models on rather general lattices, including bond percolation on the square lattice and site percolation on the triangular lattice.     

Lattice BCK logics with Modus Ponens as unique rule

Lattice BCK logic is the expansion of the well known Meredith implicational logic BCK expanded with lattice conjunction and disjunction. Although its natural axiomatization has three rules named modus ponens, ∨‐rule and ∧‐rule, we show that we can give an equivalent presentation with just modus ponens and ∧‐rule, however it is impossible to obtain an equivalent presentation with modus ponens as unique rule. In this paper we study and characterize all axiomatic extensions of lattice BCK logic with modus ponens as unique rule. We obtain an infinite chain of proper axiomatic extensions with this property. Moreover, we prove that there is no weakest axiomatic extension of Lattice BCK‐logic admitting modus ponens as unique rule.     

Vertex Colouring and Forbidden Subgraphs – A Survey

There is a great variety of colouring concepts and results in the literature. Here our focus is to survey results on vertex colourings of graphs defined in terms of forbidden induced subgraph conditions. Thus, one who wishes to obtain useful results from a graph coloring formulation of his problem must do more than just show that the problem is equivalent to the general problem of coloring a graph. If there is to be any hope, one must also obtain information about the structure of the graphs that need to be colored (D.S. Johnson [66]).Final version received: September 9, 2003     

Percolation on dual lattices with k‐fold symmetry

Zhang found a simple, elegant argument deducing the nonexistence of an infinite open cluster in certain lattice percolation models (for example, p = 1/2 bond percolation on the square lattice) from general results on the uniqueness of an infinite open cluster when it exists; this argument requires some symmetry. Here we show that a simple modification of Zhang's argument requires only two‐fold (or three‐fold) symmetry, proving that the critical probabilities for percolation on dual planar lattices with such symmetry sum to 1. Like Zhang's argument, our extension applies in many contexts; in particular, it enables us to answer a question of Grimmett concerning the anisotropic random cluster model on the triangular lattice. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008