David Galvin

most citedCounting colorings of a regular graph

3 citations · 3 across the 14 of their papers we have counts for

collaborators

Showing math.COShow all

12 papers · 1 filter

math.CO2012

Stirling numbers of forests and cycles

Do Trong Thanh, David Galvin

For a graph $G$ and a positive integer $k$ , the {\em graphical Stirling number} $S (G, k)$ is the number of partitions of the vertex set of $G$ into $k$ non-empty independent sets. E…

math.CO2012

Matchings and Independent Sets of a Fixed Size in Regular Graphs

Teena Carroll, David Galvin, Prasad Tetali

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size $ℓ$ in a $d$ -regular graph on $N$ vertices. For $\f…

math.CO2012

Two problems on independent sets in graphs

David Galvin

Let $i_{t} (G)$ denote the number of independent sets of size $t$ in a graph $G$ . Levit and Mandrescu have conjectured that for all bipartite $G$ the sequence $(i_{t} (G))_{t \geq 0}$ (t…

math.CO2012

Sampling 3-colourings of regular bipartite graphs

David Galvin

We show that if $\gS=(V,E)$ is a regular bipartite graph for which the expansion of subsets of a single parity of $V$ is reasonably good and which satisfies a certain local conditi…

math.CO2012

Bounding the partition function of spin-systems

David Galvin

With a graph $G = (V, E)$ we associate a collection of non-negative real weights $\cup_{v \in V} λ_{i, v} : 1 \leq i \leq m \cup \cup_{uv \in E} λ_{ij, uv} : 1 \leq i \leq j \leq m$ . We con…

math.CO2012

Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus

David Galvin, Dana Randall

We study local Markov chains for sampling 3-colorings of the discrete torus $T_{L, d} = 0, ..., L - 1^{d}$ . We show that there is a constant $ρ \approx .22$ such that for all even $L \geq…