Note on the path‐matching formula

As a common generalization of matchings and matroid intersections, W.H. Cunningham and J.F. Geelen introduced the notion of path‐matchings. They proved a min‐max formula for the maximum value. Here, we exhibit a simplified version of their min‐max theorem and provide a purely combinatorial proof. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 110–119, 2002     

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.     

Matching radiation-dominated and matter-dominated Einstein–de Sitter universes and an application for primordial black holes in evolving cosmological backgrounds

By matching across a surface of constant time, it is demonstrated that the spacetime for a radiation-dominated Einstein–de Sitter universe can be directly matched to the spacetime for a matter-dominated Einstein–de Sitter universe. Thus, this can serve as a model of a universe filled with radiation that suddenly is converted to matter and antimatter, or a universe filled with matter and antimatter that suddenly annihilates to leave radiation. This matching is shown to hold for asymptotically Einstein–de Sitter cosmological black hole spacetimes, yielding simplistic models of primordial black holes that evolve between being in radiation-dominated universes and matter-dominated universes.     

Algebraic and combinatorial properties of zircons

In this paper we introduce and study a new class of posets, that we call zircons, which includes all Coxeter groups partially ordered by Bruhat order. We prove that many of the properties of Coxeter groups extend to zircons often with simpler proofs: in particular, zircons are Eulerian posets and the Kazhdan-Lusztig construction of the Kazhdan-Lusztig representations can be carried out in the context of zircons. Moreover, for any zircon Z, we construct and count all balanced and exact labelings (used in the construction of the Bernstein-Gelfand-Gelfand resolutions in the case that Z is the Weyl group of a Kac-Moody algebra). Partially supported by the program “Gruppi di trasformazioni e applicazioni”, University of Rome “La Sapienza”. Part of this research was carried out while the author was a member of the Institut Mittag-Leffler of the Royal Swedish Academy of Sciences.     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Enumeration of Lozenge Tilings of Hexagons with Cut-Off Corners

Motivated by the enumeration of a class of plane partitions studied by Proctor and by considerations about symmetry classes of plane partitions, we consider the problem of enumerating lozenge tilings of a hexagon with “maximal staircases” removed from some of its vertices. The case of one vertex corresponds to Proctor's problem. For two vertices there are several cases to consider, and most of them lead to nice enumeration formulas. For three or more vertices there do not seem to exist nice product formulas in general, but in one special situation a lot of factorization occurs, and we pose the problem of finding a formula for the number of tilings in this case.     

关于3正则图的三匹配交猜想（I）

Fan和Raspaud1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配。本研究一类特殊的无桥3正则图G：存在图的G的一个完美匹配M1使得G－M1恰含有两个奇圈和若干偶圈。在偶圈数≤2的情形以及在偶圈数≤4且G是圈4－边连通的情形，本证明了一定存在图G的两个完善匹配M2和M3使得M1∩M2∩M3＝φ。     

Complete matchings in random subgraphs of the cube

In this article it is shown that for almost every random cube process the hitting time of a complete matching equals the hitting time of having minimal degree (at least) one and also the hitting time of connectedness. It follows from this that if t = (n + c + o(1))2^n?2 for some constant c, then the probability that a random subgraph of the n-cube having precisely t edges has a complete matching tends to e.     

Minimum costK-forest covers

A forest cover of a graph is a spanning forest for which each component has at least two nodes. IfK is a subset of nodes, aK-forest cover is a forest cover including exactly one node fromK in each component. AK-forest cover is of minimum cost if the sum of the costs of the edges is minimum. We present an0(n ² + ¦K¦² n) algorithm for determining the minimum costK-forest cover of a graph withn nodes. We show that the algorithm can also be used to determine, in0(n ² + ({K — K'¦ + _{deK'd v} )² _n ) time, the minimum costK-forest cover having degree equald _v each nodev of an arbitrary subsetK' ofK.     

Rainbow matchings and Hamilton cycles in random graphs

Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016