We present a new approach to a classical problem in statistical physics: estimating the partition function and other thermodynamic quantities of the ferromagnetic Ising model. Markov chain Monte Carlo methods for this problem have been well-studied,
although an algorithm that is truly practical remains elusive. Our approach takes advantage of the fact that, for a fixed bond strength, studying the ferromagnetic Ising model is a question of counting particular subgraphs of a given graph. We combine graph theory and heuristic sampling to determine coefficients that are independent of temperature and that, once obtained, can be used to determine the partition function and to compute physical quantities such as mean energy, mean magnetic moment, specific heat, and magnetic susceptibility.
For positive integers $w$ and $k$, two vectors $A$ and $B$ from $mathbb{Z}^w$ are called $k$-crossing if there are two coordinates $i$ and $j$ such that $A[i]-B[i]geq k$ and $B[j]-A[j]geq k$. What is the maximum size of a family of pairwise $1$-cross
ing and pairwise non-$k$-crossing vectors in $mathbb{Z}^w$? We state a conjecture that the answer is $k^{w-1}$. We prove the conjecture for $wleq 3$ and provide weaker upper bounds for $wgeq 4$. Also, for all $k$ and $w$, we construct several quite different examples of families of desired size $k^{w-1}$. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.
We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list.
Let $K$ be a field and $S=K[x_1,...,x_n]$. In 1982, Stanley defined what is now called the Stanley depth of an $S$-module $M$, denoted $sdepth(M)$, and conjectured that $depth(M) le sdepth(M)$ for all finitely generated $S$-modules $M$. This conjectu
re remains open for most cases. However, Herzog, Vladoiu and Zheng recently proposed a method of attack in the case when $M = I / J$ with $J subset I$ being monomial $S$-ideals. Specifically, their method associates $M$ with a partially ordered set. In this paper we take advantage of this association by using combinatorial tools to analyze squarefree Veronese ideals in $S$. In particular, if $I_{n,d}$ is the squarefree Veronese ideal generated by all squarefree monomials of degree $d$, we show that if $1le dle n < 5d+4$, then $sdepth(I_{n,d})= floor{binom{n}{d+1}Big/binom{n}{d}}+d$, and if $dgeq 1$ and $nge 5d+4$, then $d+3le sdepth(I_{n,d}) le floor{binom{n}{d+1}Big/binom{n}{d}}+d$.
