Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α(G)?n-t, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.     

Permutations avoiding consecutive patterns, II

The generating power series for the number of permutations avoiding particular consecutive patterns are derived in a new and simple fashion.Received: 24 March 2004; revised: 28 July 2004     

C1natural neighbor interpolant for partial differential equations

Natural neighbor coordinates [20] are optimum weighted‐average measures for an irregular arrangement of nodes in ℝⁿ. [26] used the notion of Bézier simplices in natural neighbor coordinates Φ to propose a C¹ interpolant. The C¹ interpolant has quadratic precision in Ω ⊂ ℝ², and reduces to a cubic polynomial between adjacent nodes on the boundary ∂Ω. We present the C¹ formulation and propose a computational methodology for its numerical implementation (Natural Element Method) for the solution of partial differential equations (PDEs). The approach involves the transformation of the original Bernstein basis functions B(Φ) to new shape functions Ψ (Φ), such that the shape functions ψ_3I−2(Φ), ψ_3I−1(Φ), and ψ_3I(Φ) for node I are directly associated with the three nodal degrees of freedom w_I, , respectively. The C¹ shape functions interpolate to nodal function and nodal gradient values, which renders the interpolant amenable to application in a Galerkin scheme for the solution of fourth‐order elliptic PDEs. Results for the biharmonic equation with Dirichlet boundary conditions are presented. The generalized eigenproblem is studied to establish the ellipticity of the discrete biharmonic operator, and consequently the stability of the numerical method. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 417–447, 1999     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs

Let $\Delta =\{{\delta }_1,{\delta }_2,\dots ,{\delta }_m\}$ be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function $D_{\Delta }(z,u_1,u_2,\dots ,u_m),$ which counts polygon dissections and marks subgraph copies of ${\delta }_i$ with the variable $u_i$. We prove that this is always algebraic, through an explicit combinatorial decomposition depending on $\Delta$. The decomposition also gives a defining system for $D_{\Delta }(z,\mathbf{0})$, which encodes polygon dissections that avoid these patterns as subgraphs. In this way, we are able to extract normal limit laws for the patterns when they are encoded, and perform asymptotic enumeration of the resulting classes when they are avoided. The results can be transferred to the case of labelled outerplanar graphs. We give examples and compute the relevant constants when the patterns are small cycles or dissections.     

On avoiding odd partial Latin squares and r-multi Latin squares

We show that for any positive integer k?4, if R is a (2k-1)×(2k-1) partial Latin square, then R is avoidable given that R contains an empty row, thus extending a theorem of Chetwynd and Rhodes. We also present the idea of avoidability in the setting of partial r-multi Latin squares, and give some partial fillings which are avoidable. In particular, we show that if R contains at most nr/2 symbols and if there is an n×n Latin square L such that δn of the symbols in L cover the filled cells in R where 0<δ<1, then R is avoidable provided r is large enough.     

Degrees and matchings

Let n, b, d be positive integers. We evaluate f(n, b, d), the largest possible number of edges in a graph with n vertices having no vertex of degree greater than d and no set of more than b independent edges. Our proof technique has a linear programming flavor and uses Berge's matching formula.     

The probability of avoiding consecutive patterns in the Mallows distribution

We use combinatorial and probabilistic techniques to study growth rates for the probability that a random permutation from the Mallows distribution avoids consecutive patterns. The Mallows distribution is a q‐analogue of the uniform distribution weighting each permutation π by , where is the number of inversions in π and q is a positive, real‐valued parameter. We prove that the growth rate exists for all patterns and all q > 0, and we generalize Goulden and Jackson's cluster method to keep track of the number of inversions in permutations avoiding a given consecutive pattern. Using singularity analysis, we approximate the growth rates for length‐3 patterns, monotone patterns, and non‐overlapping patterns starting with 1, and we compare growth rates between different patterns. We also use Stein's method to show that, under certain assumptions on q and σ, the number of occurrences of a given pattern σ is well approximated by the normal distribution.     

Transversals and multicolored matchings

Ryser conjectured that the number of transversals of a latin square of order n is congruent to n modulo 2. Balasubramanian has shown that the number of transversals of a latin square of even order is even. A 1‐factor of a latin square of order n is a set of n cells no two from the same row or the same column. We prove that for any latin square of order n, the number of 1‐factors with exactly n ? 1 distinct symbols is even. Also we prove that if the complete graph K_2n, n ≥ 8, is edge colored such that each color appears on at most edges, then there exists a multicolored perfect matching. © 2004 Wiley Periodicals, Inc.     

Odd subgraphs and matchings

Let G be a graph and f : V(G)→{1,3,5,…}. Then a subgraph H of G is called a (1,f)-odd subgraph if deg_H(x){1,3,…,f(x)} for all xV(H). If f(x)=1 for all xV(G), then a (1,f)-odd subgraph is nothing but a matching. A (1,f)-odd subgraph H of G is said to be maximum if G has no (1,f)-odd subgraph K such that |K|>|H|. We show that (1,f)-odd subgraphs have some properties similar to those of matchings, in particular, we give a formula for the order of a maximum (1,f)-odd subgraph, which is similar to that for the order of a maximum matching.     

Distance edge-colourings and matchings

We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erd?s–Rényi random graphs. We work in three settings. The first is that of a distance generalisation of an Erd?s–Ne?et?il problem. The second is that of an upper bound on the size of a largest distance matching in a random graph. The third is that of an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupień.     

Cycles and perfect matchings

Fan Chung and Ron Graham (J. Combin. Theory Ser. B 65 (1995) 273–290) introduced the cover polynomial for a directed graph and showed that it was connected with classical rook theory. Dworkin (J. Combin. Theory Ser. B 71 (1997) 17–53) showed that the cover polynomial naturally factors for directed graphs associated with Ferrers boards. The authors (Adv. Appl. Math. 27 (2001) 438–481) developed a rook theory for shifted Ferrers boards where the analogue of a rook placement is replaced by a partial perfect matching of K_2n, the complete graph on 2n vertices. In this paper, we show that an analogue of Dworkin's result holds for shifted Ferrers boards in this setting. We also show how cycle-counting matching numbers are connected to cycle-counting “hit numbers” (which involve perfect matchings of K_2n).     

On distance edge-colourings and matchings

We consider a distance generalisation of the strong chromatic index and the maximum induced matching number, for graphs of bounded maximum degree and Erdős-Rényi random graphs.     

Special matchings and Kazhdan-Lusztig polynomials

In 1979 Kazhdan and Lusztig defined, for every Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W, and which have proven to be of importance in several areas of mathematics. In this paper, we show that the combinatorial concept of a special matching plays a fundamental role in the computation of these polynomials. Our results also imply, and generalize, the recent one in [Adv. in Math. 180 (2003) 146-175] on the combinatorial invariance of Kazhdan-Lusztig polynomials.