The number of perfect matchings of a k-pfaffian graph can be counted by computing a linear combination of the pfaffians of k matrices. The pfaffian number of a graph G is the smallest integer k such that G is k-pfaffian. We present the first known lower bounds for the pfaffian number of graphs. As an intermediate step, we prove an upper bound for the rank of two matrices related to their Khatri-Rao product. One of the consequences of the found lower bounds is the existence of graphs whose pfaffian numbers are arbitrarily large.

A cut $C:=\partial(X)$ of a matching covered graph $G$ is a separating cut if both its $C$-contractions $G/X$ and $G/\overline{X}$ are also matching covered. A brick is solid if it is free of nontrivial separating cuts. In 2004, we (Carvalho, Lucchesi and Murty) showed that the perfect matching polytope of a brick may be described without recourse to odd set constraints if and only if it is solid. In 2006, we proved that the only simple planar solid bricks are the odd wheels. The problem of characterizing nonplanar solid bricks remains unsolved. A bi-subdivision of a graph $J$ is a graph obtained from $J$ by replacing each of its edges by paths of odd length. A matching covered graph $J$ is a conformal minor of a matching covered graph $G$ if there exists a bi-subdivision $H$ of $J$ which is a subgraph of $G$ such that $G-V(H)$ has a perfect matching. For a fixed matching covered graph $J$, a matching covered graph $G$ is $J$-based if $J$ is a conformal minor of $G$ and, otherwise, $G$ is $J$-free. A basic result due to Lovász (1983) states that every nonbipartite matching covered graph is either $K_4$-based or is $\overline{C_6}$-based or both, where $\overline{C_6}$ is the triangular prism. In 2016, we (Kothari and Murty) showed that, for any cubic brick $J$, a matching covered graph $G$ is $J$-free if and only if each of its bricks is $J$-free. We also found characterizations of planar bricks which are $K_4$-free and those which are $\overline{C_6}$-free. Each of these problems remains unsolved in the nonplanar case. In this paper we show that the seemingly unrelated problems of characterizing nonplanar solid bricks and of characterizing nonplanar $\overline{C_6}$-free bricks are essentially the same. We do this by establishing that a simple nonplanar brick, other than the Petersen graph, is solid if and only if it is $\overline{C_6}$-free.

In this paper we show that, with 11 exceptions, any matching covered bipartite graph on $n$ vertices, with minimum degree greater than two, has at least $2n-4$ perfect matchings. Using this bound, which is the best possible, and McCuaig's theorem [W. McCuaig, J. Graph Theory, 38 (2001), pp. 124--169] on brace generation, we show that any brace on $n$ vertices has at least $(n-2)^2/8$ perfect matchings. A bi-wheel on $n$ vertices has $(n-2)^2/4$ perfect matchings. We conjecture that there exists an integer $N$ such that every brace on $n\geq N$ vertices has at least $(n-2)^2/4$ perfect matchings.

Abstract The construction of minimal acyclic deterministic partial finite automata to represent large natural language vocabularies is described. Applications of such automata include spelling checkers and advisers, multilanguage dictionaries, thesauri, minimal perfect hashing and text compression.