Search

A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and induced matching numbers are defined as the maximum cardinality of such matchings, respectively, and are known to be NP-hard to compute. In this paper, we study the relationship between these two parameters and the matching number. In particular, we discuss the complexity of two decision problems; first: deciding if the matching number and disconnected matching number are equal; second: deciding if the disconnected matching number and induced matching number are equal. We show that given a bipartite graph with diameter four, deciding if the matching number and disconnected matching number are equal is NP-complete; the same holds for bipartite graphs with maximum degree three. We characterize diameter three graphs with equal matching number and disconnected matching number, which yields a polynomial time recognition algorithm. Afterwards, we show that deciding if the induced and disconnected matching numbers are equal is co-NP-complete for bipartite graphs of diameter 3. When the induced matching number is large enough compared to the maximum degree, we characterize graphs where these parameters are equal, which results in a polynomial time algorithm for bounded degree graphs.

We show that the Banach *-algebra $\ell^1(G,A,\alpha)$, arising from a C*-dynamical system $(A,G,\alpha)$, is an hermitian Banach algebra if the discrete group $G$ is finite or abelian (or more generally, a finite extension of a nilpotent group). As a corollary, we obtain that $\ell^1(\mathbb{Z},C(X),\alpha)$ is hermitian, for every topological dynamical system $\Sigma = (X, \sigma)$, where $\sigma: X\to X$ is a homeomorphism of a compact Hausdorff space $X$ and the action is $\alpha_n(f)=f\circ \sigma^{-n}$ with $n\in\mathbb{Z}$.

We describe Markov interval maps via branching systems and develop the theory of relative branching systems, characterizing when the associated representations of relative graph C*-algebras are faithful. When the Markov interval maps $f$ have escape sets, we use our results to characterize injectivity of the associated relative graph algebra representations, improving on previous work by the first, third, and fourth authors.

A matching $M$ is a $\mathscr{P}$-matching if the subgraph induced by the endpoints of the edges of $M$ satisfies property $\mathscr{P}$. As examples, for appropriate choices of $\mathscr{P}$, the problems Induced Matching, Uniquely Restricted Matching, Connected Matching and Disconnected Matching arise. For many of these problems, finding a maximum $\mathscr{P}$-matching is a knowingly NP-Hard problem, with few exceptions, such as connected matchings, which has the same time complexity as usual Maximum Matching problem. The weighted variant of Maximum Matching has been studied for decades, with many applications, including the well-known Assignment problem. Motivated by this fact, in addition to some recent researches in weighted versions of acyclic and induced matchings, we study the Maximum Weight Connected Matching. In this problem, we want to find a matching $M$ such that the endpoint vertices of its edges induce a connected subgraph and the sum of the edge weights of $M$ is maximum. Unlike the unweighted Connected Matching problem, which is in P for general graphs, we show that Maximum Weight Connected Matching is NP-Hard even for bounded diameter bipartite graphs, starlike graphs, planar bipartite, and bounded degree planar graphs, while solvable in linear time for trees and subcubic graphs. When we restrict edge weights to be non negative only, we show that the problem turns to be polynomially solvable for chordal graphs, while it remains NP-Hard for most of the cases when weights can be negative. Our final contributions are on parameterized complexity. On the positive side, we present a single exponential time algorithm when parameterized by treewidth. In terms of kernelization, we show that, even when restricted to binary weights, Weighted Connected Matching does not admit a polynomial kernel when parameterized by vertex cover under standard complexity-theoretical hypotheses.

In 2005, Goddard, Hedetniemi, Hedetniemi and Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293 (2005) 129 - 138] asked the computational complexity of determining the maximum cardinality of a matching whose vertex set induces a disconnected graph. In this paper we answer this question. In fact, we consider the generalized problem of finding $c$-disconnected matchings; such matchings are ones whose vertex sets induce subgraphs with at least $c$ connected components. We show that, for every fixed $c \geq 2$, this problem is NP-complete even if we restrict the input to bounded diameter bipartite graphs, while can be solved in polynomial time if $c = 1$. For the case when $c$ is part of the input, we show that the problem is NP-complete for chordal graphs, while being solvable in polynomial time for interval graphs. Finally, we explore the parameterized complexity of the problem. We present an FPT algorithm under the treewidth parameterization, and an XP algorithm for graphs with a polynomial number of minimal separators when parameterized by $c$. We complement these results by showing that, unless NP $\subseteq$ coNP/poly, the related Induced Matching problem does not admit a polynomial kernel when parameterized by vertex cover and size of the matching nor when parameterized by vertex deletion distance to clique and size of the matching. As for Connected Matching, we show how to obtain a maximum connected matching in linear time given an arbitrary maximum matching in the input.

