The rank-width of the square grid

Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×nsquare grid, denoted by G_n,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x^′,y^′) if and only if |x−x^′|+|y−y^′|=1.We prove that the rank-width of G_n,n is equal to n−1, thus solving an open problem of Oum.     

A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

On the degrees of a strongly vertex-magic graph

Let G=(V,E) be a finite graph, where |V|=n?2 and |E|=e?1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,…,n+e} with the property that for every v∈V, for some constant h. Such a labeling is strong if λ(V)={1,2,…,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if , then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.     

Walking in circles

Consider the unit circle S¹ with distance function d measured along the circle. We show that for every selection of 2n points x₁,…,x_n,y₁,…,y_n∈S¹ there exists i∈{1,…,n} such that . We also discuss a game theoretic interpretation of this result.     

A generalization of Sperner’s theorem and an application to graph orientations

A generalization of Sperner’s theorem is established: For a multifamily M={Y₁,…,Y_p} of subsets of {1,…,n} in which the repetition of subsets is allowed, a sharp lower bound for the number φ(M) of ordered pairs (i,j) satisfying i≠j and Y_i⊆Y_j is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.     

Ramsey regions

Let (T₁,T₂,…,T_c) be a fixed c-tuple of sets of graphs (i.e. each T_i is a set of graphs). Let R(c,n,(T₁,T₂,…,T_c)) denote the set of all n-tuples, (a₁,a₂,…,a_n), such that every c-coloring of the edges of the complete multipartite graph, K_a1,a2,…,an, forces a monochromatic subgraph of color i from the set T_i (for at least one i). If N denotes the set of non-negative integers, then R(c,n,(T₁,T₂,…,T_c))⊆Nⁿ. We call such a subset of Nⁿ a “Ramsey region”. An application of Ramsey's Theorem shows that R(c,n,(T₁,T₂,…,T_c)) is non-empty for n?0. For a given c-tuple, (T₁,T₂,…,T_c), known results in Ramsey theory help identify values of n for which the associated Ramsey regions are non-empty and help establish specific points that are in such Ramsey regions. In this paper, we develop the basic theory and some of the underlying algebraic structure governing these regions.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

On the spectrum of critical sets in latin squares of order 2n

Suppose that L is a latin square of order m and P ? L is a partial latin square. If L is the only latin square of order m which contains P, and no proper subset of P has this property, then P is a critical set of L. The critical set spectrum problem is to determine, for a given m, the set of integers t for which there exists a latin square of order m with a critical set of size t. We outline a partial solution to the critical set spectrum problem for latin squares of order 2ⁿ. The back circulant latin square of even order m has a well‐known critical set of size m²/4, and this is the smallest known critical set for a latin square of order m. The abelian 2‐group of order 2ⁿ has a critical set of size 4ⁿ‐3ⁿ, and this is the largest known critical set for a latin square of order 2ⁿ. We construct a set of latin squares with associated critical sets which are intermediate between the back circulant latin square of order 2ⁿ and the abelian 2‐group of order 2ⁿ. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 25–43, 2008     

An asymptotic solution to the cycle decomposition problem for complete graphs

Let m₁,m₂,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m₁,m₂,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching.     

Tangent unit-vector fields: Nonabelian homotopy invariants and the dirichlet energy

Let O be a closed geodesic polygon in S². Maps from O into S² are said to satisfy tangent boundary conditions if the edges of O are mapped into the geodesics which contain them. Taking O to be an octant of S², we compute the infimum Dirichlet energy ?(H) for continuous maps satisfying tangent boundary conditions of arbitrary homotopy type H. The expression for ?(H) involves a topological invariant – the spelling length – associated with the (non-abelian) fundamental group of the n-times punctured two-sphere, π₁(S² − {s₁,…, s_n}, *). The lower bound for ?(H) is obtained from combinatorial group theory arguments, while the upper bound is obtained by constructing explicit representatives which, on all but an arbitrarily small subset of O, are alternatively locally conformal or anticonformal. For conformal and anticonformal classes (classes containing wholly conformal and anticonformal representatives respectively), the expression for ?(H) reduces to a previous result involving the degrees of a set of regular values s₁, …, s_n in the target S² space. These degrees may be viewed as invariants associated with the abelianization of π₁(S² - {s₁,…, s_n}, *). For nonconformal classes, however, ?(H) may be strictly greater than the abelian bound. This stems from the fact that, for nonconformal maps, the number of preimages of certain regular values may necessarily be strictly greater than the absolute value of their degrees.     

Latin Squares without Orthogonal Mates

In 1779 Euler proved that for every even n there exists a latin square of order n that has no orthogonal mate, and in 1944 Mann proved that for every n of the form 4k + 1, k ≥ 1, there exists a latin square of order n that has no orthogonal mate. Except for the two smallest cases, n = 3 and n = 7, it is not known whether a latin square of order n = 4k + 3 with no orthogonal mate exists or not. We complete the determination of all n for which there exists a mate-less latin square of order n by proving that, with the exception of n = 3, for all n = 4k + 3 there exists a latin square of order n with no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.     

Interval partitions and Stanley depth

In this paper, we answer a question posed by Herzog, Vladoiu, and Zheng. Their motivation involves a 1982 conjecture of Richard Stanley concerning what is now called the Stanley depth of a module. The question of Herzog et al., concerns partitions of the non-empty subsets of {1,2,…,n} into intervals. Specifically, given a positive integer n, they asked whether there exists a partition P(n) of the non-empty subsets of {1,2,…,n} into intervals, so that |B|?n/2 for each interval [A,B] in P(n). We answer this question in the affirmative by first embedding it in a stronger result. We then provide two alternative proofs of this second result. The two proofs use entirely different methods and yield non-isomorphic partitions. As a consequence, we establish that the Stanley depth of the ideal (x₁,…,xn)⊆K[x₁,…,xn] (K a field) is ⌈n/2⌉.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Minimal homogeneous latin trades

A latin trade is a subset of a latin square which may be replaced with a disjoint mate to obtain a new latin square. A d-homogeneous latin trade is one which intersects each row, each column and each entry of the latin square either 0 or d times. In this paper we give a construction for minimal d-homogeneous latin trades of size dm, for every integer d?3, and m?1.75d²+3. We also improve this bound for small values of d. Our proof relies on the construction of cyclic sequences whose adjacent sums are distinct.     

Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

Enumerating split-pair arrangements

An arrangement of the multi-set {1,1,2,2,…,n,n} is said to be “split-pair” if for all i<n, between the two occurrences of i there is exactly one i+1. We enumerate the number of split-pair arrangements and in particular show that the number of such arrangements is (−1)ⁿ⁺¹n²(²2n−1)B2n where Bi is the ith Bernoulli number.     

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

A set of planar graphs {G₁(V,E₁),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K₅ or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n⁴)-time algorithms to compute a SEFE.