text:
# Heat Conduction in One-Dimensional chain of Hard Discs with Substrate Potential

## 1 Introduction

Heat conductivity in one-dimensional (1D) lattices is a well known classical problem related to the microscopic foundation of Fourier’s law. The problem started from the famous work of Fermi, Pasta, and Ulam (FPU) , where an abnormal process of heat transfer was detected for the first time. Non-integrability of a system is a necessary condition for normal heat conductivity. As it was demonstrated recently for the FPU lattice , disordered harmonic chain , diatomic 1D gas of colliding particles , and the diatomic Toda lattice , non-integrability is not sufficient in order to get normal heat conductivity. It leads to linear distribution of temperature along the chain for small gradient, but the value of heat flux is proportional to $`1/N^\alpha `$, where $`N`$ is the number of particles of the chain, and number exponent $`0<\alpha <1`$. Thus, the coefficient of heat conductivity diverges in the thermodynamic limit $`N\mathrm{}`$. Analytical estimations  have demonstrated that any chain possessing an acoustic phonon branch should have infinite heat conductivity in the limit of low temperatures.

From the other side, there are some artificial systems with on-site potential (ding-a-ling and related models) which have normal heat conductivity . The heat conductivity of the Frenkel-Kontorova chain was first considered in Ref. . Finite heat conductivity for certain parameters was observed for Frenkel-Kontorova chain , for the chain with sinh-Gordon on-site potential , and for the chain with $`\varphi ^4`$ on-site potential . These models are not invariant with respect to translation and the momentum is not conserved. It was supposed that the on-site potential is extremely significant for normal heat conduction  and that the anharmonicity of the on-site potential is sufficient to ensure the validity of Fourier’s law . A recent detailed review of the problem is presented in Ref. .

Probably the most interesting question related to heat conductivity of 1D models (which actually inspired the first investigation of Fermi, Pasta and Ulam ) is whether small perturbation of an integrable model will lead to convergent heat conduction coefficient. One supposes that for the one-dimensional chains with conserved momentum the answer is negative . Still, normal heat conduction has been observed in some special systems with conserved momentum , but it may be clearly demonstrated only well apart from integrable limit.

The situation is not so clear in the systems with on-site potential. Although it was supposed that non-integrable system without additional integrals of motion would have convergent heat conductivity , no rigorous proof was presented. From the other side, recent attempt of numerical simulation of heat transfer in Frenkel-Kontorova model  demonstrated that because of computational difficulties no unambiguous conclusion can be drawn whether heat conduction is convergent for all finite values of perturbation of the integrable limit system (linear chain or continuous sine-Gordon system).

It seems that computational difficulties of investigation of heat conduction in a vicinity of integrable limit are not just issue of weak computers or ineffective procedures. In the systems with conserved momentum divergent heat conduction is fixed by power-like decrease of heat flux autocorrelation function with power less than unity. Still, for the systems with on-site potential exponential decrease is more typical . For any fixed value of the exponent the heat conduction converges; if the exponent tends to zero with the value of the perturbation of the integrable case, then for any finite value of the perturbation the characteristic correlation time and length will be finite but may become very large. Consequently, they will exceed any available computation time or size of the system and still no conclusion on the convergence of heat conduction will be possible.

In this respect it is reasonable to mention the findings of our papers  concerning the transitions from infinite to finite heat conduction in the chain of rotators and Frenkel - Kontorova system. These findings were criticized in paper  by providing the computation results for larger systems. We agree with the authors that the results of papers  do not prove the reality of the above transition. In fact, we have pointed it out in . From the other side, it is clear that such more extended numerical simulations cannot prove that the transitions do not exist at all. Probably, such conclusion may be driven if, with the help of some not yet developed method, the simulation length or effective time will be extended by many orders of magnitude.

The other way to overcome this difficulty is to construct a model, which will be, at least to some extent, tractable analytically and will allow one to predict some characteristic features of the heat transfer process and the behavior of the heat conduction coefficient. Afterwards the numerical simulation may be used to verify the assumptions made in the analytic treatment. To the best of our knowledge, no models besides pure harmonic chains were treated in such a way to date. Introduction and investigation of a nontrivial model of this sort is a scope of present paper.

We are going to demonstrate that there exist models which have integrable system as their natural limit case, small perturbation of the integrability immediately leading to convergent heat conduction. The mechanism of energy scattering in this kind of systems is universal for any temperature and set of the model parameters. The simplest example of such model is one-dimensional set of equal rigid particles with nonzero diameter $`(d>0)`$ subjected to periodic on-site potential. This system is completely integrable only if $`d=0`$. It will be demonstrated that any $`d>0`$ leads to effective mixing due to unequal exchange of energy between the particles in each collision. This mixing leads to diffusive mechanism of the heat transport and, subsequently, to convergent heat conduction.

## 2 Description of the model

Let us consider the one-dimensional system of hard particles with equal masses subject to periodic on-site potential. The Hamiltonian of this system will read

$$=\underset{n}{}\{\frac{1}{2}M\dot{x}_n^2+V(x_{n+1}x_n)+U(x_n)\},$$
(1)
where $`M`$ – mass of the particle, $`x_n`$ – coordinate of the center of the $`n`$-th particle, $`\dot{x}_n`$ – velocity of this particle, $`U(x)`$ – periodic on-site potential with period $`a`$ $`[U(x)U(x+a)]`$. Interaction of absolutely hard particles is described by the following potential

$$V(r)=\mathrm{}\text{if}rd\text{and}V(r)=0\text{if}r>d,$$
(2)
where $`d`$ is the diameter of the particle. This potential corresponds to pure elastic impact with unit recovery coefficient. Sketch of the model considered is presented at Fig. 1.

It is well-known that the elastic collision of two equal particles with collinear velocity vectors leads to exchange of their velocities. An external potential present does not change this fact, since the collision takes zero time and thus the effect of the external force on the energy and momentum conservation is absent.

The one-dimensional chain of equivalent hard particles without external potential is a paradigm of the integrable nonlinear chain, since all interactions are reduced to exchange of velocities. In other words, the individual values of velocities are preserved and just transferred from particle to particle. It is natural therefore to introduce quasiparticles associated with these individual values of velocities. They will be characterized by a pair of parameters $`(E_k,𝐧_k)`$, where $`E_k=v_k^2/2`$ is an energy of the quasiparticle, $`𝐧_k`$ is a unit vector in a direction of its motion. Every particle in every moment ”carries” one quasiparticle. The elastic collision between the particles leads to simple exchange of parameters of the associated quasiparticles, therefore the quasiparticles themselves should be considered as non-interacting.

## 3 Analytical study

The situation changes if the external on-site potential is present. It is easy to introduce similar quasiparticles ($`E_k`$ will be a sum of kinetic and potential energy). The unit vector n of each quasiparticle between subsequent interactions may be either constant (motion in one direction) or periodically changing (vibration of the particle in a potential well). In every collision the particles exchange their velocity vectors, but do not change their positions. Consequently two quasiparticles interact in a way described by the following relationships:

$`E_1^{}`$ $`=`$ $`E_1+U(x_c+d/2)U(x_cd/2),`$
$`E_2^{}`$ $`=`$ $`E_2U(x_c+d/2)+U(x_cd/2),`$
$`𝐧_1^{}`$ $`=`$ $`𝐧_1,`$ (3)
$`𝐧_2^{}`$ $`=`$ $`𝐧_2.`$
The values denoted by apostrophe correspond to the state after the collision, $`x_c`$ is a point of contact between the particles. It should be mentioned that in the case of nonzero diameter the quasiparticles are associated with the centers of the carrying particles.

If the diameter of the particles is zero, then the additives to the energies in the first two equations of system (3) compensate each other and the energies of the quasiparticles are preserved in the collision. Therefore effectively the interaction between the quasiparticles disappears and the chain of equal particles with zero size subject to any on-site potential turns out to be completely integrable system. Thus, contrary to some previous statements it is possible to construct an example of strongly nonlinear one-dimensional chain without momentum conservation, which will have clearly divergent heat conductivity (even linear temperature profile will not be formed).

The situation differs if the size of the particles is not zero, as the individual energies of the quasiparticles are not preserved in the collisions. In order to consider the effect of such interaction we propose simplified semi-phenomenological analytical model.

After $`l`$ collisions the energy of the quasiparticle will be

$$E(l)=E_0+\underset{j=1}{\overset{l}{}}\mathrm{\Delta }E_j,\mathrm{\Delta }E_j=U(x_j+d/2)U(x_jd/2),$$
(4)
where $`j`$-th collision takes place in point $`x_j`$, $`E_0`$ is the initial energy of the quasiparticle. Now we suppose that the coordinates of subsequent contact points $`\{\mathrm{},x_{j1},x_j,x_{j+1},\mathrm{}\}`$, taken by modulus of the period of the on-site potential, are not correlated. Such proposition is equivalent to fast phase mixing in a system close to integrable one and is well-known in various kinetic problems . The consequences of this proposition will be verified below by direct numerical simulation.

Average energy of the quasiparticle is equal to $`E_0`$ over the ensemble of the quasiparticles, as obviously $`\mathrm{\Delta }E_j=0`$. Still, the second momentum will be nonzero:

$$(E(l)E_0)^2=l(U(x+d/2)U(xd/2))^2_x$$
(5)
The right-hand side of this expression will depend only on the exact shape of the potential function

$$(E(l)E_0)^2=lF(d),F(d)=\frac{1}{a}_0^a[U(x+d/2)U(xd/2)]^2𝑑x,$$
(6)
The last expression is correct only at the limit of high temperatures; it neglects the fact that the quasiparticle spends more time near the top of the potential barrier due to lower velocity.

Let us consider the quasiparticle with initial energy $`E_0>U_0`$, where $`U_0`$ is the height of the potential barrier. Therefore vector $`𝐧`$ is constant. Equations (5) and (6) describe random walks of the energy of the quasiparticle along the energy scale axis. Therefore after certain number of steps (collisions) the energy of the quasiparticle will enter the zone below the potential barrier $`E(l)<U_0`$. In this case the behaviour of the quasiparticle will change, as constant vector $`𝐧`$ will become oscillating, as described above. After some additional collisions the energy will again exceed $`U_0`$, but the direction of motion of the quasiparticle will be arbitrary. It means that the only mechanism of energy transfer in the system under consideration is associated with diffusion of the quasiparticles, which are trapped by the on-site potential and afterwards released in arbitrary direction. Such traps-and-releases resemble Umklapp processes of phonon-phonon interaction , but occur in a purely classic system.

The diffusion of the quasiparticles in the chain is characterized by mean free path, which may be evaluated as

$$\lambda \frac{2a(U_0E_0)^2}{n_cF(d)}\frac{2a[2(k_BT)^22U_0k_BT+U_0^2]}{n_cF(d)},$$
(7)
where $`n_c`$ is a number of particles over one period of the on-site potential (concentration). Coefficient 2 appears due to equivalent probability of positive and negative energy shift in any collision, $`T`$ – temperature of the system, $`k_B`$ – Boltzmann constant.

Average absolute velocity of the quasiparticle may be estimated as

$$|v|\frac{a}{an_cd}\sqrt{\frac{\pi k_BT}{2}}$$
(8)
Here the first multiplier takes into account the nonzero value of $`d`$ and absolute rigidity of the particles. The second one is due to standard Maxwell distribution function for 1D case.

Heat capacity of the system over one particle is unity, as the number of degrees of freedom (i.e. the number of quasiparticles) coincides with the number of the particles and does not depend on the temperature and other parameters of the system. Therefore the coefficient of heat conductivity may be estimated  as

$$\kappa \lambda |v|\frac{2a^2}{n_c(an_cd)}\frac{2(k_BT)^22U_0k_BT+U_0^2}{F(d)}\sqrt{\pi k_BT/2}$$
(9)
It is already possible to conclude that according to (9) regardless the concrete shape of potential $`U(x)`$ in the limit $`d0`$ we have $`F(d)0`$ and therefore $`\kappa \mathrm{}`$, although for every nonzero value $`d`$ the heat conductivity will be finite. Therefore unlikely known models with conserved momentum the small perturbation of the integrable case $`d=0`$ immediately brings about convergent heat conductivity.

## 4 Numerical simulations

It is convenient to introduce the dimensionless variables for the following numerical simulation. Let us set the mass of each particle $`M=1`$, on-site potential period $`a=2`$, its height $`U_0=1`$, and Boltzmann constant $`k_B=1`$ in all above relationships. We suppose that the chain contains one particle per each period of the potential, i.e. that $`n_c=1`$, and the particle diameter $`0<d<2`$.

