Dimension and enumeration of primitive ideals in quantum algebras

In this paper, we study the primitive ideals of quantum algebras supporting a rational torus action. We first prove a quantum analogue of a Theorem of Dixmier; namely, we show that the Gelfand-Kirillov dimension of primitive factors of various quantum algebras is always even. Next we give a combinatorial criterion for a prime ideal that is invariant under the torus action to be primitive. We use this criterion to obtain a formula for the number of primitive ideals in the algebra of 2×n quantum matrices that are invariant under the action of the torus. Roughly speaking, this can be thought of as giving an enumeration of the points that are invariant under the induced action of the torus in the “variety of 2×n quantum matrices”. The first author thanks NSERC for its generous support. This research was supported by a Marie Curie Intra-European Fellowship within the 6th European Community Framework Programme held at the University of Edinburgh, by a Marie Curie European Reintegration Grant within the 7th European Community Framework Programme and by Leverhulme Research Interchange Grant F/00158/X.     

On decompositions of leapfrog fullerenes

It is shown that given a fullerene F with the number of vertices n divisible by 4, and such that no two pentagons in F share an edge, the corresponding leapfrog fullerene Le(F) contains a long cycle of length 3n − 6 missing out only one hexagon.     

Orthogonally Resolvable Matching Designs

An orthogonally resolvable matching design OMD$(n,k)$ is a partition of the edges of the complete graph $K_n$ into matchings of size $k$, called blocks, such that the blocks can be resolved in two different ways. Such a design can be represented as a square array whose cells are either empty or contain a matching of size $k$, where every vertex appears exactly once in each row and column. In this paper we show that an OMD$(n,k)$ exists if and only if $n\equiv 0(mod2k)$ except when $k=1$ and $n=4$ or $6$.     

Degree Conditions for Matchability in 3‐Partite Hypergraphs

We study conjectures relating degree conditions in 3‐partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko [14] (as generalized by the first two authors [2]), that every family of $2n-1$ matchings of size n in a bipartite graph has a partial rainbow matching of size n. We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless [11], that every $n\times n$ Latin square has a generalized diagonal (set of n entries, each in a different row and column) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row‐Latin.     

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.     

Maximal Induced Matchings in Triangle‐Free Graphs

An induced matching in a graph is a set of edges whose endpoints induce a 1‐regular subgraph. It is known that every n‐vertex graph has at most  maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most  maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3, 3}. Our result implies that all maximal induced matchings in an n‐vertex triangle‐free graph can be listed in time , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.     

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