The graph homomorphism problem is a canonical $NP$-complete problem. It generalizes various other well-studied problems such as graph coloring and finding cliques. To get a better insight into a combinatorial problem, one often studies relaxations of the problem. We define fractional homomorphisms and pseudo-homomorphisms as natural relaxations of graph homomorphisms. ... more >>>

In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coefficients of the characteristic polynomial, in terms of walks and closed walks of different kinds in the underlying graph. We develop algorithms based on ... more >>>

We consider testing graph expansion in the bounded-degree graph model. Specifically, we refer to algorithms for testing whether the graph has a second eigenvalue bounded above by a given threshold or is far from any graph with such (or related) property. We present a natural algorithm aimed towards achieving the ... more >>>

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph $G$ with $n$ vertices are adjacent or not, distinguishes, with high probability, between the case of $G$ satisfying ... more >>>