Convexity of the permanent for doubly stochastic matrices

Let Ω _n denote the set of all n×n doubly stochastic matrices and let J_n denote the n×n matrix all of whose entries are 1/n. Lih and Wang conjectuted that per[(1?i)J_n +iA≤(1?i)perJ_n 1i perA for all A∈Ω _n and all t∈[0,1/2], and proved their conjecture for n=3. In this paper we propose a similar conjecture asserting that for any A∈Ω _n \{J_n }, the permanent function is strietly convex on the straight line segment joining J_n and (J_n +A)/2, and prove it for the case n=3.     

A generating function for all semi-magic squares and the volume of the Birkhoff polytope

We present a multivariate generating function for all n×n nonnegative integral matrices with all row and column sums equal to a positive integer t, the so called semi-magic squares. As a consequence we obtain formulas for all coefficients of the Ehrhart polynomial of the polytope B _n of n×n doubly-stochastic matrices, also known as the Birkhoff polytope. In particular we derive formulas for the volumes of B _n and any of its faces.     

An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n ≥ 1, let G_n denote the complete graph of order n, and for all even integers n ≥ 2 let G_n denote the complete graph of order n with the edges of a 1‐factor removed. It is shown that for all non‐negative integers h and t and all positive integers n, G_n can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G_n. © 2004 Wiley Periodicals, Inc.     

A remark on local-global principles for conjugacy classes

A local-global principle is shown to hold for all conjugacy classes of any inner form of GL(n), SL(n), U(n), SU(n), and for all semisimple conjugacy classes in any inner form of Sp(n), over fieldsk with vcd(k)≤1. Over number fields such a principle is known to hold for any inner form of GL(n) and U(n), and for the split forms of Sp(n), O(n), as well as for SL(p) but not for SL(n),n non-prime. The principle holds for all conjugacy classes in any inner form of GL(n), but not even for semisimple conjugacy classes in Sp(n), over fieldsk with vcd(k)≤2. The principle for conjugacy classes is related to that for centralizers.     

Smallest maximally nonhamiltonian graphs II

Bollobás posed the problem of finding the least number of edges,f(n), in a maximally nonhamiltonian graph of ordern. Clark and Entringer showedf(n)=3n/2 for all evenn≥36 andf(n)=(3n+1)/2 or (3n+3)/2 for all oddn≥55. We showf(n)=(3n+1)/2 for all oddn≥53.     

Subpermanents of doubly stochastic matrices †

It is shown that if all subpermaneats of order k of an n × n doubly stochastic matrix are equal for some k ≤ n ? 2, then all the entries of the matrix must be equal to 1/n.     

Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs

In this paper, a sequential algorithm is presented to find all cut-vertices on trapezoid graphs. To every trapezoid graph G there is a corresponding trapezoid representation. If all the 4n corner points of n trapezoids, in a trapezoid representation of a trapezoid graph G with n vertices, are given, then the proposed sequential algorithm runs in O(n) time. Parallel implementation of this algorithm can be done in O(log n) time using O(n/ log n) processors on an EREW PRAM model.     

3,5-Cycle decompositions

For all odd integers n and all non-negative integers r and s satisfying 3r + 5s = n(n − 1)/2 it is shown that the edge set of the complete graph on n vertices can be partitioned into r 3-cycles and s 5-cycles. For all even integers n and all non-negative integers r and s satisfying 3r + 5s = n(n − 2)/2 it is shown that the edge set of the complete graph on n vertices with a 1-factor removed can be partitioned into r 3-cycles and s 5-cycles. © 1998 John Wiley & Sons, Inc. J Combin Designs 6:91–110, 1998     

The classification of N-dimensional non-associative Jordan algebras with (N − 3)-dimensional annihilator

The paper is devoted to give a complete classification of all n-dimensional non-associative Jordan algebras with (n?3)-dimensional annihilator over an algebraically closed field of characteristic ≠2. We also give a complete classification of all n-dimensional Jordan algebras with (n?1)- and (n?2)-dimensional annihilator.     

The tripartite Ramsey number for trees

We prove that for all ε>0 there are α>0 and n₀∈? such that for all n?n₀ the following holds. For any two‐coloring of the edges of K_{n, n, n} one color contains copies of all trees T of order t?(3 ? ε)n/2 and with maximum degree Δ(T)?n^α. This confirms a conjecture of Schelp. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 264–300, 2012     

Bipartite labeling of trees with maximum degree three

Let T = (V, E) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, |V|} for which there exists a k such that whenever φ(u) ≤ k < φ(v), then u and v have different colors. The α‐size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) − φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α‐size of trees with maximum degree three. Let α₃(n) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α₃(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5n/6. Using a computer search, we also establish that α₃(n) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999     

Maximal regular subsemigroups of certain semigroups of transformations

Let T _n and P _n be the full and partial transformation semigroups on a finite set of order n respectively. The properties of the subsemigroups of T _n and P _n have been widely studied. But the maximal regular subsemigroups of T _n and P _n seem to be unknown. In this note, we determine all the maximal regular subsemigroups of all ideals of T _n and P _n . April 7, 1999     

On the construction of odd cycle systems

Three obvious necessary conditions for the existence of a k-cycle system of order n are that if n > 1 then n ? k, n is odd, and 2k divides n(n ? 1). We show that if these necessary conditions are sufficient for all n satisfying k ? n < 3k then they are sufficient for all n. In particular, there exists a 15-cycle system of order n if and only if n ≡ 1, 15, 21, or 25 (mod 30), and there exists a 21-cycle system of order n if and only if n ≡ 1, 7, 15, or 21 (mod 42), n ≠ 7. 15.     

Fast generation of cubic graphs

In this paper an efficient algorithm to generate regular graphs with small vertex valency is presented. The running times of a program based on this algorithm and designed to generate cubic graphs are below two natural benchmarks: (a) If N(n) denotes the number of pairwise non-isomorphic cubic graphs with n vertices and T(n) the time needed for generating the list of all these graphs, then T(n)/N(n) decreases gradually for the observed values of n. This suggests that T(n)/N(n) might be uniformly bounded for all n, ignoring the time to write the outputs, but we are unable to prove this and in fact are not confident about it. (b) For programs that generate lists of non-isomorphic objects, but cannot a priori make sure to avoid the generation of isomorphic copies, the time needed to check a randomly ordered list of these objects for being non-isomorphic is a natural benchmark. Since for large lists (n ≥ 22, girth 3) existing graph isomorphism programs take longer to canonically label all of the N(n) graphs than our algorithm takes to generate them, our algorithm is probably faster than any method which does one or more isomorphism test for every graph. © 1996 John Wiley & Sons, Inc.     

Triangular stochastic matrices generated by infinitesimal elements

We show that each element in the semigroup S _n of all n × n non-singular upper (or lower) triangular stochastic matrices is generated by the infinitesimal elements of S _n, which form a cone consisting of all n × n upper (or lower) triangular intensity matrices.     

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.     

The number of distinct latin squares as a group-theoretical constant

It is shown that the number l_n of all distinct Latin squares of the nth order appears as a structure constant of the algebra defined on the Magic squares of the same order. The algebra is isomorphic to the algebra of double cosets of the symmetric group of degree n² with respect to the intransitive subgroup of all substitutions in the n sets of transitivity, each set being of cardinality n. The representation theory makes it possible then to express l_n in terms of eigenvalues of a certain element of the algebra.