Let us consider periodic piecewise linear on-site potential

$`U(x)`$ $`=`$ $`x\text{if}x[0,1],`$
$`U(x)`$ $`=`$ $`2x\text{if}x[1,2],`$ (10)
$`U(x+2l)`$ $`=`$ $`U(x)\text{for}x[0,2],l=0,\pm 1,\pm 2,\mathrm{}`$
(the shape of the potential is presented at Fig. 1). Then it follows from (9) that the non-dimensional heat conduction coefficient is expressed as

$$\kappa =\frac{8(2T^22T+1)}{(2d)F(d)}\sqrt{\pi T/2},$$
(11)
where function

$`F(d)`$ $`=`$ $`d^22/3d^3,\text{for}0<d1`$ (12)
$`F(d)`$ $`=`$ $`4/3+4d3d^2+2/3d^3,\text{for}1d<2.`$
The numerical scheme for solving the equations of motion describing the dynamics of the 1D hard-point gas has been developed in a series of papers .

Dynamics of the system of particles with potential of the nearest-neighbor interaction (2) and piecewise linear on-site potential (10) may be described exactly. Between the collisions each particle moves under constant force with sign dependent on the position of the particle. Therefore the coordinate of each particle depends on time $`t`$ as piecewise parabolic function which may be easily computed analytically. If the particle centers are situated at distance equal to $`d`$, then elastic collision occurs. The particles exchange their momenta as described above and afterwards the particle motion is again described by piecewise parabolic functions until the next collision.

Let us consider finite chain of $`N`$ particles with periodic boundary conditions. Let at the moment $`t=0`$ one particle be at each potential minimum and let us choose Boltzmann’s distribution of the initial velocity. Solving the equations of motion, we find a time $`t_1`$ of the first collision between some pair of the adjacent particles, next a time $`t_2`$ of the second collision, in general between another pair of the adjacent particles, and so on. As a result, we obtain a sequence $`\{t_i,n_i\}_{i=1}^{\mathrm{}}`$, where $`t_i`$ is the time of the $`i`$th collision in the system, and $`n_i`$ and $`n_i+1`$ are the particles participating in this collision. Since we need to implement numerical simulations as long as possible, in order to find the time asymptotic of the heat flux autocorrelation function entering the Green-Kubo formula, we use the numerical scheme of paper . First, we incorporate the energy change of the $`n_i`$th particle during the $`i`$th collision as

$$\mathrm{\Delta }E_{n_i}=\frac{1}{2}(v_{n_i}^{}{}_{}{}^{2}v_{n_i}^{}{}_{}{}^{2})=\frac{1}{2}(v_{n_i+1}^{}{}_{}{}^{2}v_{n_i}^{}{}_{}{}^{2}).$$

Next, we introduce a time step $`\mathrm{\Delta }t`$, which is significantly less than the simulation time, but satisfies the inequality $`\mathrm{\Delta }tt_0`$, where $`t_0=lim_i\mathrm{}(t_i/i)`$ is the mean time between successive collisions. Then, for each $`k=0,1,\mathrm{}`$, we define the local energy flow as a piecewise constant (in time) function

$$j_n(t)=\frac{a}{\mathrm{\Delta }t}\underset{iI_{kn}}{}\mathrm{\Delta }E_{n_i},k\mathrm{\Delta }tt<(k+1)\mathrm{\Delta }t,$$
(13)
where the integer sets $`I_{kn}`$’s are defined by

$$I_{kn}=\{i|k\mathrm{\Delta }tt_i<(k+1)\mathrm{\Delta }_t,n_i=n\}.$$

The set $`I_{kn}`$ takes into account those collisions that occur between particles $`n`$ and $`n+1`$ during the time interval $`k\mathrm{\Delta }tt<(k+1)\mathrm{\Delta }_t`$. Equilibration times were typically occurring in the system of the order $`10^6`$. After these times have passed, we define the time-averaged local thermal flow

$$J_n=j_n(t)_t\underset{t\mathrm{}}{lim}\frac{1}{t}_0^tj_n(\tau )𝑑\tau $$
(14)
and the temperature distribution $`T_n=v_n^2(t)_t`$, where $`v_n(t)`$ is the velocity of particle $`n`$ calculated at a time $`t`$. To find these averaged quantities, we have used times up to $`10^7`$.

To find the heat flux autocorrelation function $`C(t)`$ numerically, we calculated the time mean$`J(\tau )J(\tau t)_\tau /NT^2`$, with $`J(t)=_nj_n(t)`$ being the total heat flow through the gas/chain system consisting of $`N=500`$ particles and temperature $`T=_nT_n/N`$ averaged over $`10^4`$ realizations of initial thermalization.

Numerical simulation of the dynamics demonstrates exponential decrease of the autocorrelation $`C(t)\mathrm{exp}(\alpha t)`$ for all values of the diameter $`0<d<2`$ and temperature $`T>0`$ where the simulation time is plausible from technical viewpoint. For low temperatures however the exponential decrease is accompanied by oscillations with period corresponding to the frequency of the vibrations near the potential minima (Fig. 2). The reason is that if the temperatures are low, the concentration of transient particles decreases exponentially and majority of the particles vibrates near the potential minima. It means that the 1D gas on the on-site potential has finite heat conductivity. Coefficient of the exponential decrease of the autocorrelation function

$$\alpha =\underset{t\mathrm{}}{lim}\frac{\mathrm{ln}C(t)}{t}$$
(15)
and coefficient of the heat conduction

$$\kappa =_0^{\mathrm{}}C(t)𝑑t.$$
(16)
are computed numerically.

Dependence of $`\alpha `$ and $`\kappa `$ on particle diameter $`d`$ is presented at Fig. 3. Maximum of $`\alpha `$ and minimum of $`\kappa `$ is attained at $`d=1.4`$. As the temperature grows, $`\alpha `$ decreases \[Fig. 4 (a)\], and heat conduction $`\kappa `$ increases \[Fig. 4 (a)\].

Theoretical analysis of the heat conductivity presented above allows only approximate \[although rather reliable, see Figs. 3(b), 5\] prediction of the numerical value of the heat conduction coefficient $`\kappa `$. Still, the other question of interest is the asymptotic dependence of the heat conduction on the parameters of the model. Formulae (11), (12) lead to the following estimations:

$`\kappa T^{5/2},`$ $`\text{for}T\mathrm{},`$ (17)
$`\kappa d^2,`$ $`\text{for}d+0,`$ (18)
$`\kappa (2d)^3,`$ $`\text{for}d20.`$ (19)
These estimations should be compared to numerical results.

In order to check estimation (17) we consider the dependence of the logarithm of the heat conduction $`\mathrm{ln}\kappa `$ on the logarithm of the temperature $`\mathrm{ln}T`$. From Fig. 5 it is clear that in accordance with (17) $`\mathrm{ln}\kappa `$ grows as $`2.5\mathrm{ln}T`$ as $`T\mathrm{}`$. Fig. 6 (a) demonstrates that as $`d+0`$, the logarithm $`\mathrm{ln}\kappa `$ grows as $`2\mathrm{ln}d`$, in accordance with (18). Fig. 6 (b) demonstrates that as $`d20`$, the logarithm $`\mathrm{ln}\kappa `$ grows as $`3\mathrm{ln}(2d)`$, in accordance with (19). So, it is possible to conclude that analytical estimations (17), (18) and (19) fairly correspond to the numerical simulations data.

The above analytical estimations imply that the type of dependence of characteristic exponent $`\alpha `$ and heat conductivity $`\kappa `$ on diameter $`d`$ and temperature $`T`$ does not depend on the concrete shape of on-site potential $`U(x)`$ – actually, only its finiteness and periodicity do matter. Piecewise linear periodic potential (10) was chosen since it allowed essential simplification of the numerical procedure. For comparison we have considered also the smooth sinusoidal periodic potential

$$U(x)=[1\mathrm{cos}(\pi u)]/2$$
(20)
with period 2 and amplitude $`U_0=1`$, similarly to potential (10).

Potential (20) does not allow exact integration and requires standard numerical procedures. Therefore it is convenient also to change rigid wall potential (2) by smooth Lennard-Jones potential

$$V(ϵ;r)=ϵ\left(\frac{1}{rd}\frac{1}{2d}\right)^2.$$
(21)
Parameter $`ϵ>0`$ characterizes rigidity of the potential, the hard-particle potential being the limit case:

$$V(r)=\underset{ϵ+0}{lim}V(ϵ;r).$$

Methods of computing of the autocorrelation function $`C(t)`$ and the heat conduction coefficient $`\kappa `$ in 1D chain with analytic potentials of interaction are described in  in detail. It should be mentioned that in order to get close to the limit of the hard particles we should use small values of $`ϵ`$ (at the temperature $`T=1`$ value $`ϵ=0.01`$ was used). It implies rather small value of the integration step. (We used standard Runge-Kutta procedure of the fourth order with constant integration step $`\mathrm{\Delta }t=0.0001`$). Therefore for the case of hard (or nearly hard) particles the simulation with smooth on-site potential (20) is far more time-consuming than the simulation with piecewise linear potential (2).

In the case of hard particles with smooth on-site potential the autocorrelation function $`C(t)`$ decreases exponentially as $`t\mathrm{}`$ for all range $`0<d<2`$, $`T>0`$, i.e. the heat conduction converges. Fig. 7 demonstrates that the type of dependence of $`\alpha `$ and $`\kappa `$ on parameters $`d`$ and $`T`$ is similar for piecewise linear potential (2) and sinusoidal potential (20) (although numerical values $`\alpha `$ and $`\kappa `$ vary slightly). For this potential function $`F(d)=\frac{1}{2}\mathrm{sin}^2(\pi d/2)`$. It confirms that type of heat conduction does not depend on concrete choice of on-site potential function.

## 5 Conclusion

We have considered the heat conduction process in the 1D lattice of hard particles with periodic on-site potential. Analytical treatment predicts that for zero diameter of the particles the system will be completely integrable regardless the exact shape of the on-site potential. Therefore the heat conductivity will be infinite. For any nonzero size of the particles the heat transfer is governed by diffusion of quasiparticles giving rise to finite heat conductivity. The value of the heat conduction coefficient computed by the analytical treatment is in line with numerical simulation data. This coincidence is very profound if speaking about the asymptotic scaling behavior of the heat conduction coefficient in the cases of small and large particle sizes, as well as for the case of high temperatures. The characteristic behavior of the heat conduction coefficient does not depend on the exact shape of the on-site potential function.

The above results mean that there exists a new class of universality of 1D chain models with respect to their heat conductivity. The limit case of zero-size particles is integrable, but the slightest perturbation of this integrable case by introducing the nonzero size leads to drastic change of the behavior – it becomes diffusive and the heat conduction coefficient converges. It should be stressed that this class of universality, unlikely the systems with conserved momentum, cannot be revealed by sole numerical simulation. The reason is that the correlation length (as well as the heat conduction coefficient) diverges as the system approaches the integrable limit; therefore any finite capacity of the numerical installation will be exceeded. That is why the analytical approach is also necessary.

The authors are grateful to Russian Foundation of Basic Research (grant 01-03-33122) and to RAS Commission for Support of Young Scientists (6th competition, grant No. 123) for financial support. O.V.G. is grateful to Russian Science Support Foundation for the financial support.


format: text

text:
# Markov Bases of Binary Graph Models

## 1 Introduction and Definitions

The study of multidimensional tables and their marginals is of central importance whenever one wishes to make inferences based on statistical samples. In general, one is presented with a nonnegative integral table of data of size $`d_1\times \mathrm{}\times d_n`$ and a simplicial complex $`\mathrm{\Delta }`$ on $`\{1,\mathrm{},n\}`$ which encodes the specific marginals we would like to compute; this is called a hierarchical model.

Certainly, the oldest example of such a model is the case of computing the row and column sums of a matrix. If the matrix is a square $`m\times m`$ matrix and we require that all the row and column sums have the same value $`k`$, one calls such a matrix a semi-magic square with magic sum $`k`$. Here, our simplicial complex consists of two isolated points.