Every representation of the Cuntz algebra $\mathcal{O}_n$ leads to a unitary representation of the Higman-Thompson group $V_n$. We consider the family $\{\pi_x\}_{x\in [0,1[}$ of permutative representations of $\mathcal{O}_n$ that arise from the interval map $f(x)=nx$ (mod 1) acting on the Hilbert space that underlies each orbit, and then study the unitary equivalence and the irreducibility of the corresponding family $\{\rho_x\}_{x\in [0,1[}$ of representations of Higman-Thompson group $V_n$, showing that that these representations are indeed irreducible and moreover $\rho_x$ and $\rho_y$ are equivalent if and only if the orbits of $x$ and $y$ coincide., Comment: Introduction expanded

We produce and study a family of representations of relative graph algebras on Hilbert spaces that arise from the orbits of points of one dimensional dynamical systems, where the underlying Markov interval maps $f$ have escape sets. We identify when such representations are faithful in terms of the transitions to the escape subintervals., Comment: A final version will appear in Annals of Functional Analysis

Suppose that $n\geq 1$ and that, for all $i$ and $j$ with $1\leq i,j\leq n$ and $i\neq j$, $z_{ij}\in{\mathbb T}$ are given such that $z_{ji}=\overline{z}_{ij}$ for all $i\neq j$. If $V_1,\dotsc, V_n$ are isometries on a Hilbert space such that $V_i^\ast V_j^{\phantom{\ast}}\!=\overline{z}_{ij} V_j^{\phantom{\ast}}\!V_i^\ast$ for all $i\neq j$, then $(V_1,\dotsc,V_n)$ is called an $n$-tuple of doubly non-commuting isometries. The generators of non-commutative tori are well-known examples. In this paper, we establish a simultaneous Wold decomposition for $(V_1,\dotsc,V_n)$. This decomposition enables us to classify such $n$-tuples up to unitary equivalence. We show that the joint listing of a unitary equivalence class of a representation of each of the $2^n$ non-commutative tori that are naturally associated with the structure constants is a classifying invariant. A dilation theorem is also established, showing that an $n$-tuple of doubly non-commuting isometries can be extended to an $n$-tuple of doubly non-commuting unitary operators on an enveloping Hilbert space., Comment: A remark on the relation between the dilation theorem in this paper and other dilation theorems for multiple operators in the literature has been added. Otherwise, there are only a few minor editorial changes compared to the first version; some typos have also been corrected. Final version, to appear in Advances in Mathematics

We prove that the crossed product Banach algebra $\ell^1(G,A;\alpha)$ that is associated with a ${\mathrm C}^\ast$-dynamical system $(A,G,\alpha)$ is amenable if $G$ is a discrete amenable group and $A$ is a strongly amenable ${\mathrm C}^\ast$-algebra. This is a consequence of the combination of a more general result with Paterson's characterisation of strongly amenable unital $\mathrm{C}^\ast$-algebras in terms of invariant means for their unitary groups., Comment: 19 pages

We prove that the crossed product Banach algebra $\ell^1(A,G,\alpha)$ that is associated with a $\mathrm{C}^\ast$-dynamical system $(A,G,\alpha)$ is amenable if $G$ is a discrete amenable group and $A$ is a commutative or finite dimensional $\mathrm{C}^\ast$-algebra. Perspectives for further developments are indicated., Comment: Improved discussion of the relation with the existing literature and of perspectives for further developments. 8 pages. To appear in Integral Equations and Operator Theory

Given $n\geq 2$, $z_{ij}\in\mathbb{T}$ such that $z_{ij}=\overline z_{ji}$ for $1\leq i,j\leq n$ and $z_{ii}=1$ for $1\leq i\leq n$, and integers $p_1,...,p_n\geq 1$, we show that the universal $\mathrm{C}^*$-algebra generated by unitaries $u_1,...,u_n$ such that $u_i^{p_i}u_j^{p_j}=z_{ij}u_j^{p_j}u_i^{p_i}$ for $1\leq i,j \leq n$ is not simple if at least one exponent $p_i$ is at least two. We indicate how the method of proof by `working with various quotients' can be used to establish nonsimplicity of universal $\mathrm{C}^*$-algebras in other cases., Comment: 3 pages. Small improvements from the first version. Final version, to appear in Annals of Functional Analysis