A shuffling theorem for reflectively symmetric tilings

The author and Rohatgi recently proved a ‘shuffling theorem’ for doubly-dented hexagons. In particular, they showed that shuffling removed unit triangles along a horizontal axis in a hexagon changes the tiling number by only a simple multiplicative factor. In this paper, we consider a similar phenomenon for a symmetry class of tilings, namely, the reflectively symmetric tilings. We also prove several shuffling theorems for halved hexagons.     

A short proof for a generalization of Vizing's theorem

For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these results to multigraphs. Instead of considering several color interchanges along alternating chains (Vizing, Gupta), using counting arguments (Ehrenfeucht, Faber, Kierstead), or improving nonvalid colorings with Fournier's Lemma, the method of proof consists of using one single easy transformation, called “sequential recoloring”, to augment a partial k-coloring of the edges.     

On a characterization of spectra and tilings

Lagarias et al. (Duke Math. J. 103 (2000) 25-37) established a characterization of spectra and tilings that can be used to prove a conjecture of Jorgensen and Pedersen (J. Fourier Anal. Appl. 5 (1999) 285-302) by Keller's criterion. Different techniques to prove these facts have also been developed by Iosevich and Pedersen and Kolountzakis. In this expository article, the author presents an elementary approach to obtain a more general form of this characterization that relates spectra and tilings.     

A short proof for the sum formula and its generalization

For positive integers with a _r  = 2, the multiple zeta value or r-fold Euler sum is defined as [2]

A variational principle for domino tilings

We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical tiling of an arbitrary finite region can be described by a function that maximizes an entropy integral. We associate an entropy to every sort of local behavior domino tilings can exhibit, and prove that almost all tilings lie within (for an appropriate metric) of the unique entropy-maximizing solution. This gives a solution to the dimer problem with fully general boundary conditions, thereby resolving an issue first raised by Kasteleyn. Our methods also apply to dimer models on other grids and their associated tiling models, such as tilings of the plane by three orientations of unit lozenges.

     

A short proof of Glivenko theorems for intermediate predicate logics

We give a simple proof-theoretic argument showing that Glivenko’s theorem for propositional logic and its version for predicate logic follow as an easy consequence of the deduction theorem, which also proves some Glivenko type theorems relating intermediate predicate logics between intuitionistic and classical logic. We consider two schemata, the double negation shift (DNS) and the one consisting of instances of the principle of excluded middle for sentences (REM). We prove that both schemata combined derive classical logic, while each one of them provides a strictly weaker intermediate logic, and neither of them is derivable from the other. We show that over every intermediate logic there exists a maximal intermediate logic for which Glivenko’s theorem holds. We deduce as well a characterization of DNS, as the weakest (with respect to derivability) scheme that added to REM derives classical logic.     

On characterizations of spectra and tilings

In a recent paper, Lagarias, Reeds and Wang established a characterization of spectra and tilings that can be used to prove a conjecture of Jorgensen and Pedersen by Keller's criterion. Different techniques to prove these facts have also been developed by Kolountzakis, Iosevich and Pedersen. The primary aim of this paper is to present an elementary method of describing certain characterizations of spectra and tilings. To illustrate this method, we first give a simple proof of this characterization. We then use the method to derive some characteristic results connected with the dual Fuglede's spectral-set conjecture. The results here extend several known conclusions in a simple manner.     

New proof of two Berstein-Hilton theorems

With arguments of Homotopy Theory and without the assumption of finite type, we give short proofs of two classic theorems which deal with the co--type of a suspension and the homotopy class of a suspension map.

     

函数图及函数有向图计数式的组合证明

本文给出了函数有向图计数式的一个简短证明     

A generalization of theorems of Krasnoselskii and Juberg

In this paper, we use the author's diagram proof of Riesz's theorem together with special seminorms to show that two theorems proved by the author generalize a compact interpolation theorem of Krasnoselskii, and a compact interpolation theorem of Juberg.     

A constructive proof of a permutation-based generalization of Sperner's lemma

In a recent paper, Gale has given an interesting generalization of the KKM lemma in combinatorial topology. We present a similar generalization of Sperner's well-known lemma and give a constructive proof. The argument uses the familiar idea of following simplicial paths in a triangulation. To demonstrate that the algorithm must work, orientation considerations are necessary. Gale's generalized KKM lemma is derived from the main result. A permutation-based generalization of Brouwer's fixed point theorem is also given.     

A short proof for the nonvanishing of a character sum

Let χ be an odd residue class character with conductor f (a prime power) and order 2^h. It is shown that the nonvanishing of the sum χ(1) + 2χ(2) + … + fχ(f) follows directly from properties of the minimum polynomial of a 2^hth root of unity.     

A short proof of a theorem of Birkhoff

This paper gives a new proof of a theorem of G. Birkhoff: Every group can be represented as the automorphism group of a distributive lattice D; if is finite, D can be chosen to be finite. The new proof is short, and it is easily visualized. Received November 3, 1995; accepted in final form October 3, 1996.