In the more general statistical situations, each node of the simplicial complex corresponds to a feature of a population sample (e.g. eye color) and the levels of the table correspond to different states of the feature (e.g. green, brown, hazel, etc.). The faces of the simplicial complex are intended to model interactions between the features. One of the most fundamental questions in statistical analysis is: do the data appear to be satisfied by a given model? One way to test the hypothesis is to compare the sample data to the maximum likelihood estimate using the $`\chi ^2`$ or $`G^2`$ statistic. One problem with applying this approach directly is that the data is always an integral table, while the maximum likelihood estimate almost never is. As a result, there might be no integral table with the same marginals which has a small $`\chi ^2`$ statistic. This problem is especially dramatic when analyzing the large, sparse data sets which occur in real world situations (e.g. census data). To remedy this situation, one may attempt to decide whether or not a model fits the data by comparing statistics of the data table with statistics of random integral tables with the same marginals. If the statistic of the table of data is exceptional one could hope to conclude that the table was also exceptional. For example, if the $`\chi ^2`$ statistic of the table of data was exceptionally small, one could conclude that the data did, in fact, fit the model.

We are now left with the problem of generating random integral tables from the set of all nonnegative integral tables with fixed marginals. One solution is to perform a random walk over the set of all nonnegative integral tables with given fixed marginal. Such a random walk can be taken by first finding a suitable set of “moves” (these are tables with integral entries which have all their marginals equal to zero) and randomly adding moves to some starting table. It is at this point in the story that computational commutative algebra enters the picture: finding such a set of moves is equivalent to finding a generating set for the associated toric ideal. For a detailed introduction to the connections between toric algebra and multidimensional contingency tables, see , , and .

In this paper, we restrict attention to tables where $`d_i=2`$ for all $`i`$ and for which the underlying simplicial complex is a graph; that is, we compute only two- and one-way marginals of our binary table. We refer to such models as binary graph models. These are generally not the usual graphical models studied so frequently in statistics, where the simplicial complex consists of the cliques of the underlying graph $`G`$ . Our notion of graph model coincides with the more familiar graphical model if and only if the graph has no three-cycle. Now, we will give two formal presentations of the objects of interest in this paper.

Let $`G`$ be a graph on the $`n`$-element vertex set $`[n]:=\{1,2,\mathrm{},n\}`$ with edge set $`E(G)`$. Denote by $`Iso(G)`$ the set of isolated vertices of $`G`$. For each edge $`\{j,k\}`$ of the graph $`G`$ consider the linear transformations $`\pi _{j,k}`$

$$\pi _{j,k}:^{2^n}^4$$

$$e_{i_1,\mathrm{}i_n}e_{i_j,i_k}$$

and for each isolated vertex $`k`$ of $`G`$ consider the linear transformations $`\pi _k`$

$$\pi _k:^{2^n}^2$$

$$e_{i_1\mathrm{}i_n}e_{i_k}.$$

We think of the maps $`\pi _{j,k}`$ as computing the 2-way marginal of a $`2\times \mathrm{}\times 2`$ table corresponding to the edge $`\{j,k\}`$ and the maps $`\pi _k`$ as computing the 1-way marginal of a $`2\times \mathrm{}\times 2`$ table corresponding to the vertex $`k`$. We define the map $`\pi _G`$ by taking all the marginal computations induced by a given graph as

$$\pi _G:^{2^n}\underset{\{j,k\}E(G)}{}^4\underset{kIso(G)}{}^2$$

$$v\underset{\{j,k\}E(G)}{}\pi _{j,k}(v)\underset{kIso(G)}{}\pi _k(v).$$

We say that $`\pi _G`$ is the map which computes the marginals of a $`2\times \mathrm{}\times 2`$ table according to the graph $`G`$. The matrix which represents this linear transformation will be denoted $`A_G`$ and the polytope which is the convex hull of the columns of $`A_G`$ is denoted $`P_G`$ where we consider the columns of $`A_G`$ as vectors in $`^d`$ for an appropriate $`d`$. A move for $`G`$ is an element of the integral kernel of $`\pi _G`$; that is, a move is an integral table which does not change the $`G`$-marginals of a table it is added to. In general we are interested in sets of moves with special properties.

###### Definition 1.1.

A finite subset of moves $`B\mathrm{ker}_{}(\pi _G)`$ is called a Markov basis for the graph $`G`$ if for every pair of nonnegative integral tables $`v_1,v_2^{2^n}`$ with the same $`G`$-marginals $`\pi _G(v_1)=\pi _G(v_2)`$, there is a sequence of moves $`\{u_i\}_{i=1}^l\pm B`$ such that

$$v_1+\underset{i=1}{\overset{l}{}}u_i=v_2$$

and

$$v_1+\underset{i=1}{\overset{j}{}}u_i^{2^n}\text{ for all }1jl.$$

There is also a much shorter and more algebraic way to arrive at this definition. Recall that $`G`$ is a graph on the $`n`$-element vertex set $`[n]:=\{1,2,\mathrm{},n\}`$ with edge set $`E(G)`$, and isolated vertices $`Iso(G)`$. Consider the map of polynomial rings

$$\varphi _G:[p_{i_1,\mathrm{}i_n}|i_j\{0,1\}][t_{i_j,i_k}^{(j,k)},t_{i_l}^{(l)}|\{j,k\}E(G)\text{ and }lIso(G)]$$

$$p_{i_1\mathrm{}i_n}\underset{\{j,k\}E(G)}{}t_{i_j,i_k}^{(j,k)}\underset{lIso(G)}{}t_{i_l}^{(l)}.$$

The object of interest in this paper is the ideal denoted $`I_G=\mathrm{ker}(\varphi _G)`$, which we call the ideal of a binary graph model. It is a toric ideal: a prime ideal generated by monomial differences whose leading and trailing terms have disjoint support.

Markov bases and toric ideals are connected by the following fundamental theorem.

###### Theorem 1.2.

 A finite subset of moves $`B=\{u_i\}_{i=1}^l\mathrm{ker}_{}(\pi _G)`$ is a Markov basis for $`G`$ if and only if the set of binomials $`\{p^{u_i^+}p^{u_i^{}}\}`$ is a generating set for $`I_G`$.

Here, we write $`u_i=u_i^+u_i^i`$ as the difference of two positive vectors of disjoint support. In light of Theorem 1.2, we will use the expressions “Markov basis for $`G`$” and “generating set for $`I_G`$” interchangeably throughout this paper. Similarly, we can interchange the words “move” and “binomial” whenever we are discussing the Markov bases/generating sets of $`I_G`$. These definitions are best illustrated by a simple example.

###### Example 1.3.

Consider the graph $`G`$ on four nodes with two edges $`\{1,2\}`$ and $`\{2,3\}`$ and one isolated vertex $`4`$. The map $`\varphi _G`$ is a map from a polynomial ring in sixteen variables to a polynomial ring in ten variables. It is the map of rings

$$\varphi _G:[p_{ijkl}|i,j,k,l\{0,1\}][r_{ij},s_{jk},t_l]$$

$$p_{ijkl}r_{ij}s_{jk}t_l.$$

On the other hand, the marginal map $`\pi _G`$ is given by a $`10\times 16`$ matrix $`A_G`$. It is the matrix

$$A_G=\left(\begin{array}{cccccccccccccccc}1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1\end{array}\right).$$

The polytope $`P_G`$ in $`^{10}`$ has dimension 6 and has 10 facets. These facets are indexed naturally by the rows of $`A_G`$ and the facet defining inequalities are given by $`y_i0`$ with one inequality for each row. The ideal $`I_G`$ has a Markov basis consisting of quadratic moves. These are

$$p_{0j0l_1}p_{1j1l_2}p_{0j1l_1}p_{1j0l_2}\text{ with }j,l_1,l_2\{0,1\}$$

and

$$p_{i_1j_1k_1l_1}p_{i_2j_2k_2l_2}p_{i_1j_1k_1l_2}p_{i_2j_2k_2l_1}\text{ with }i_1,j_1,k_1,l_1,i_2,j_2,k_2,l_2\{0,1\}.$$

These generators are also a Gröbner basis with respect to the reverse lexicographic term order with $`p_{0\mathrm{}0}\mathrm{}p_{1\mathrm{}1}`$.

In general, when the underlying graph is a forest, the toric ideal $`I_G`$ is relatively well understood.

###### Theorem 1.4.

 The ideal $`I_G`$ is minimally generated by quadrics if and only if $`G`$ is a forest. In this case, the set of quadratic squarefree binomials in $`I_G`$ forms a Gröbner basis with respect to the reverse lexicographic term order with $`p_{0\mathrm{}0}p_{0\mathrm{}01}\mathrm{}p_{1\mathrm{}1}`$.

In this paper, we are primarily concerned with investigating graphs which contain cycles. One fundamental question is to compute the following invariant of a graph.

###### Definition 1.5.

Let $`G`$ be a graph. The Markov width $`\mu (G)`$ is the degree of the largest minimal generator of the toric ideal $`I_G`$.

Studying the Markov width of a graph is of fundamental importance for statistical applications because it relates the complexity of analyzing data to the complexity of the underlying graphical structure. Note that, Theorem 1.4 states that the graphs with $`\mu (G)=2`$ are precisely forests, which are certainly topologically simple. Indeed, the Markov width of a graph $`G`$ is topological in nature, by which we mean that $`\mu (G)`$ can only decrease under the operations of vertex deletion and edge contraction; we will show this in Section 4. Since these operations interact nicely with the toric ideals of the initial and final graph, we will use the following definition throughout.

###### Definition 1.6.

Let $`G`$ be a graph. By a minor of $`G`$, we mean a graph $`H`$ which can be obtained from $`G`$ via a sequence of edge contractions and vertex deletions.

This is different from the usual definition of a graph minor in that we do not allow edge deletion, whose interaction with the toric ideal is more complicated.

The rest of the paper is organized as follows. In the next section, we discuss computational results for graphs with few vertices and suggest some conjectures based upon these data. In particular, we have computed the Markov width $`\mu (G)`$ for all graphs on five vertices and many of the graphs on six vertices. In the third section, we prove that the $`n`$-cycle and $`K_{2,n}`$ have Markov width 4. Furthermore, we are able to explicitly describe the moves needed in the Markov bases for these graph. The fourth section is devoted to the inverse problem: that is, studying which graphs may have Markov basis elements of a given degree. We give an algorithm which does not depend on computing $`S`$-pairs for computing all the minimal generators of a given degree for the ideals $`I_G`$. As a consequence of our algorithm, we give a combinatorial characterization of moves of degree two and three. In the final section, we return to the study of forests and use the reverse lexicographic Gröbner basis from Theorem 1.4 to derive combinatorial formulae for the algebraic degree of $`I_G`$ whenever $`G`$ is a forest.

## 2 Graphs with Few Vertices

In this section we discuss and display computational results about the ideals of binary graph models. In particular, we describe generating sets for the ideals $`I_G`$ for all graphs $`G`$ with fewer than five vertices and all the graphs on six vertices with at most eight edges. These computational results suggest many conjectures and open problems which we describe at the end of the section. All of our computations were carried out using the toric Gröbner basis program `4ti2`  and the computational algebra system `Macaulay 2` . We limit our description to graphs which cannot be “glued” together from smaller graphs based on the following definition and theorem.

###### Definition 2.1.

Let $`(V_1,S,V_2)`$ be a partition of the vertex set of a graph $`G`$ such that

1. there are no edges in $`G`$ between $`V_1`$ and $`V_2`$ and
2. $`S`$ is either the empty set or $`S`$ is a common vertex or edge of the induced subgraphs $`G_1`$ and $`G_2`$ with vertex sets $`V_1S`$ and $`V_2S`$, respectively.

Then $`G`$ is called reducible with decomposition $`(V_1,S,V_2)`$.

###### Theorem 2.2.

 Let $`G`$ be a graph which is reducible and $`G_1`$ and $`G_2`$ the induced subgraphs arising from the vertex decomposition. Then there is a degree preserving operation with which one can build generating sets and Gröbner bases for $`I_G`$ from generating sets and Gröbner bases of $`I_{G_1}`$ and $`I_{G_2}`$. In particular, $`\mu (G)=\mathrm{max}(\mu (G_1),\mu (G_2))`$.

There are precisely one graph on three vertices, two graphs on four vertices, six graphs on five vertices, and six graphs with six vertices and at most eight edges which are not reducible. We will briefly describe these graphs and their Markov bases.

### 2.1 Three and Four Vertices

The only graph on three vertices which is not reducible is the complete graph $`K_3`$. The Markov basis of $`I_{K_3}`$ consists of the single degree four binomial

$$p_{000}p_{011}p_{101}p_{110}p_{001}p_{010}p_{100}p_{111}.$$

The two irreducible graphs on four vertices are $`C_4`$ and $`K_4`$. The graph $`C_4`$ is the four cycle with $`E(C_4)=\{12,23,34,14\}`$. The Markov basis of $`C_4`$ consists of eight quadrics such as

$$p_{0000}p_{0101}p_{0001}p_{0100}$$

