Given $R subseteq mathbb{N}$ let ${n brace k}_R$, ${n brack k}_R$, and $L(n,k)_R$ be the number of ways of partitioning the set $[n]$ into $k$ non-empty subsets, cycles and lists, respectively, with each block having cardinality in $R$. We refer to t
hese as the $R$-restricted Stirling numbers of the second and first kind and the $R$-restricted Lah numbers, respectively. Note that the classical Stirling numbers of the second kind and first kind, and Lah numbers are ${n brace k} = {n brace k}_{mathbb{N}}$, ${n brack k} = {n brack k}_{mathbb{N}} $ and $L(n,k) = L(n,k)_{mathbb{N}}$, respectively. The matrices $[{n brace k}]_{n,k geq 1}$, $[{n brack k}]_{n,k geq 1}$ and $[L(n,k)]_{n,k geq 1}$ have inverses $[(-1)^{n-k}{n brack k}]_{n,k geq 1}$, $[(-1)^{n-k} {n brace k}]_{n,k geq 1}$ and $[(-1)^{n-k} L(n,k)]_{n,k geq 1}$ respectively. The inverse matrices $[{n brace k}_R]^{-1}_{n,k geq 1}$, $[{n brack k}_R]^{-1}_{n,k geq 1}$ and $[L(n,k)_R]^{-1}_{n,k geq 1}$ exist if and only if $1 in R$. We express each entry of each of these matrices as the difference between the cardinalities of two explicitly defined families of labeled forests. In particular the entries of $[{n brace k}_{[r]}]^{-1}_{n,k geq 1}$ have combinatorial interpretations, affirmatively answering a question of Choi, Long, Ng and Smith from 2006. If $1,2 in R$ and if for all $n in R$ with $n$ odd and $n geq 3$, we have $n pm 1 in R$, we additionally show that each entry of $[{n brace k}_R]^{-1}_{n,k geq 1}$, $[{n brack k}_R]^{-1}_{n,k geq 1}$ and $[L(n,k)_R]^{-1}_{n,k geq 1}$ is up to an explicit sign the cardinality of a single explicitly defined family of labeled forests. Our results also provide combinatorial interpretations of the $k$th Whitney numbers of the first and second kinds of $Pi_n^{1,d}$, the poset of partitions of $[n]$ that have each part size congruent to $1$ mod $d$.
A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph $G$ is the maximum density of an independent set in $G$. Lih, Liu,
and Zhu [Star extremal circulant graphs, SIAM J. Discrete Math. 12 (1999) 491--499] showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs. We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three, determine asymptotic values for others, and present several conjectures.
In the hard-core model on a finite graph we are given a parameter lambda>0, and an independent set I arises with probability proportional to lambda^|I|. On infinite graphs a Gibbs distribution is defined as a suitable limit with the correct condition
al probabilities. In the infinite setting we are interested in determining when this limit is unique and when there is phase coexistence, i.e., existence of multiple Gibbs states. On finite graphs we are interested in determining the mixing time of local Markov chains. On Z^2 it is conjectured that these problems are related and that both undergo a phase transition at some critical point lambda_c approx 3.79. For phase coexistence, much of the work to date has focused on the regime of uniqueness, with the best result being recent work of Restrepo et al. showing that there is a unique Gibbs state for all lambda < 2.3882. Here we give the first non-trivial result in the other direction, showing that there are multiple Gibbs states for all lambda > 5.3646. Our proof adds two significant innovations to the standard Peierls argument. First, building on the idea of fault lines introduced by Randall, we construct an event that distinguishes two boundary conditions and always has long contours associated with it, obviating the need to accurately enumerate short contours. Second, we obtain vastly improved bounds on the number of contours by relating them to a new class of self-avoiding walks on an oriented version of Z^2. We extend our characterization of fault lines to show that local Markov chains will mix slowly when lambda > 5.3646 on lattice regions with periodic (toroidal) boundary conditions and when lambda > 7.1031 with non-periodic (free) boundary conditions. The arguments here rely on a careful analysis that relates contours to taxi walks and represent a sevenfold improvement to the previously best known values of lambda.
