Markov Bases of Binary Graph Models

This paper is concerned with the topological invariant of a graph given by the maximum degree of a Markov basis element for the corresponding graph model for binary contingency tables. We describe a degree four Markov basis for the model when the underlying graph is a cycle and generalize this result to the complete bipartite graph K_2,n. We also give a combinatorial classification of degree two and three Markov basis moves as well as a Buchberger-free algorithm to compute moves of arbitrary given degree. Finally, we compute the algebraic degree of the model when the underlying graph is a forest.AMS Subject Classification: 05C99, 13P10, 62Q05.     

Constructing orthogonal pandiagonal Latin squares and panmagic squares from modular n‐queens solutions

In this article, we show how to construct pairs of orthogonal pandiagonal Latin squares and panmagic squares from certain types of modular n‐queens solutions. We prove that when these modular n‐queens solutions are symmetric, the panmagic squares thus constructed will be associative, where for an n × n associative magic square A = (a_ij), for all i and j it holds that a_ij + an?i?1,n?j?1 = c for a fixed c. We further show how to construct orthogonal Latin squares whose modular difference diagonals are Latin from any modular n‐queens solution. As well, we analyze constructing orthogonal pandiagonal Latin squares from particular classes of non‐linear modular n‐queens solutions. These pandiagonal Latin squares are not row cyclic, giving a partial solution to a problem of Hedayat. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 221–234, 2007     

Atomic Latin squares of order eleven

A Latin square is pan‐Hamiltonian if the permutation which defines row i relative to row j consists of a single cycle for every i ≠ j. A Latin square is atomic if all of its conjugates are pan‐Hamiltonian. We give a complete enumeration of atomic squares for order 11, the smallest order for which there are examples distinct from the cyclic group. We find that there are seven main classes, including the three that were previously known. A perfect 1‐factorization of a graph is a decomposition of that graph into matchings such that the union of any two matchings is a Hamiltonian cycle. Each pan‐Hamiltonian Latin square of order n describes a perfect 1‐factorization of K_n,n, and vice versa. Perfect 1‐factorizations of K_n,n can be constructed from a perfect 1‐factorization of K_n+1. Six of the seven main classes of atomic squares of order 11 can be obtained in this way. For each atomic square of order 11, we find the largest set of Mutually Orthogonal Latin Squares (MOLS) involving that square. We discuss algorithms for counting orthogonal mates, and discover the number of orthogonal mates possessed by the cyclic squares of orders up to 11 and by Parker's famous turn‐square. We find that the number of atomic orthogonal mates possessed by a Latin square is not a main class invariant. We also define a new sort of Latin square, called a pairing square, which is mapped to its transpose by an involution acting on the symbols. We show that pairing squares are often orthogonal mates for symmetric Latin squares. Finally, we discover connections between our atomic squares and Franklin's diagonally cyclic self‐orthogonal squares, and we correct a theorem of Longyear which uses tactical representations to identify self‐orthogonal Latin squares in the same main class as a given Latin square. © 2003 Wiley Periodicals, Inc.     

Markov bases and subbases for bounded contingency tables

In this paper we study the computation of Markov bases for contingency tables whose cell entries have an upper bound. It is known that in this case one has to compute universal Gröbner bases, and this is often infeasible also in small- and medium-sized problems. Here we focus on bounded two-way contingency tables under independence model. We show that when these bounds on cells are positive the set of basic moves of all 2 × 2 minors connects all tables with given margins. We also give some results about bounded incomplete table and we conclude with an open problem on the necessary and sufficient condition on the set of structural zeros so that the set of basic moves of all 2 × 2 minors connects all incomplete contingency tables with given positive margins.     

An extension of 0-1 laws