and eight quartics. The complete graph $`K_4`$ has Markov basis consisting of 20 moves of degree four and 40 sextic binomials such as

$$p_{0000}^2p_{0111}p_{1011}p_{1101}p_{1110}p_{0001}p_{0010}p_{0100}p_{1000}p_{1111}^2.$$

### 2.2 Five Vertices

There are six graphs on five vertices which cannot be decomposed into subgraphs. These are the graphs we denote $`C_5`$, $`K_{2,3}`$, $`\stackrel{~}{K_4}`$, $`SP`$, $`BP`$, and $`K_5`$. The graph $`C_5`$ is the five-cycle $`E(C_5)=\{12,23,34,45,15\}`$. Its Markov basis consists of 80 quadrics and 40 quartics. The graph $`K_{2,3}`$ is the complete bipartite graph $`E(K_{2,3})=\{13,14,15,23,24,25\}`$. Its Markov basis consists of 44 quadrics and 420 quartics. The graph $`\stackrel{~}{K_4}`$ is the graph obtained from $`K_4`$ by subdividing an edge, $`E(\stackrel{~}{K_4})=\{12,15,23,24,34,35,45\}`$. The Markov basis for $`I_{\stackrel{~}{K_4}}`$ consists of 32 quadrics, 473 quartics, and 160 sextics. The graph $`SP`$ is the edge graph of the square pyramid, $`E(SP)=\{12,13,15,23,24,34,35,45\}`$. The Markov basis of $`SP`$ consists of 16 quadrics, 671 quartics, and 320 sextics. The graph $`BP`$ is the edge graph of the bipyramid over a triangle, $`E(BP)=\{12,13,15,23,24,25,34,35,45\}`$. Its Markov basis consists of 8 quadrics, 436 quartics, and 2872 sextic binomials. Finally, $`K_5`$ is the complete graph on five vertices. The Markov basis of $`K_5`$ consists of 260 degree four moves, 3952 sextic binomials, 846 binomials of degree eight such as

$$p_{00000}^3p_{01111}p_{10111}p_{11011}p_{11101}p_{11110}p_{00001}p_{00010}p_{00100}p_{01000}p_{10000}p_{11111}^3$$

and 480 degree ten binomials like

$$p_{00000}^2p_{01111}^2p_{10001}^2p_{10010}^2p_{10100}p_{11000}p_{00010}p_{00101}p_{01001}p_{01110}p_{10000}^4p_{10011}p_{11111}.$$

### 2.3 Six Vertices

There are a total of 29 graphs on six vertices which are not reducible. We were able to compute Markov bases for the six irreducible graphs on six vertices which have at most eight edges. It remains a major computational challenge to determine Markov bases of the other 23 irreducible graphs on six vertices. The six irreducible graphs on six vertices with less than nine edges will be denoted $`C_6`$, $`K_{2,4}`$, $`G_{129}`$, $`G_{151}`$, $`G_{153}`$, and $`G_{154}`$.

The graph $`C_6`$ is the six cycle with edge set $`E(C_6)=\{12,23,34,45,56,16\}`$. The graph $`K_{2,4}`$ is the complete bipartite graph with edge set $`E(K_{2,4})=\{13,14,15,16,23,24,25,26\}`$. The remaining graphs do not have special names: the labels we have chosen come from . These four graphs have edge sets $`E(G_{129})=\{12,15,23,26,34,45,56\}`$, $`E(G_{151})=\{12,14,23,26,34,36,45,46\}`$, $`E(G_{153})=\{12,15,16,23,24,45,46,56\}`$, and $`E(G_{154})=\{12,14,23,25,34,36,45,56\}`$. The data regarding the Markov bases of these graphs as well as all the irreducible graphs on five and fewer vertices is summarized in the following table. The columns are labeled by the particular irreducible graph, the rows are labelled by degree of minimal generators and the table entries are the number of minimal generators of a given degree.

$$\begin{array}{cccccccccccccccc}& \hfill K_3& \hfill C_4& \hfill K_4& \hfill C_5& \hfill K_{2,3}& \hfill \stackrel{~}{K_4}& \hfill SP& \hfill BP& \hfill K_5& \hfill C_6& \hfill K_{2,4}& \hfill G_{129}& \hfill G_{151}& \hfill G_{153}& \hfill G_{154}\\ & & & & & & & & & & & & & & & \\ \hfill 2& \hfill 0& \hfill 8& \hfill 0& \hfill 80& \hfill 44& \hfill 32& \hfill 16& \hfill 8& \hfill 0& \hfill 528& \hfill 236& \hfill 360& \hfill 280& \hfill 320& \hfill 256\\ & & & & & & & & & & & & & & & \\ \hfill 4& \hfill 1& \hfill 8& \hfill 20& \hfill 40& \hfill 420& \hfill 473& \hfill 671& \hfill 436& \hfill 260& \hfill 160& \hfill 11696& \hfill 2636& \hfill 4949& \hfill 4149& \hfill 7784\\ & & & & & & & & & & & & & & & \\ \hfill 6& \hfill 0& \hfill 0& \hfill 40& \hfill 0& \hfill 0& \hfill 160& \hfill 320& \hfill 2872& \hfill 3952& \hfill 0& \hfill 0& \hfill 0& \hfill 640& \hfill 480& \hfill 640\\ & & & & & & & & & & & & & & & \\ \hfill 8& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 846& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0\\ & & & & & & & & & & & & & & & \\ \hfill 10& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 480& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0\\ & & & & & & & & & & & & & & & \\ & & & & & & & & & & & & & & & \\ \hfill \text{Total}& \hfill 1& \hfill 16& \hfill 60& \hfill 120& \hfill 464& \hfill 665& \hfill 1007& \hfill 3316& \hfill 5538& \hfill 688& \hfill 11932& \hfill 2996& \hfill 5869& \hfill 4949& \hfill 8680\\ & & & & & & & & & & & & & & & \\ \hfill \mu (G)& \hfill 4& \hfill 4& \hfill 6& \hfill 4& \hfill 4& \hfill 6& \hfill 6& \hfill 6& \hfill 10& \hfill 4& \hfill 4& \hfill 4& \hfill 6& \hfill 6& \hfill 6\end{array}$$

For these graphs, all generators are in even degree. This is not true in general, however, as we will demonstrate in Section 4. Theorem 1.4 characterizes graphs with $`\mu (G)=2`$ as forests, but the next case is already quite interesting.

###### Problem 2.3.

Characterize those graphs with Markov width $`\mu (G)=4`$.

In the next section we will show that cycles and the complete bipartite graphs $`K_{2,n}`$ have Markov bases consisting of moves of degree four or less, but from the data we see that this is not yet a complete characterization.

A natural class of graphs which one would hope to understand is planar graphs. The data above suggest the following optimistic conjecture.

###### Conjecture 2.4.

There is a universal constant $`C`$ such that the Markov width $`\mu (G)C`$ whenever $`G`$ is a planar graph. Even stronger, $`C=6`$.

On the other hand, the data also suggest the following conjecture.

###### Conjecture 2.5.

The invariant $`\mu (G)`$ is a function only of the tree width of $`G`$.

The tree width is a topological invariant of a graph $`G`$ which is equal to one less than the size of the largest clique in the chordal graph containing $`G`$ which has the smallest maximal clique. For example, forests are precisely those graphs with tree width zero or one, and indeed Theorem 1.4 tells us that these graphs all have Markov width two. Conjecture 2.5 also agrees with Theorem 2.2, since the tree width of a reducible graph is the maximum of the tree widths of its components.

While the limited information we have suggests both Conjecture 2.4 and Conjecture 2.5, they cannot both be true: there are planar graphs with arbitrarily large tree width. For example, grid graphs can have arbitrarily large clique size in their minimal chordal triangulations. This suggests another research problem.

###### Problem 2.6.

Study the binary graph model $`I_G`$ for the family of $`m\times n`$ grid graphs.

We do know that $`\mu (G)`$ can be arbitrarily large. For example, for the complete graph $`K_m`$ we can construct generators of large degree.

###### Proposition 2.7.

The complete graph $`K_m`$ with $`m3`$ has Markov width $`\mu (K_m)2m2`$.

###### Proof.

It suffices to show that there is a minimal generator of $`K_m`$ of degree $`2m2`$. For this consider the binomial

$$p_\mathrm{𝟎}^{m2}\underset{i=1}{\overset{m}{}}p_{\mathrm{𝟏}e_i}p_\mathrm{𝟏}^{m2}\underset{i=1}{\overset{m}{}}p_{e_i}$$

where $`\mathrm{𝟎}`$ is the string of all zeros, $`\mathrm{𝟏}`$ is the string of all ones, and $`e_i`$ is the $`i`$th unit vector. Then the monomials coming from the leading and trailing terms are the only monomials which have the given image under $`\varphi _{K_m}`$. Equivalently, the corresponding tables are the only two tables which have these same fixed marginals under $`\pi _{K_m}`$. Since the leading and trailing terms have disjoint support, this binomial must appear in every Markov basis for $`I_{K_m}`$. ∎

Of course, this bound is already not tight for $`m=5`$, where it yields $`\mu (K_5)8`$ despite the fact that $`K_5`$ has Markov width 10. In general we suspect that $`\mu (K_m)`$ grows exponentially in $`m`$.

## 3 Cycles and Bipartite Graphs

In this section we confirm the observations from the second section: the ideal of the cycle and the complete bipartite graph $`K_{2,n}`$ are generated in degrees two and four.

### 3.1 Cycles

For ease of notation, we will represent a binomial such as $`p_{1011}p_{1110}p_{1111}p_{1010}`$ in tableau notation as

$$\left[\begin{array}{cccccc}1& 0& 1& 1& & \\ 1& 1& 1& 0& & \end{array}\right]\left[\begin{array}{cccccc}1& 1& 1& 1& & \\ 1& 0& 1& 0& & \end{array}\right].$$

The tableau are obtained from a binomial by recording the indices of each variable which appears in the monomial, repeating indices when a variable appears to a power greater than one. We say that one binomial contains another if it does so in the Graver sense; that is, $`p^up^v`$ contains $`p^ap^b`$ if $`au`$ and $`bv`$ componentwise.

We first prove the following theorem bounding the degree of minimal generators for the $`n`$-cycle.

###### Theorem 3.1.

Let $`C_n`$ be the $`n`$-cycle graph. Then $`\mu (C_n)=4`$, and in particular $`I_{C_n}`$ is generated in degrees 2 and 4.

###### Proof.

We will start with an arbitrary binomial $`f`$ in the ideal, and express it as a linear combination of elements either of lower degree or of degree at most 4.

Given any binomial, take one variable from each monomial such that the two variables chosen agree in first and last index. Our strategy will be as follows: by adding multiples of ideal elements of degree 4 and less, we will eventually obtain a binomial in which both monomials have the same variable. Dividing out by this variable (which clearly does not affect membership in $`I_G`$) yields a binomial of lower degree which must still be in the ideal, completing the proof.

We now start this process. We have a variable $`p_{1\mathrm{?}\mathrm{}\mathrm{?}1}`$ in the first term of $`f`$, and a variable $`p_{1\mathrm{?}\mathrm{}\mathrm{?}1}`$ in the second term. We wish to eliminate all disagreements between these indices by “moving” the table entries corresponding to these binary strings using binomials of degree 4 or less.

Consider any block of disagreements, in which, without loss of generality, the indices of these variables look like $`(\mathrm{}\mathrm{?}10\mathrm{}01\mathrm{?}\mathrm{})`$ and $`(\mathrm{}\mathrm{?}11\mathrm{}11\mathrm{?}\mathrm{})`$. We propose to add some multiple of an ideal element of degree $`g`$ at most 4 so that the resulting binomial contains the two variables in question, and is unchanged except that some of the disagreements in the block have been removed. The two sets of index strings in $`g`$ will agree on the portion of $`C_n`$ outside of the block in question, counting the boundary elements. Essentially, we are performing a local move by changing indices on a subgraph of $`C_n`$. Let $`\stackrel{~}{f}`$ represent the image of $`f`$ in this subgraph, i.e. under the map sending $`p_{\mathrm{}\mathrm{?}I\mathrm{?}\mathrm{}}`$ to $`p_I`$, where $`I`$ is the index substring on the block we have.

Continuing in this manner, by induction on the number of disagreements we eventually obtain a binomial for which the same variable appears in both monomials, completing the proof. We now construct the ideal element $`g`$ which we will add a multiple of. We first construct the part $`\stackrel{~}{g}`$ which corresponds to the block in question; in the tableaux that follow, we consider only the indices corresponding to this block.

