Perfect matchings and the octahedron recurrence

We study a recurrence defined on a three dimensional lattice and prove that its values are Laurent polynomials in the initial conditions with all coefficients equal to one. This recurrence was studied by Propp and by Fomin and Zelivinsky. Fomin and Zelivinsky were able to prove Laurentness and conjectured that the coefficients were 1. Our proof establishes a bijection between the terms of the Laurent polynomial and the perfect matchings of certain graphs, generalizing the theory of Aztec Diamonds. In particular, this shows that the coefficients of this polynomial, and polynomials obtained by specializing its variables, are positive, a conjecture of Fomin and Zelevinsky.     

The multidimensional cube recurrence

We introduce a recurrence which we term the multidimensional cube recurrence, generalizing the octahedron recurrence studied by Propp, Fomin and Zelevinsky, Speyer, and Fock and Goncharov and the three-dimensional cube recurrence studied by Fomin and Zelevinsky, and Carroll and Speyer. The states of this recurrence are indexed by tilings of a polygon with rhombi, and the variables in the recurrence are indexed by vertices of these tilings. We travel from one state of the recurrence to another by performing elementary flips. We show that the values of the recurrence are independent of the order in which we perform the flips; this proof involves nontrivial combinatorial results about rhombus tilings which may be of independent interest. We then show that the multidimensional cube recurrence exhibits the Laurent phenomenon - any variable is given by a Laurent polynomial in the other variables. We recognize a special case of the multidimensional cube recurrence as giving explicit equations for the isotropic Grassmannians IG(n−1,2n). Finally, we describe a tropical version of the multidimensional cube recurrence and show that, like the tropical octahedron recurrence, it propagates certain linear inequalities.     

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.     

On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M₁ and M₂ be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M₁ and M₂ intersect at most |M₁|+|M₂|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. Supported by PAPIIT(UNAM) of México, Proyecto IN110802 Supported by FAI-UASLP and by CONACYT of México, Proyecto 32168-E Supported by CONACYT of México, Proyecto 37540-A     

An excluded minor theorem for the octahedron

In this article it is shown that every 4‐connected graph that does not contain a minor isomorphic to the octahedron is isomorphic to the square of an odd cycle. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 95–100, 1999     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.     

A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs

Let $G$ be a balanced bipartite graph of order $2n\ge 4$, and let ${\sigma }_{1,1}\left(G\right)$ be the minimum degree sum of two non-adjacent vertices in different partite sets of $G$. In 1963, Moon and Moser proved that if ${\sigma }_{1,1}\left(G\right)\ge n+1$, then $G$ is hamiltonian. In this note, we show that if $k$ is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly $k$ cycles for sufficiently large graphs. In order to prove this, we also give a ${\sigma }_{1,1}$ condition for the existence of $k$ vertex-disjoint alternating cycles with respect to a chosen perfect matching in $G$.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

Dimers, tilings and trees

Generalizing results of Temperley (London Mathematical Society Lecture Notes Series 13 (1974) 202), Brooks et al. (Duke Math. J. 7 (1940) 312) and others (Electron. J. Combin. 7 (2000); Israel J. Math. 105 (1998) 61) we describe a natural equivalence between three planar objects: weighted bipartite planar graphs; planar Markov chains; and tilings with convex polygons. This equivalence provides a measure-preserving bijection between dimer coverings of a weighted bipartite planar graph and spanning trees of the corresponding Markov chain. The tilings correspond to harmonic functions on the Markov chain and to “discrete analytic functions” on the bipartite graph.The equivalence is extended to infinite periodic graphs, and we classify the resulting “almost periodic” tilings and harmonic functions.     

A Gallai–Edmonds‐type structure theorem for path‐matchings

As a generalization of matchings, Cunningham and Geelen introduced the notion of path‐matchings. We give a structure theorem for path‐matchings which generalizes the fundamental Gallai–Edmonds structure theorem for matchings. Our proof is purely combinatorial. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 93–102, 2004     

Parametrizing the abstract Ellentuck theorem