Let σ be a first-order sentence about graphs. For n ? ω let n^α, α ? 0, be the edge probability for the random graph on n vertices, and let pr(σ, n) be the probability that the random graph on n vertices, satisfies σ. If σ and σ satisfy certain conditons then either pr(σ,n)～βn^?γ for some β > 0 and γ ?0, or pr(σ,i)=o(n?γ) for all γ, In particular, this holds for all γ and irrational α. The result has implications for rapidly mixing Markov chains whose stags are finite structures. If the stationary distribution is the same as the for random graphs with edg probability n^?α, then the expected waiting time unitl σ holds (as a function of n) is either bounded above by a polynomial in n, or it grows faster than any polynomical. All these results easily extend to finite structures of any relational type. © 1994 John Wiley & Sons, Inc.     

The choice of optimum scores in a Markov chain of order one

Summary The states of a Markov chain may be on an ordinal or a nominal scale. In this situation we need to assign appropriate scores to the states in order to study a given problem in detail. Using Fisher's criterion for assigning optimum scores to the marginals of anm×n contingency table, we shall obtain a system of optimum scores to assign to the states of a stationary Markov chain of order one.     

Induced embeddings in Steinhaus graphs

Fix any positive integer n. Let S be the set of all Steinhaus graphs of order n(n − 1)/2 + 1. The vertices for each graph in S are the first n(n − 1)/2 + 1 positive integers. Let I be the set of all labeled graphs of order n with vertices of the form i(i − 1)/2 + 1 for the first n positive integers i. This article shows that the function ϕ : S → I that maps a Steinhaus graph to its induced subgraph is a bijection. Therefore, any graph of order n is isomorphic to an induced subgraph of a Steinhaus graph of order n(n − 1)/2 + 1. This considerably tightens a result of Brigham, Carrington, and Dutton in [Brigham, Carrington, & Dutton, Combin. Inform. System Sci. 17 (1992)], which showed that this could be done with a Steinhaus graph of order 2ⁿ⁻¹. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 1–9, 1998     

Polynomial time perfect sampling algorithm for two‐rowed contingency tables

This paper proposes a polynomial time perfect (exact) sampling algorithm for 2 × n contingency tables. The algorithm is based on monotone coupling from the past (monotone CFTP) algorithm. The expected running time is bounded by O(n³ lnN) where n is the number of columns and N is the total sum of all entries. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The number of transversals in a Latin square

A Latin Square of order n is an n × n array of n symbols, in which each symbol occurs exactly once in each row and column. A transversal is a set of n entries, one selected from each row and each column of a Latin Square of order n such that no two entries contain the same symbol. Define T(n) to be the maximum number of transversals over all Latin squares of order n. We show that for n ≥ 5, where b ≈ 1.719 and c ≈ 0.614. A corollary of this result is an upper bound on the number of placements of n non-attacking queens on an n × n toroidal chess board. Some divisibility properties of the number of transversals in Latin squares based on finite groups are established. We also provide data from a computer enumeration of transversals in all Latin Squares of order at most 9, all groups of order at most 23 and all possible turn-squares of order 14.     

Random lifts of graphs: Independence and chromatic number

For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ_f, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χ_f/log²χ_f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002     

Latin squares with one subsquare

We look at two classes of constructions for Latin squares which have exactly one proper subsquare. The first class includes known squares due to McLeish and to Kotzig and Turgeon, which had not previously been shown to possess unique subsquares. The second class is a new construction called the corrupted product. It uses subsquare‐free squares of orders m and n to build a Latin square of order mn whose only subsquare is one of the two initial squares. We also provide tight bounds on the size of a unique subsquare and a survey of small order examples. Finally, we foreshadow how our squares might be used to create new Latin squares devoid of proper subsquares—so called N_∞ squares. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 128–146, 2001     

Discriminant of symmetric matrices as a sum of squares and the orthogonal group