Because this element is in the ideal $`I_{C_n}`$, considering the marginal in the first two directions, since an element in the first term of $`f`$ has a $`10`$ marginal, so must an element in the second term. So $`\stackrel{~}{f}`$ contains

$$\left[\begin{array}{cccccc}1& 0& 0& \mathrm{}& 0& 1\end{array}\right]\left[\begin{array}{cccccc}1& 1& 1& \mathrm{}& 1& 1\\ 1& 0& \mathrm{?}& \mathrm{}& \mathrm{?}& \mathrm{?}\end{array}\right].$$

Now, if any of the unspecified elements is 1, we let $`\stackrel{~}{g}`$ be the binomial which switches the intervening substrings, i.e. something of the form

$$\left[\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 0& 0& 1& A\end{array}\right]\left[\begin{array}{ccccc}1& 0& 0& 1& 1\\ 1& 1& 1& 1& A\end{array}\right],$$

where $`A`$ is the remainder of the index string of the element that the second term of $`\stackrel{~}{f}`$ contains starting with $`10`$. We fill in the rest of both terms of $`g`$ as the two index strings corresponding to the two variables contained in the second term of $`\stackrel{~}{f}`$ are filled in, so that the two variables of the first term of $`g`$ are contained in the second term of $`f`$. Adding $`g`$ to $`f`$ then has the effect of eliminating some disagreements between the two variables as desired, while leaving everything unchanged outside the block in question.

Otherwise, all of the elements marked $`\mathrm{?}`$ must be 0. We can apply the same argument to the terminal string and to the other binomials to obtain $`g`$ in all cases except where $`\stackrel{~}{f}`$ contains

$$\left[\begin{array}{ccccc}1& 0& \mathrm{}& 0& 1\\ 1& 1& \mathrm{}& 1& 0\\ 0& 1& \mathrm{}& 1& 1\end{array}\right]\left[\begin{array}{ccccc}1& 1& \mathrm{}& 1& 1\\ 1& 0& \mathrm{}& 0& 0\\ 0& 0& \mathrm{}& 0& 1\end{array}\right].$$

In this case, because we have a $`00`$ marginal in the first two coordinates of the second term of $`\stackrel{~}{f}`$, we must have one in the first term. If that element contains any 1, by adding a multiple of a binomial of degree 2 involving it and the third element in the first term, and then another multiple of a binomial of degree 2 involving the third element and the first element in the first term, we can construct a $`g`$ essentially as before which reduces disagreements. The only case where we cannot apply this argument to this fourth element is when $`\stackrel{~}{f}`$ contains

$$\left[\begin{array}{ccccc}1& 0& \mathrm{}& 0& 1\\ 1& 1& \mathrm{}& 1& 0\\ 0& 1& \mathrm{}& 1& 1\\ 0& 0& \mathrm{}& 0& 0\end{array}\right]\left[\begin{array}{ccccc}1& 1& \mathrm{}& 1& 1\\ 1& 0& \mathrm{}& 0& 0\\ 0& 0& \mathrm{}& 0& 1\\ 0& 1& \mathrm{}& 1& 0\end{array}\right].$$

In this case, we let $`\stackrel{~}{g}`$ be this binomial of degree 4, corresponding to switching the middle substrings of all 0’s and all 1’s. Again, we extend this to $`g`$ by copying the indices from $`f`$ outside this block to the relevant variables, and we can add this element to $`f`$ to eliminate this patch of disagreements between the variables in question. This completes the proof by induction. Note that we did not use any elements of degree 3 in this process, so $`I_{C_n}`$ is in fact generated in degrees 2 and 4. ∎

This theorem not only shows that the minimal generators are all of degree 2 or 4, but it also gives a complete description of these generators. The degree-2 generators come from separations of the graph; we will prove a general statement characterizing degree-2 generators of graph ideals in Section 5. As for the minimal generators of degree four, we have the following categorization.

###### Theorem 3.2.

The minimal generators of degree 4 in the graph ideal $`I_{C_n}`$ are those elements of the form

$$\left[\begin{array}{cccc}A_1& 1& B& 1\\ A_2& 1& 1B& 0\\ A_3& 0& 1B& 1\\ A_4& 0& B& 0\end{array}\right]\left[\begin{array}{cccc}A_1& 1& 1B& 1\\ A_2& 1& B& 0\\ A_3& 0& B& 1\\ A_4& 0& 1B& 0\end{array}\right],$$

where the columns correspond to $`V_1,x_1,V_2`$, and $`x_2`$, $`V_1`$ and $`V_2`$ are contiguous blocks of elements, and these elements in this order comprise the $`n`$-cycle. Here, $`1B`$ represents the opposite string of $`B`$.

Note that these generators of degree 4 are very similar to the generator of degree 4 in $`K_3`$, namely

$$\left[\begin{array}{ccc}1& 1& 1\\ 1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\\ 0& 0& 0\end{array}\right].$$

We will prove a general similarity theorem in this vein in Section 4, when we classify generators of a given degree.

### 3.2 Complete Bipartite Graphs

Another nice class of models is the $`K_{m,n}`$ model, where $`K_{m,n}`$ is the complete bipartite graph with partite sets of $`m`$ and $`n`$ vertices. We first prove the following theorem.

###### Theorem 3.3.

The graph ideal for $`G=K_{2,n}`$ is generated in degrees 2 and 4 (for $`n2`$).

###### Proof.

As in the proof of Theorem 3.1, we use binomials of small degree ($`4`$) to transform a binomial in this ideal to one whose two terms share a variable, completing the proof by induction. Let the vertices of the two-element partite set be $`V=\{v_1,v_2\}`$, and let the vertices of the $`n`$-element partite set be $`W=\{w_1,\mathrm{},w_n\}`$.

For each monomial $`M`$, we define the submonomial $`M_{ij}`$, $`i,j\{0,1\}`$, to be the product of the variables with $`ij`$ in the index string corresponding to the two-element partite set; we will write that index string first. For a monomial $`M`$, we define $`a_{ij}(M)`$ to be the total degree of $`M_{ij}`$, and $`b_{ij,k,l}(M)`$ to be the number of appearances of the digit $`k`$ in the $`w_l`$-position of the index strings of the variables in $`M_{ij}`$. Here $`k\{0,1\}`$ and $`l\{1,\mathrm{},n\}`$. In other words, these function values enumerates the marginal in the direction $`(v_1,v_2,w_l)`$ with the set values $`(i,j,k)`$. We can of course recover $`a_{ij}(M)=b_{ij,0,l}+b_{ij,1,l}`$ for any $`l`$.

Then we have the following easy lemma.

###### Lemma 3.4.

If $`M_1`$ and $`M_2`$ are monomials such that $`b_{ij,k,l}(M_1)=b_{ij,k,l}(M_2)`$ for all $`i,j,k,l`$, then their difference can be expressed as a sum of multiples of quadratic elements of $`I_G`$.

We do this simply by, for each $`M_{ij}`$, using quadratic generators corresponding to the separation $`(w_l,V,W\{w_l\})`$ to move around the $`b_{ij,1,l}(M)`$ 1’s in the $`l`$th column. Consequently, we need only to connect monomials with the same marginals and different $`F`$-values. We introduce an additional definition.

Given a monomial $`M`$, the function $`c_{ij,l}(M)`$ is defined to be the subset of $`0,1`$ which appears in the $`w_l`$-position in the variables of $`M_{ij}`$. Explicitly, this contains 0 when $`b_{ij,0,l}(M)>0`$, and 1 when $`b_{ij,1,l}(M)>0`$.

We now unspool a series of moves designed to connect all of the remaining $`F`$-values of monomials with the same marginals.

###### Lemma 3.5.

Suppose we have a monomial $`M`$ and a column $`l`$ such that $`1c_{01,l}(M),c_{10,l}(M)`$ and $`0c_{00,l}(M),c_{11,l}(M)`$. Then $`M`$ is equivalent by adding a multiple of a binomial of degree 4 to a monomial with the following changes to the $`a_I`$’s and $`b_I`$’s:

$$\begin{array}{c}+1:b_{01,0,l},b_{10,0,l},b_{11,1,l},b_{00,1,l},\\ 1:b_{01,1,l},b_{10,1,l},b_{11,0,l},b_{00,0,l}.\end{array}$$

###### Proof.

This corresponds merely to adding a multiple of the degree 4 binomial

$$\left[\begin{array}{cccc}1& 1& 1& I_1\\ 1& 0& 0& I_2\\ 0& 0& 1& I_3\\ 0& 1& 0& I_4\end{array}\right]\left[\begin{array}{cccc}1& 0& 1& I_1\\ 1& 1& 0& I_2\\ 0& 1& 1& I_3\\ 0& 0& 0& I_4\end{array}\right],$$

where the columns are $`v_1,w_l`$, and $`v_2`$, and all other vertices in some order. This binomial comes from the minor $`K_3`$ given by contracting all the $`w_i`$, $`il`$, into either $`v_1`$ or $`v_2`$. ∎

###### Lemma 3.6.

Suppose we have a monomial $`M`$ such that for each column $`l`$, there exists some index $`i_l`$ such that $`i_lc_{01,l}(M),c_{10,l}(M)`$. Then $`M`$ is equivalent by adding a multiple of a binomial of degree $`2`$ to a monomial with the following changes to the $`a_I`$’s and $`b_I`$’s:

$$\begin{array}{c}+1:a_{11},a_{00},b_{11,i_l,l},b_{00,i_l,l},\\ 1:a_{10},a_{01},b_{01,i_l,l},b_{10,i_l,l},\end{array}$$

for all $`l\{1,\mathrm{},n\}`$.

###### Proof.

If $`I`$ is the index string composed of the $`i_l`$, this corresponds to adding a multiple of the degree 2 binomial

$$\left[\begin{array}{ccc}1& 1& I\\ 0& 0& I\end{array}\right]\left[\begin{array}{ccc}1& 0& I\\ 0& 1& I\end{array}\right],$$

where the columns are indexed by $`v_1`$, $`v_2`$, and the $`w_l`$. ∎

Now, suppose we have two monomials with the same marginals, that is the same image under $`\varphi _G`$. Add multiples of the binomials from Lemma 3.5 and Lemma 3.6 until one can no longer apply these; since both increase $`a_{11}+b_{11,l}`$, one will not go around in circles. Our monomials $`M`$ and $`N`$ are now in “reduced” form, in the sense that neither move can be applied. We break the situation down into cases.

Case 1. Suppose that $`M_{11}`$ and $`N_{11}`$ are both not equal to $`1`$, so that both $`M`$ and $`N`$ have an entry which is $`11`$ in the $`(v_1,v_2)`$ direction.

If, for each $`l`$, there exists an index $`i_l`$ such that $`i_lc_{11,l}(M)`$ and $`i_lc_{11,l}(N)`$, then, as desired, we can simply extract the variable $`p_{11,(i_l)}`$ from both $`M`$ and $`N`$; in other words, for both $`M`$ and $`N`$, we can find a monomial with the same values of $`a`$ and $`b`$ containing this variable.

If this is not the case, then there exists an $`l`$ for which without loss of generality $`c_{11,l}(M)=\{1\}`$ and $`c_{11,l}(N)=\{0\}`$. Looking at the $`(v_1,w_l)`$ marginal, there exists at least one marginal $`11`$ because of the first condition; consequently, there must exist at least one of these marginals in $`N`$. Since $`c_{11,l}(N)=\{0\}`$, the only other option is that $`1c_{10,l}(N)`$. Similarly, considering the $`(v_2,w_l)`$ marginal, we must have $`1c_{01,l}(N)`$.

Now, we have $`b_{11,0,l}(N)=k>0`$. Since $`b_{11,0,l}(M)=0`$, looking at the $`10`$-count in the $`(v_1,w_l)`$ direction, we must have $`b_{10,0,l}(M)=b_{10,0,l}(N)+k`$. However, looking at the $`00`$-count in the $`(v_2,w_l)`$ direction, it now follows that we must have $`b_{00,0,l}(N)=b_{00,0,l}(M)+k`$, and in particular $`0c_{00,l}(N)`$. This is a contradiction, since we can now apply a move as in Lemma 3.5 to $`N`$, contradicting the assumption that $`N`$ is reduced.

Case 2. Exactly one of $`M_{11}`$ and $`N_{11}`$ is equal to 1.

Suppose without loss of generality that $`M_{11}1`$ and $`N_{11}=1`$. Take any $`i_lc_{11,l}(M)`$; this $`i_l`$ must be in $`c_{10,l}(N)`$ and $`c_{01,l}(N)`$. This means that we can apply a move as in Lemma 3.6 to $`N`$, again contradicting the hypothesis that $`N`$ is reduced.