We give a parametrization with perfect subsets of 2^∞ of the abstract Ellentuck theorem (see [T.J. Carlson, S.G. Simpson, Topological Ramsey Theory, in: J. Ne?etrˆil, V. Rödl (Eds.), Mathematics of Ramsey Theory, Algorithms and Combinatorics, vol. 5, Springer, Berlin, 1990, pp. 172-183], [S. Todorcevic, Introduction to Ramsey spaces, to appear] or [S. Todorcevic, Lecture notes from a course given at the Fields Institute in Toronto, Canada, Autumn 2002]). The main tool for achieving this goal is a sort of parametrization of an abstract version of the Nash-Williams theorem. As corollaries, we obtain some known classical results like the parametrized version of the Galvin-Prikry theorem due to Miller and Todorcevic [A.W. Miller, Infinite combinatorics and definability, Ann. Pure Appl. Logic 41 (1989) 179-203], and the parametrized version of Ellentuck's theorem due to Pawlikowski [Parametrized Ellentuck theorem, Topology Appl. 37 (1990) 65-73]. Also, we obtain parametized vesions of nonclassical results such as Milliken's theorem [K.R. Milliken, Ramsey's theorem with sums or unions, J. Combin. Theory (A) 18 (1975) 276-290], and we prove that the family of perfectly Ramsey subsets of is closed under the Souslin operation.     

Using graphs for some discrete tomography problems

Given a rectangular array whose entries represent the pixels of a digitalized image, we consider the problem of reconstructing an image from the number of occurrences of each color in every column and in every row. The complexity of this problem is still open when there are just three colors in the image. We study some special cases where the number of occurrences of each color is limited to small values. Formulations in terms of edge coloring in graphs and as timetabling problems are used; complexity results are derived from the model.     

The octahedron theorem in Minkowski three-space a metric vector space proof of Miquel's theorem in the Laguerre plane

As is well known [1, p.480], the cycles and spears of the real Laguerre plane can be represented by the points and null planes of three-dimensional Minkowski space. Miquel's theorem in the Laguerre plane can then be expressed as an intrinsically interesting Minkowski space theorem the octahedron theorem. We outline the correspondence between the two theorems, and then give a metric vector space proof of the octahedron theorem, thereby providing an alternate proof of Miquel's theorem. We then discuss the generalization of both theorems to more general spaces.     

Weak almost periodicity and the strong ergodic limit theorem for contraction semigroups

We show that if (S(t)) _t≧0 is a contraction semigroup on a closed convex subset of a uniformly convex Banach space, then every bounded and “asymptotically isometric” almost-orbit of (S(t)) _t≧0 is weakly almost periodic in the sense of Eberlein. As one consequence, results on the existence of almost periodic solutions to the abstract Cauchy problem are obtained without the need fora priori compactness assumptions. As a further consequence, the known strong ergodic limit theorems for (almost-) orbits of nonlinear contraction semigroups turn out to be special cases of Eberlein’s classical ergodic theorem for weakly almost periodic functions.     

一个求解二项式系数幂和序列递推公式的方法

根据同余理论并利用二项式系数幂和序列在模p下具有周期性的事实,提出一种求解递推公式的方法,从理论上证明其可行性.使得求解和验证二项式系数幂和序列递推公式具有完备的理论基础.     

A multidimensional continued fraction based on a high-order recurrence relation

The paper describes and studies an iterative algorithm for finding small values of a set of linear forms over vectors of integers. The algorithm uses a linear recurrence relation to generate a vector sequence, the basic idea being to choose the integral coefficients in the recurrence relation in such a way that the linear forms take small values, subject to the requirement that the integers should not become too large. The problem of choosing good coefficients for the recurrence relation is thus related to the problem of finding a good approximation of a given vector by a vector in a certain one-parameter family of lattices; the novel feature of our approach is that practical formulae for the coefficients are obtained by considering the limit as the parameter tends to zero. The paper discusses two rounding procedures to solve the underlying inhomogeneous Diophantine approximation problem: the first, which we call ``naive rounding' leads to a multidimensional continued fraction algorithm with suboptimal asymptotic convergence properties; in particular, when it is applied to the familiar problem of simultaneous rational approximation, the algorithm reduces to the classical Jacobi-Perron algorithm. The second rounding procedure is Babai's nearest-plane procedure. We compare the two rounding procedures numerically; our experiments suggest that the multidimensional continued fraction corresponding to nearest-plane rounding converges at an optimal asymptotic rate.