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 ... 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
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 ... 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 >>>

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to an agreed communication protocol, and the players must decide,
deterministically, if their inputs ... more >>>