Case 3. Both $`M_{11}`$ and $`N_{11}`$ are empty.

In this case, it follows immediately that $`b_{10,i,l}(M)=b_{10,i,l}(N)`$ for all $`i`$ and $`l`$ by considering the $`(v_1,w_l)`$ marginals equal to $`(1,i)`$. If $`M_{10}1`$, this means that we can find an $`i_l`$ for all $`l`$ such that this number is nonzero, and we can then pull the corresponding variable out of both $`M`$ and $`N`$. Similarly, if $`M_{01}1`$, we can find a shared variable there, and if both of these are 1 then applying the same argument to $`M_{00}=M`$ and $`N_{00}=N`$ finishes the job.

Our litany of cases has come to an end, completing the proof of Theorem 3.3. Note again that we have not only shown that $`\mu (K_{2,n})=4`$, but also given an explicit generating set in degrees 2 and 4 for $`I_{K_{2,n}}`$. ∎

For $`K_{m,n}`$ where $`m,n>2`$, the answer is less clear. The statement and proof of Theorem 3.3 indicate that for $`m`$ fixed, as $`n`$ gets large, the maximum degree of an element in the Markov basis of the graph ideal of $`K_{m,n}`$ stabilizes. The degree, on the other hand, certainly goes up as $`\text{min}(m,n)`$ does; for instance, there is an element of degree $`2m`$ in the Markov basis of $`K_{m,m}`$, and we have the following result.

###### Proposition 3.7.

Fix $`m2`$. Then for $`n\left(\genfrac{}{}{0pt}{}{m}{2}\right)2^{m2}`$, there is an element of degree $`2^{m1}`$ in the graph ideal of $`K_{m,n}`$.

###### Proof.

Let the vertices of $`K_{m,n}`$ be $`\{v_1,\mathrm{},v_m\}\{w_I\}`$, where $`I=(i_1,\mathrm{},i_m)`$ is an index string of length $`m`$, consisting of precisely two 1’s, and some number of 0’s and 2’s. There are precisely $`\left(\genfrac{}{}{0pt}{}{m}{2}\right)2^{m2}`$ such strings.

Specify the marginals as follows: between $`v_j`$ and $`w_I`$, insist upon $`i_j`$ marginals of $`11`$, $`2i_j`$ marginals of $`01`$, $`2^{m2}i_j`$ marginals of $`10`$, and $`2^{m2}2+i_j`$ marginals of $`00`$. What this means is that exactly two variables with coordinate $`w_I`$ equal to 1 occur, and that the sum of the $`v`$-coordinates (considered as vectors) is precisely $`I`$; it furthermore specifies that each of 0 and 1 occurs $`2^{m2}`$ times in each $`v_j`$-coordinate.

For each $`w_I`$, there are only two ways to express the vector $`I`$ as the sum of two 0-1 vectors. Since we consider all index strings $`I`$, we obtain that for each diamond in the natural Boolean partial order of binary strings of length $`m`$, either the top and bottom elements are in the set of $`v`$-coordinates of table entries, or the middle two entries are. By an easy induction, it follows that the set of $`v`$-coordinates, which numbers only $`2^{m1}`$, must consist of either all strings with an even number of 1’s, or all strings with an odd number of 1’s. From here, we can easily compute the $`w`$-coordinates of each of these entries.

These resulting tables are the only two which satisfy these marginals, and thus their difference, an element of degree $`2^{m1}`$, must be in the Markov basis of $`I_{K_{m,n}}`$ as desired. For all $`n\left(\genfrac{}{}{0pt}{}{m}{2}\right)2^{m2}`$ there is a move of degree $`2^{m1}`$ by Corollary 4.2. ∎

We suspect that the following conjecture, an extension of the result for $`K_{2,n}`$, holds.

###### Conjecture 3.8.

The graph ideal for $`G=K_{m,n}`$ is generated in degree at most $`2^{\mathrm{min}\{m,n\}}`$.

## 4 Combinatorial Classification of Minimal Generators of Low Degree

In this section, we give algorithms for computing all generators of a given degree in the graph ideal $`I_G`$. For degrees two and three, we give an explicit combinatorial characterization of these generators, giving a generating set which generates $`I_G`$ in degree less than or equal to 3; for arbitrary degree $`d`$, we categorize these generators as pullbacks of a distinguished generator in the graph ideal of a fundamental graph $`X_d`$. The key lemma is the following, relating generators in $`I_G`$ to generators in a minor of $`G`$.

###### Lemma 4.1.

Let $`G`$ be a graph, and let $`f=\mathrm{\Pi }p_{I_j}\mathrm{\Pi }p_{I_k}`$ be a binomial contained in $`I_G`$. Then we have the following.

(a) If $`v_i`$ corresponds to a column where all the index strings $`I_j`$ have the same value, then $`f`$ is a minimal generator if and only if $`\stackrel{~}{f}`$ is a minimal generator of the graph ideal $`G\backslash v_i`$, where $`\stackrel{~}{f}`$ is the natural image of $`f`$ with the column $`v_i`$ deleted from each index string.

(b) If $`v_i`$ and $`v_j`$ are adjacent and correspond to columns where for each index string $`I_j`$ or $`I_k`$, the value of that string in each column is identical, then $`f`$ is a minimal generator if and only if $`\stackrel{~}{f}`$ is a minimal generator, where $`\stackrel{~}{f}`$ is the natural image of $`f`$ with the two columns $`v_i`$ and $`v_j`$ fused. Here, $`\stackrel{~}{f}`$ is an element of the graph ideal of $`G`$ with those two vertices fused.

(c) Suppose $`v_i`$ and $`v_j`$ are any two vertices and correspond to columns where for each index string $`I_j`$ or $`I_k`$, the value of that string in each column is identical. In this case, if $`f`$ is a minimal generator of the graph ideal of $`G`$, then $`\stackrel{~}{f}`$ is a minimal generator of the graph ideal of $`G`$ with those two vertices fused.

###### Proof.

In each case, a decomposition of $`\stackrel{~}{f}`$ into generators of lower degree can be lifted via the obvious method to a decomposition of $`f`$. In (a), this is simply inserting the shared value of $`v_i`$ into each index string to form a valid index string for $`G`$; in (b) and (c), this is simply duplicating the value of each index string in the obvious manner.

In cases (a) and (b), any decomposition of $`f`$ must necessarily satisfy the property that each binomial used has the property in question, by considering in (a) any marginal containing $`v_i`$ and in (b) the marginal corresponding to the edge $`v_iv_j`$. Therefore, a decomposition of $`f`$ naturally yields a decomposition of $`\stackrel{~}{f}`$, so if $`\stackrel{~}{f}`$ is a minimal generator $`f`$ must be also. ∎

This lemma has a corollary legitimizing our notion of minor.

###### Corollary 4.2.

If $`H`$ is a minor of $`G`$, then $`\mu (H)\mu (G)`$.

###### Proof.

It suffices to show $`\mu (H)\mu (G)`$ if $`H`$ is obtained from $`G`$ by a single vertex deletion or edge contraction. However, if it is obtained by a vertex deletion, then by part (a) of Lemma 4.1, every minimal generator of a given degree in $`I_H`$ lifts to a minimal generator of the same degree in $`I_G`$. Similarly, part (b) of Lemma 4.1 guarantees that $`\mu (H)\mu (G)`$ if $`H`$ is obtained from $`G`$ via an edge contraction. ∎

A natural extension of this is the following, which agrees with the data in Section 2, but which we have been unable to prove.

###### Conjecture 4.3.

If $`H`$ is obtained from $`G`$ by deleting an edge, then $`\mu (H)\mu (G)`$.

This set of minimal generators comes with a group action. In particular, the group $`(/2)^n`$ acts naturally on $`[p_I]`$, via the element $`(c_1,\mathrm{},c_n)`$ sending a variable $`p_{i_1\mathrm{}i_n}`$ to $`p_{j_1,\mathrm{},j_n}`$, where $`j_r=i_r+c_r`$; the sum is evaluated in $`/2`$. This action consists merely of flipping 0’s and 1’s in some positions.

Furthermore, the automorphism group $`\text{Aut}(G)`$ acts naturally on $`[p_I]`$ as well, by permuting the indices according to the permutation of the vertices of the graph, so we have a natural action of $`(/2)^n\text{Aut}(G)`$ on $`[p_I]`$. This action maps $`I_G`$ onto itself; we make the following natural definition.

###### Definition 4.4.

Two generators are equivalent if they lie in the same orbit of $`[p_I]`$ under the action of $`(/2)^n\text{Aut}(G)`$.

If two generators of graph ideals $`I_{G_1}`$ and $`I_{G_2}`$ reduce to equivalent generators in a basic graph $`H`$ by means of the above manipulations, we say that they are weakly similar. If they furthermore reduce to equivalent generators using only manipulations of type (a) and (b), we say that they are strongly similar. We are now prepared to define the object pivotal in our categorization of generators of degree $`d`$.

###### Definition 4.5.

Fix a degree $`d2`$. The fundamental graph $`X_d`$ has vertex set $`(S_i,T_i)`$, where $`S_i`$ and $`T_i`$ are subsets of $`\{1,\mathrm{},d\}`$ with cardinalities $`|S_i|=|T_i|d/2`$, and if $`|S_i|=d/2`$ then $`1S_i`$. Two vertices $`(S_1,T_1)`$ and $`(S_2,T_2)`$ are connected by an edge if $`|S_1S_2|=|T_1T_2|`$.

To this fundamental graph is associated a distinguished element of $`I_{X_d}`$.

###### Definition 4.6.

Fix a degree $`d2`$. Then the distinguished generator $`f_dI_{X_d}`$ is the binomial

$$\left[\begin{array}{c}I_1\\ \mathrm{}\\ I_d\end{array}\right]\left[\begin{array}{c}J_1\\ \mathrm{}\\ J_d\end{array}\right],$$

where $`I_{ji}=1`$ if $`jS_i`$ and 0 otherwise, and similarly $`J_{ji}=1`$ if $`jT_i`$ and 0 otherwise.

It is clear that the distinguished generator is actually in $`I_{X_d}`$, since for all adjacent $`v_i`$ and $`v_j`$, the number of 11-marginals in $`I`$ is equal to $`S_iS_j`$, while the number of 11-marginals in $`J`$ is equal to $`T_iT_j`$. By definition of $`X_d`$, these are equal, and furthermore, the number of 11-marginals determines the numbers of all other marginals (along with the numbers of 1’s in each column of $`I`$ and $`J`$, which are of course identical.)

###### Example 4.7.

The fundamental graph $`X_2`$ has two vertices $`(1,1)`$ and $`(1,2)`$ which are not connected by an edge. The distinguished generator of $`I_{X_2}`$ is the binomial

$$\left[\begin{array}{cc}1& 1\\ 0& 0\end{array}\right]\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

which is just as $`2\times 2`$ determinant. The fundamental graph $`X_3`$ has nine vertices which are $`(1,1),(1,2),\mathrm{},(3,3)`$. Two vertices $`(i,j)`$ and $`(k,l)`$ are connected if and only if $`ik`$ and $`jl`$. Each vertex has degree four: $`X_3`$ is the edge graph of the 4-polytope $`\mathrm{\Delta }_2\times \mathrm{\Delta }_2`$, the product to two triangles pictured in Figure 1. Note the six triangular prisms which appears as minors of $`X_3`$. The fundamental generator of $`I_{X_3}`$ is the binomial

$$\left[\begin{array}{ccccccccc}1& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 1\end{array}\right]\left[\begin{array}{ccccccccc}1& 0& 0& 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 0& 1\end{array}\right].$$

With these definitions, we can formulate the main theorem of this section, categorizing all generators of degree $`d`$.

###### Theorem 4.8.

Let $`G`$ be any graph. Then the minimal generators of degree $`d`$ in $`I_G`$ can be enumerated by the following procedure.

1. Consider all graph homomorphisms $`\varphi `$ from minors $`H`$ of $`G`$ to $`X_d`$.
2. Determine if the natural image of the fundamental generator $`\stackrel{~}{f_d}`$ is a minimal generator on the image subgraph.
3. If so, consider the pullback $`\varphi ^{}\stackrel{~}{f_d}`$, a binomial of degree $`d`$ in $`I_G`$. We can pull this back to $`H`$ using Lemma 4.1 part (b) and (c), and then to $`G`$ using Lemma 4.1 part (a) and (b).

