David Galvin
H-coloring tori.
Thu, 01/06/2011 - 16:01 — SomNambulAuthors: David Galvin, John Engbers
Subjects: Combinatorics
AbstractFor graphs $G$ and $H$, an $H$-coloring of $G$ is a function from the
vertices of $G$ to the vertices of $H$ that preserves adjacency. $H$-colorings
encode graph theory notions such as independent sets and proper colorings, and
are a natural setting for the study of hard-constraint models in statistical
physics.H-colouring bipartite graphs.
Thu, 01/06/2011 - 16:01 — SomNambulAuthors: David Galvin, John Engbers
Subjects: Combinatorics
AbstractFor graphs $G$ and $H$, an {\em $H$-colouring} of $G$ (or {\em homomorphism}
from $G$ to $H$) is a function from the vertices of $G$ to the vertices of $H$
that preserves adjacency. $H$-colourings generalize such graph theory notions
as proper colourings and independent sets.Sampling independent sets in the discrete torus.
Thu, 07/29/2010 - 15:01 — SomNambulAuthors: David Galvin
Subjects: Combinatorics
AbstractThe even discrete torus is the graph T_{L,d} on vertex set {0,...,L-1}^d (L
even) with two vertices adjacent if they differ by 1 (mod L) on one coordinate.
The hard-core measure with activity x on T_{L,d} is the distribution pi_x on
the independent sets (sets of vertices spanning no edges) of T_{L,d} in which a
set I is chosen with probability proportional to x^|I|. This distribution
occurs in problems from statistical physics and communication networks.An upper bound for the number of independent sets in regular graphs.
Thu, 07/29/2010 - 15:01 — SomNambulAuthors: David Galvin
Subjects: Combinatorics
AbstractWrite ${\cal I}(G)$ for the set of independent sets of a graph $G$ and $i(G)$
for $|{\cal I}(G)|$. It has been conjectured (by Alon and Kahn) that for an
$N$-vertex, $d$-regular graph $G$, $$ i(G) \leq \left(2^{d+1}-1\right)^{N/2d}.
$$ If true, this bound would be tight, being achieved by the disjoint union of
$N/2d$ copies of $K_{d,d}$.
User login