It is proved that the discriminant of n × n real symmetric matrices can be written as a sum of squares, where the number of summands equals the dimension of the space of n‐variable spherical harmonics of degree n. The representation theory of the orthogonal group is applied to express the discriminant of 3 × 3 real symmetric matrices as a sum of five squares and to show that it cannot be written as the sum of less than five squares. It is proved that the discriminant of 4 × 4 real symmetric matrices can be written as a sum of seven squares. These improve results of Kummer from 1843 and Borchardt from 1846. © 2010 Wiley Periodicals, Inc.     

On Parity Vectors of Latin Squares

The parity vectors of two Latin squares of the same side n provide a necessary condition for the two squares to be biembeddable in an orientable surface. We investigate constraints on the parity vector of a Latin square resulting from structural properties of the square, and show how the parity vector of a direct product may be obtained from the parity vectors of the constituent factors. Parity vectors for Cayley tables of all Abelian groups, some non-Abelian groups, Steiner quasigroups and Steiner loops are determined. Finally, we give a lower bound on the number of main classes of Latin squares of side n that admit no self-embeddings.     

Packing of three copies of a graph

A graph of order n is said to be 3-placeable if there are three edge-disjoint copies of this graph in K_n. An (n, n − 1)-graph is a graph of order n with n − 1 edges. In this paper we characterize all the (n, n − 1)-graphs which contain no cycles of length 3 or 4 and which are 3-placeable. © 1996 John Wiley & Sons, Inc.     

Markov chain mixing time on cycles

Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n²) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.     

On the threshold problem for Latin boxes

Let m ≤ n ≤ k. An m × n × k 0‐1 array is a Latin box if it contains exactly m n ones, and has at most one 1 in each line. As a special case, Latin boxes in which m = n = k are equivalent to Latin squares. Let be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p, independently of the other entries. The threshold question for Latin squares asks when contains a Latin square with high probability. More generally, when does support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and , and where n = m and . In both cases, the threshold probability is . This implies threshold results for Latin rectangles and proper edge‐colorings of K_n,n.     

Dynamic Markov Bases

This article presents a computational approach for generating Markov bases for multiway contingency tables whose cell counts might be constrained by fixed marginals and by lower and upper bounds. Our framework includes tables with structural zeros as a particular case. Instead of computing the entire Markov bases in an initial step, our framework finds sets of local moves that connect each table in the reference set with a set of neighbor tables. We construct a Markov chain on the reference set of tables that requires only a set of local moves at each iteration. The union of these sets of local moves forms a dynamic Markov basis. We illustrate the practicality of our algorithms in the estimation of exact p-values for a three-way table with structural zeros and a sparse eight-way table. This article has online supplementary materials.     

Random doubly stochastic tridiagonal matrices

Let \begin{align*}{\mathcal T}\end{align*}n be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study ‘typical’ matrices T∈ \begin{align*}{\mathcal T}\end{align*}n chosen uniformly at random in the set \begin{align*}{\mathcal T}\end{align*}n. A simple algorithm is presented to allow direct sampling from the uniform distribution on \begin{align*}{\mathcal T}\end{align*}n. Using this algorithm, the elements above the diagonal in T are shown to form a Markov chain. For large n, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013     

Random markov processes and uniform martingales

It is shown here that a certain generalization of ann-step Markov chain is equivalent to the uniform convergence of the martingale {P(X ₀|X ₋₁ X ₋₂···X _−n)} _n=1 ^∞ . Ergodic and probabilistic properties of this process are explored. This work was initiated at SUNY/Albany.     

Triangulations of orientable surfaces by complete tripartite graphs

Orientable triangular embeddings of the complete tripartite graph K_n,n,n correspond to biembeddings of Latin squares. We show that if n is prime there are at least e^{nlnn-n(1+o(1))} nonisomorphic biembeddings of cyclic Latin squares of order n. If n=kp, where p is a large prime number, then the number of nonisomorphic biembeddings of cyclic Latin squares of order n is at least e^{plnp-p(1+lnk+o(1))}. Moreover, we prove that for every n there is a unique regular triangular embedding of K_n,n,n in an orientable surface.