A graph homomorphism $`GH`$ is simply a map $`\varphi `$ from vertices of $`G`$ to vertices of $`H`$ such that if $`u`$ and $`v`$ are adjacent in $`G`$, $`\varphi (u)`$ and $`\varphi (v)`$ are adjacent in $`H`$. Note that since we have used Lemma 4.1 part (c), the pullback will not always be a minimal generator but the set of moves calculated in this way contains all minimal generators $`I_G`$ of degree $`d`$.

###### Proof.

Suppose we have a generator $`f`$ of degree $`d`$ in $`I_G`$, written in tableau notation as

$$\left[\begin{array}{c}I_1\\ \mathrm{}\\ I_d\end{array}\right]\left[\begin{array}{c}J_1\\ \mathrm{}\\ J_d\end{array}\right],$$

where $`I`$ and $`J`$ are 0-1 matrices. Each column of $`I`$ has the same number of 1’s as the corresponding column of $`J`$. If this number is either 0 or $`d`$, we can delete that vertex via Lemma 4.1 (a) to obtain an equivalent generator in a minor of $`G`$, proving the theorem by induction.

Therefore, by flipping 0 with 1 if necessary, we can assume that each column has at most $`d/2`$ 1’s, and if it has $`d/2`$ 1’s then $`I_i`$ has a 1 in that column. To each vertex $`v_i`$ associate the pair $`(S_i,T_i)`$, where $`jS_i`$ if $`I_j`$ has a 1 in the column corresponding to $`v_i`$, and $`jT_i`$ if $`J_j`$ has a 1 in that column. If two adjacent vertices have the same pair, we can contract the edge between them via Lemma 4.1 (b) to again obtain an equivalent generator in a minor of $`G`$.

If this is not the case, then we claim that the map given by sending $`v_i`$ to the vertex $`(S_i,T_i)`$ in $`X_d`$ is a graph homomorphism. Indeed, all that we need to check is that if $`v_i`$ and $`v_j`$ are connected by an edge, $`S_iS_j=T_iT_j`$ (and it is not the case that $`(S_i,T_i)=(S_j,T_j)`$, which is true since no two adjacent vertices have the same pair.) But this must be true, since each is just the number of 11-marginals along the edge $`v_iv_j`$ in the corresponding tables $`I`$ and $`J`$, which are equal since $`f`$ is in $`I_G`$.

Furthermore, this map fuses two vertices $`v_i`$ and $`v_j`$ only if the corresponding columns of $`I`$ and of $`J`$ are identical. Therefore, by Lemma 4.1 (c), the image of $`f`$ in $`I_R`$, where $`R`$ is the image subgraph of $`X_d`$, must be a minimal generator of $`X_{I_R}`$. However, this generator is precisely the natural image of the distinguished generator in the graph ideal $`I_R`$. If this is irreducible, then $`f`$ is produced by the procedure in Theorem 4.8, which we have just done in reverse. If not, then $`f`$ cannot be a minimal generator by the contrapositive of Lemma 4.1. ∎

In this manner, we have reduced the computation of all generators of degree $`d`$ to the process of determining which images of the distinguished generator in subgraphs of $`X_d`$ are minimal generators, and of enumerating graph homomorphisms from $`G`$ to $`X_d`$. While the problem of computing graph homomorphisms is a difficult one, we can use symmetry techniques to greatly aid us in many cases. Theorem 4.8 also divulges which generators are weakly similar: those whose corresponding graph homomorphisms have images which are isomorphic subgraphs of $`X_d`$.

We now apply Theorem 4.8 to degrees 2 and 3. Consider first generators of degree 2. The fundamental graph $`X_2`$ has two vertices, $`(1,1)`$ and $`(1,2)`$, which are not connected by an edge. Given a minor of $`G`$, it has a homomorphism onto $`X_2`$ if and only if there are no edges between the vertices mapped to $`(1,1)`$ and the vertices mapped to $`(1,2)`$. In this case the homomorphisms correspond to partitions of the vertices into $`V_1`$ and $`V_2`$. Extracting the definition of minor yields the following Corollary.

###### Corollary 4.9.

Let $`G`$ be a graph. Then equivalence classes of generators of degree 2 of $`I_G`$ correspond to partitions $`V_1V_2V_3`$, where there are no edges between $`V_1`$ and $`V_2`$. The generator corresponding to this is precisely

$$\left[\begin{array}{cc}101& \\ 011& \end{array}\right]\left[\begin{array}{cc}111& \\ 001& \end{array}\right],$$

where the three columns correspond to $`V_1,V_2`$, and $`V_3`$.

Readers familiar with the study of graphical models and their induced independence statements will recognize this as a theorem which says that the only independence statements induced by a graphical model are the global independence statements. See, for example .

Next, we turn our attention to the case of generators of degree 3, using the methods of Theorem 4.8 to obtain a combinatorial classification of all such cubic minimal generators of $`I_G`$. The fundamental graph $`X_3`$ has nine vertices $`\{(1,1),\mathrm{},(3,3)\}`$, with $`(i,j)`$ connected to $`(k,l)`$ if $`ik`$ and $`jl`$. By direct computation, the image of the fundamental generator $`d_3`$ in $`I_R`$, $`R`$ a subgraph of $`X_3`$, is a minimal generator if and only if $`R`$ contains one of the six triangular prism subgraphs of $`X_3`$. Therefore, we can classify cubic generators by finding all homomorphisms from minors of $`G`$ to the fundamental graph $`X_3`$ whose image contains a triangular prism. In particular, if no such homomorphism exists, then $`I_G`$ cannot have a generator of degree 3. This yields the following corollary.

###### Corollary 4.10.

For all $`n`$, the graph ideal $`I_{K_n}`$ has no minimal generators of degree 3.

###### Proof.

The only minors of $`K_n`$ are copies of $`K_m`$ for $`mn`$. Furthermore, all homomorphic images of complete graphs are again complete graphs (indeed, of the same degree.) The only complete graphs occurring in $`X_3`$ are $`K_2`$ and $`K_3`$, neither of which contains a triangular prism. ∎

Corollary 4.10 shows why edge deletion does not behave well with respect to the graph ideal $`I_G`$ and its Markov basis; this operation obviously can introduce elements of new degrees, since there exist graphs with cubic minimal generators, and every graph can be obtained from a complete graph by edge deletion. The same technique can be used to show that there are no minimal generators of degree 5 in the graph ideal $`I_{K_n}`$, since the largest clique in $`X_5`$ has size 5, and the distinguished generator cannot be minimal in the graph ideal of these subgraphs since in fact there are no minimal generators of degree 5 in $`K_i`$ for $`i5`$.

In addition to the description of Theorem 4.8, we can obtain a more straightforward combinatorial characterization of minimal generators of degree 3 in graph ideals. We start with a pair of definitions.

###### Definition 4.11.

Let $`G`$ be any graph. Then the 3-coloring graph $`C_3(G)`$ has vertices equal to the set of proper 3-colorings of $`G`$. Two 3-colorings are connected by an edge if one can be obtained from the other by the following (reversible) procedure: pick a color $`i\{1,2,3\}`$, pick a connected component of the induced subgraph consisting of all vertices with colors not equal to $`i`$, and switch the other two colors on this component.

###### Definition 4.12.

A graph $`G`$ is 3-rigid if the coloring space $`C_3(G)`$ is disconnected.

The crucial example of a 3-rigid graph is the same triangular prism that arose in the analysis of degree 3 via Theorem 4.8. This graph is 3-rigid, since there are only two proper 3-colorings up to permutation of the colors: one triangle $`(v_1,v_2,v_3)`$ is colored $`(1,2,3)`$, and the other triangle $`(w_1,w_2,w_3)`$ must be colored either $`(2,3,1)`$ or $`(3,1,2)`$. Here, the vertex labels are chosen so that $`v_i`$ is adjacent to $`w_i`$. It is easy to check that these colorings lie in different connected components of $`C_3(G)`$; the connected component of each consists of the colorings obtained from it by permutation of the colors.

We now present a complete description of cubic generators of $`G`$ based on these combinatorial objects.

###### Proposition 4.13.

Let $`G`$ be any graph. Then we can enumerate the (equivalence classes of) cubic minimal generators of the graph ideal $`I_G`$ as follows.

(a) Find all the 3-rigid minors of $`G`$.

(b) For each such 3-rigid minor $`H`$, consider all of the connected components of the 3-coloring graph of $`H_3`$. For each connected component, pick a representative 3-coloring $`R_i`$.

(c) For each $`R_i`$, $`i>1`$, take the element

$$f=\left[\begin{array}{ccc}a_1& & \\ a_2& & \\ a_3& & \end{array}\right]\left[\begin{array}{ccc}b_1& & \\ b_2& & \\ b_3& & \end{array}\right],$$

where $`a_{jk}=1`$ if either the vertex $`k`$ of $`G`$ is deleted in obtaining $`H`$ or its image in $`H`$ is colored with color $`j`$ in $`R_1`$, and $`b_{jk}=1`$ if either $`k`$ is deleted or its image in $`H`$ is colored with color $`j`$ in $`R_i`$.

Each of these elements $`f`$ is a minimal generator of $`I_G`$ in degree 3, and these elements together with the quadratic elements described above generate $`I_G`$ up to degree 3.

###### Proof.

Suppose we have a cubic minimal generator of $`I_G`$, given by

$$f=\left[\begin{array}{ccc}a_1& & \\ a_2& & \\ a_3& & \end{array}\right]\left[\begin{array}{ccc}b_1& & \\ b_2& & \\ b_3& & \end{array}\right].$$

We construct two 3-colorings $`C_A`$ and $`C_B`$ of a minor of $`G`$ as follows. For the vertex $`v_j`$, consider the $`j`$-th column of $`A`$ and $`B`$. If this consists of all 1’s or all 0’s, delete $`v_j`$. If not, exchange 0’s and 1’s if necessary so that it has exactly one 1. Then, in $`C_A`$ (resp. $`C_B`$), color $`v_j`$ with the position in which this 1 appears in $`A`$ (resp. B).

Next, if two adjacent vertices have the same color in $`A`$ (equivalent to having the same color in $`B`$ by counting 11-marginals along this edge), then contract that edge. What remains is two proper 3-colorings of a minor $`H`$, and when these 3-colorings are converted to a binomial in $`I_G`$ via the method in part (c), we recover precisely the element $`f`$. By Lemma 4.1, the image $`\stackrel{~}{f}`$ in $`I_H`$ is a minimal generator if and only if $`f`$ is a minimal generator of $`I_G`$.

We claim that the image $`\stackrel{~}{f}`$ is a minimal generator of $`I_H`$, i.e. inexpressible as a sum of multiples of quadrics, if and only if $`C_A`$ and $`C_B`$ are in different connected components of $`C_3(H)`$. Indeed, consider a multiple of a binomial generator, say

$$g=\left[\begin{array}{ccc}a_1& & \\ a_2& & \\ a_3& & \end{array}\right]\left[\begin{array}{ccc}c_1& & \\ c_2& & \\ a_3& & \end{array}\right].$$

If we convert the two monomials of $`g`$ into colorings, the same set of vertices will have color 3 in these colorings. Therefore, the difference between these colorings consists of changing colors from 1 to 2 or vice versa. The only way this can be done while preserving the properness of the coloring is if the change consists of switching the colors 1 and 2 on some connected components of the induced subgraph of $`H`$ consisting of vertices not colored 3. Therefore, when we add a multiple of a binomial generator, we end 1 up with an element corresponding to a 3-coloring in the same component of $`C_3(H)`$, and any two elements connected by an edge in $`C_3(H)`$ differ by a multiple of a binomial generator.

Consequently, the colorings $`C_A`$ and $`C_B`$ are in the same component of $`C_3(H)`$ if and only if $`\stackrel{~}{f}`$ is not expressible as the sum of multiples of binomials in $`I_H`$, which is equivalent to $`\stackrel{~}{f}`$ being a minimal generator of $`I_H`$, as desired. ∎

Classifying 3-rigid graphs is an interesting problem; the graph $`C_3(G)`$ has been studied in connection with the problem of picking a random 3-coloring of a graph . Indeed, the flip interchanging two colors on a connected component is precisely the move used in the Wang-Swendsen-Kotecký algorithm to pick a random $`k`$-coloring of a graph, and this scheme has ties to mathematical physics . There are simple operations to produce 3-rigid graphs from other ones, but the triangular prism seems to be the only 3-rigid graph without a proper 3-rigid minor.

This method, paralleling Theorem 4.8, can be extended to higher degrees. However, it rapidly becomes unwieldy, as the vertices can now be colored with sets of $`d/2`$ colors, and the moves are more complicated, consisting of all moves keeping one of the colors fixed. For instance, the fundamental graph $`X_4`$ has 34 vertices and understanding the homomorphisms to this graph seems difficult.

## 5 Algebraic Degree of Forests

A recent series of results gave a very thorough description of the family of ideals of decomposable models . A special case of these results is the following fundamental theorem.

###### Theorem 5.1.

The ideal $`I_G`$ is minimally generated by quadrics if and only if $`G`$ is a forest. In this case, the set of quadratic squarefree binomials in $`I_G`$ forms a Gröbner basis with respect to the reverse lexicographic term order with $`p_{0\mathrm{}0}p_{0\mathrm{}01}\mathrm{}p_{1\mathrm{}1}`$.

Sturmfels  posed the natural follow-up problem of calculating the degree of the toric ideal $`I_G`$. The degree of the toric ideal is interesting in statistics because it provides a natural upper bound for the maximum likelihood degree of the toric ideal . In this section we give combinatorial formulae for the degree of the graph model ideal $`I_G`$ when $`G`$ is a forest. As the maximum likelihood degree of a forest is always 1, we see that the degree can be arbitrarily far from the maximum likelihood degree. To perform these degree computations, we first recall a result about the degree of a general toric ideal. This result can be found in .

###### Theorem 5.2.

Let $`A`$ be a $`d\times n`$ matrix whose toric ideal $`I_A`$ is homogeneous in the standard $``$-grading. Then the degree of the ideal $`I_A`$ ($`=`$ degree of the projective toric variety defined by $`I_A`$) is equal to the normalized volume of the lattice polytope $`Q=\mathrm{conv}(A)`$.

Henceforth, the normalized volume of a lattice polytope $`Q`$ will be denoted $`Vol(Q)`$. This theorem reduces the problem of calculating degree to computing the normalized volume of polytope. We now record some some basic facts about the polytope $`P_G`$ when the underlying graph is a forest.

###### Lemma 5.3.

The polytope $`P_G`$ has dimension equal to the sum of the number of vertices and the number of edges of the graph (this is true for any graph). There are precisely $`4|E(G)|+2|Iso(G)|`$ facets of $`P_G`$ when $`G`$ is a forest. If the variables in marginal space are labelled $`y_{i_j,i_k}^{(j,k)}`$ for the variables coming from an edge and $`y_{i_l}^{(l)}`$ for the variables coming from an isolated vertex, then the facets are given by the inequalities

$$y_{i_j,i_k}^{(j,k)}0\text{ and }y_{i_l}^{(l)}0.$$

###### Proof.

The dimension formula appears in . The polyhedral results are a direct consequence of the closed form expressions for maximum likelihood estimates in decomposable models in . ∎

The following lemma implies that to compute the degree of $`I_G`$ when $`G`$ is a forest, one need only describe a formula which is valid for trees. Furthermore, this lemma is important for carrying out the recursive computations implied by Theorem 5.5.

###### Lemma 5.4.

Let $`G`$ be a graph with a partition of the vertices $`\{V_1,V_2\}`$ such that there is no edge in $`G`$ between the $`V_1`$ and $`V_2`$. Let $`G_1`$ and $`G_2`$ be the corresponding induced subgraphs. Let $`d_1`$ and $`d_2`$ be the corresponding dimensions of the polytopes $`P_{G_1}`$ and $`P_{G_2}`$; that is, $`d_i=|V_i|+|E(G_i)|`$ . Then we have

$$Vol(P_G)=\left(\genfrac{}{}{0pt}{}{d_1+d_2}{d_1}\right)Vol(P_{G_1})Vol(P_{G_2}).$$

###### Proof.

With these restrictions on the graph $`G`$, we have $`P_G=P_{G_1}\times P_{G_2}`$. Equation 5.4 is then the usual formula for the normalized volume of the direct product in terms of the normalized volumes of the components of the product. ∎

We now come to the main theorem of this section.

###### Theorem 5.5.

Let $`G`$ be a tree with $`n`$-vertices. Then the degree of the toric ideal $`I_G`$ can be calculated by the formula

$$deg(I_G)=\frac{1}{2}\underset{eE(G)}{}deg(I_{Ge})$$

where the notation $`Ge`$ denotes the graph $`G`$ with the edge $`e`$ removed.

###### Proof.

As previously indicated, we prove the theorem by calculating the volume of the corresponding polytope $`P_G`$. Theorem 5.1 implies that the pulling triangulation of $`P_G`$ induced by the reverse lexicographic term order above is unimodular. This in turn, implies that the normalized volume of $`P_G`$ is equal to the sum of the normalized volumes of the facets of $`P_G`$ which do not contain the vertex indexed by the variable $`p_{1\mathrm{}1}`$ (see  for all the definitions and relevant theory). This is where the polyhedral description of $`P_G`$ when $`G`$ is a forest becomes essential. We see from the polyhedral characterization that there are exactly $`n1`$ facets of $`P_G`$ which do not contain this “last” vertex, and that they are indexed by the edges of $`G`$. We will show that the normalized volume of the facet $`F_e`$ of $`P_G`$ which is indexed by the edge $`e`$ has volume precisely $`\frac{1}{2}Vol(P_{Ge})`$ which will complete the proof.

There are two cases to consider: either the edge in question has one node a leaf or not (the case of the graph on two vertices with a lone edge is clear, by a direct calculation). We will handle the two cases separately.

*Case 1*: We may suppose without loss of generality that our edge $`e`$ is $`\{1,2\}`$, the vertex 1 is a leaf and the vertex $`2`$ has the edge $`\{2,3\}`$ incident to it. Then the matrix whose columns correspond to the vertices of $`P_G`$ has the top eight rows which look like

$$\left(\begin{array}{cccccccc}1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\end{array}\right)$$

with this $`8\times 8`$ block repeated $`2^{n3}`$ times across the first eight rows. We claim that the facet which corresponds to the inequality $`y_{1,1}^{(1,2)}0`$ (corresponding to the fourth row of the above matrix) has volume equal to $`\frac{1}{2}Vol(P_{G\{1,2\}})`$. Note the the vertices of $`P_G`$ which lie on this facet are precisely the $`32^{n2}`$ vertices of $`P_G`$ which have a zero in the fourth row. First we show that this facet is naturally isomorphic to a sub-configuration of $`P_{G\{1,2\}}`$. Consider the matrix $`A_{G\{1,2\}}`$ whose columns give the vertices of $`P_{G\{1,2\}}`$. This matrix has two fewer rows than the matrix $`A_G`$ above and is almost the same: its first six rows look like

$$\left(\begin{array}{cccccccc}1& 1& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\end{array}\right).$$

To show the natural isomorphism mentioned above, it suffices to show that there is a unimodular linear transformation from the first six columns of the first matrix above to the first six columns of the second matrix above. Such a linear transformation is obtained by replacing the first row by the sum of the first and second rows, and then deleting the second and fourth rows. We can delete the second and fourth rows because they are linear combinations of other rows and hence do not change the polyhedral description. Such a transformation is clearly unimodular.

Now that we have shown that our configuration of $`32^{n2}`$ points sits naturally inside $`P_{G\{1,2\}}`$, we wish to compute its volume. For this, we show that there is a hyperplane which divides $`P_{G\{1,2\}}`$ into two congruent pieces, one of which is the convex hull of our new configuration of $`32^{n2}`$ points. This hyperplane is given by the equation

$$y_0^{(1)}y_1^{(1)}+y_{0,0}^{(2,3)}+y_{0,1}^{(2,3)}y_{1,0}^{(2,3)}y_{1,1}^{(2,3)}=0.$$

Note that exactly $`2^{n1}`$ vertices of $`P_{G\{1,2\}}`$ lie on this hyperplane (these are the ones corresponding to the middle four columns of the submatrix of $`A_{G\{1,2\}}`$ displayed above) and the remaining $`2^{n1}`$ vertices are split equally on each side of the hyperplane. In particular, all of the vertices from our configuration of $`32^{n2}`$ points lie on the nonnegative side of this hyperplane and the remaining $`2^{n2}`$ points are on the negative side. Furthermore, there is a natural reflexive symmetry across this hyperplane. To complete the proof, we must show more: not only is the point configuration naturally “cut in half” by this hyperplane, but so is the polytope $`P_{G\{1,2\}}`$. This follows from a direct computation with the eight points listed above. We performed the computation using the program `PORTA` .

*Case 2*: The argument is very similar to case 1; we will sketch the relevant details. We may assume that our edge is the edge $`\{2,3\}`$. Since neither 2 nor 3 is a leaf we may assume $`G`$ also contains the edges $`\{1,2\}`$ and $`\{3,4\}`$. With these conditions, the first 12 rows of our matrix looks like

$$\left(\begin{array}{cccccccccccccccc}1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 1\\ 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1\end{array}\right)$$

with this block repeated $`2^{n4}`$ times. We wish to show that the facet defined by the inequality $`y_{1,1}^{(2,3)}0`$ (corresponding to the eighth row in the above matrix) has volume equal to $`\frac{1}{2}Vol(P_{G\{2,3\}})`$. The vertices which lie on this facet are precisely the $`32^{n2}`$ vertices with a zero in the eighth row in this matrix representation. First we show that this facet naturally appears as a sub-configuration of $`P_{G\{2,3\}}`$. This can be achieved by applying a unimodular transformation to the configuration: the key point is that once we restrict attention to the facet, the middle 4 rows of the above configuration can be written as linear combinations of the other rows and hence are redundant in terms of the polyhedral description.

Now we show that there is a hyperplane which divides the polytope $`P_{G(2,3)}`$ in half. This is just the hyperplane given by

$$y_{0,0}^{(1,2)}y_{0,1}^{(1,2)}+y_{1,0}^{(1,2)}y_{1,1}^{(1,2)}+y_{0,0}^{(3,4)}+y_{0,1}^{(3,4)}y_{1,0}^{(3,4)}y_{1,1}^{(3,4)}=0.$$

Note that our configuration of $`32^{n2}`$ points are precisely the points on the nonnegative side of this hyperplane. Furthermore, there is a natural reflexive symmetry across the hyperplane. A direct calculation shows that this hyperplane not only separates the point configuration, but also divides the polytope into two symmetric pieces with the the desired integral points as vertices. Thus we deduce the desired equation of volumes. ∎

For some special families of trees we use this recurrence relation to deduce simple formulae for the degree. These appear in the following corollaries.

###### Corollary 5.6.

Let $`K_{1,n}`$ denote a star graph with $`n`$ leaves. Then $`deg(I_{K_{1,n}})=(n!)^2`$.

###### Proof.

Removing any edge of the graph $`K_{1,n}`$ produces the graph consisting of the disjoint union of a $`K_{1,n1}`$ and an isolated point. Hence from theorem 5.5 and lemma 5.4 we deduce that

$$deg(I_{K_{1,n}})=n\frac{1}{2}\left(\genfrac{}{}{0pt}{}{2n}{1}\right)deg(I_{K_{1,n1}})=n^2deg(I_{K_{1,n1}}).$$

Since $`deg(I_{K_{1,1}})=1`$ we have the desired result. ∎

###### Corollary 5.7.

Let $`T_n`$ denote the graph of the $`n`$-chain and $`d_n=deg(I_{T_n})`$. Then $`d_n`$ satisfies the recurrence

$$d_{n+1}=\frac{1}{2}\underset{i=1}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{2n}{2i1}\right)d_id_{n+1i}$$

with $`d_1=1`$. Furthermore, we have the equality of generating functions

$$\underset{n=1}{\overset{\mathrm{}}{}}\frac{d_n}{(2n1)!}x^{2n1}=\sqrt{2}\mathrm{tan}(\frac{x}{\sqrt{2}}).$$

###### Proof.

The recurrence relation 5.7 follows immediately from the formula in Theorem 5.5 and by applying Lemma 5.4 to the graph consisting of two disjoint chains of length $`i`$ and $`n+1i`$.

To deduce the equality of generating functions, let $`y=\frac{1}{2}_{n=1}^{\mathrm{}}\frac{d_n}{(2n1)!}x^{2n1}`$. The recurrence relation implies that $`2y^{}2=y^2`$. Solving the differential equation yields the desired formula. ∎

The recurrence relation and generating function in the case of the $`n`$-chain also appears in a paper by Poupard , but we do not know how to show that the objects we are counting (simplices in a regular unimodular triangulation) are in bijection with the objects she was counting (types of binary trees).

## 6 Acknowledgements

Mike Develin was supported in part by an NSF Graduate Research Fellowship and by the American Institute of Mathematics. Seth Sullivant was supported by an NSF Graduate Research Fellowship.