Natural Isomorphism Classes of Cycle Permutation Graphs Over a Graph

 A permutation graph over a graph was introduced by Lee and Sohn in [8] as a generalization of both a graph bundle over a graph and a standard permutation graph, and they gave a characterization of a natural isomorphism and an automorphism of a given permutation graph over a graph. In this paper, we enumerate the natural isomorphism classes of cycle permutation graphs over a graph. Received: October 21, 1996 Revised: August 25, 1997     

Collapsing permutation groups

It is shown in [3] that any nonregular quasiprimitive permutation group is collapsing. In this paper we describe a wider class of collapsing permutation groups. Received June 6, 2000; accepted in final form August 11, 2000.     

A Fractional Muckenhoupt–Wheeden Theorem and its Consequences

In the 1970s Muckenhoupt and Wheeden made several conjectures relating two weight norm inequalities for the Hardy-Littlewood maximal operator to such inequalities for singular integrals. Using techniques developed for the recent proof of the A ₂ conjecture we prove a related pair of conjectures linking the Riesz potential and the fractional maximal operator. As a consequence we are able to prove a number of sharp one and two weight norm inequalities for the Riesz potential.     

A harmonic-type maximal principle in the three chains completion problem

In this note, we prove a harmonic-type maximal principle for the Schur parametrization of all contractive interpolants in the three chains completion problem (see [4]), which is analogous to the maximal principle proven in [2] in case of the Schur parametrization of all contractive intertwining liftings in the commutant lifting theorem.     

Lehmer code transforms and Mahonian statistics on permutations

In 2000 Babson and Steingrímsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006.In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections between subexcedant sequences) which when applied to the Lehmer code yield new permutation codes which count occurrences of some vincular patterns. These code transforms can be seen as a pre-compression step of the Lehmer code because they map some redundancies into runs of 0s. Also, our proofs, unlike the previous ones, provide explicit bijections between permutations having a given value for two different Mahonian pattern-based statistics.     

Formulas for multi-parameter classes of Kazhdan–Lusztig polynomials in S(n)

We give explicit formulas for several classes of Kazhdan–Lusztig polynomials of the symmetric group which are related to others already considered in the literature. In particular, we generalize two theorems of Brenti and Simion [Explicit formulae for some Kazhdan–Lusztig polynomials, J. Algebraic Combin. 11 (2000) 187–196], we prove an unpublished conjecture of Brenti, and we treat the case missing in Theorem 4.8 of F. Caselli [Proof of two conjectures of Brenti and Simion on Kazhdan–Lusztig polynomials, J. Algebraic Combin. 18 (2003) 171–187].     

The three squares lemma revisited

A recent paper Fan et al. (2006) [10] showed that the occurrence of two squares at the same position in a string, together with the occurrence of a third near by, is possible only in very special circumstances, represented by 14 well-defined cases. Similar results were published in Simpson (2007) [19]. In this paper we begin the process of extending this research in two ways: first, by proving a “two squares” lemma for a case not considered in Fan et al. (2006) [10]; second, by showing that in other cases, when three squares occur, more precise results — a breakdown into highly periodic substrings easily recognized in a left-to-right scan of the string — can be obtained with weaker assumptions. The motivation for this research is, first, to show that the maximum number of runs (maximal periodicities) in a string is at most n; second, and more important, to provide a combinatorial basis for a new generation of algorithms that directly compute repetitions in strings without elaborate preprocessing. Based on extensive computation, we present conjectures that describe the combinatorial behavior in all 14 of the subcases that arise. We then prove the correctness of seven of these conjectures. Along the way we establish a new combinatorial lemma characterizing strings of which two rotations have the same period.     

Packing sets of patterns

Packing density is a permutation occurrence statistic which describes the maximal number of permutations of a given type that can occur in another permutation. In this article we focus on containment of sets of permutations. Although this question has been tangentially considered previously, this is the first article focusing exclusively on it. We find the packing density for various special sets of permutations and study permutation and pattern co-occurrence.     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.     

Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus–Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.     

On the boundedness of some rational difference equations

We study the boundedness character of solutions of some third order rational difference equations and we confirm some of the conjectures posed in Camouzis et al. [“Progress report on the boundedness character of third-order rational equations”, Journal of Difference Equations and Applications 11 (2005), 1029–1035] and [“On third order rational difference equations, part 6”, Journal of Difference Equations and Applications 11 (2005), 759–777].     

交换环上特殊线性李代数的极大子代数

文章利用有单位元且2,3是单位的交换环的极大理想刻画了其上特殊线性李代数包含典范环面的极大子代数.确定了特殊线性李代数极大子代数的个数,并证明了每个极大子代数均可通过置换矩阵共轭于标准的极大子代数.     

Nowhere zero flows in line graphs

Cai an Corneil (Discrete Math. 102 (1992) 103–106), proved that if a graph has a cycle double cover, then its line graph also has a cycle double cover, and that the validity of the cycle double cover conjecture on line graphs would imply the truth of the conjecture in general. In this note we investigate the conditions under which a graph G has a nowhere zero k-flow would imply that L(G), the line graph of G, also has a nowhere zero k-flow. The validity of Tutte's flow conjectures on line graphs would also imply the truth of these conjectures in general.     

Comments on conjectures of trace inequalities on a generalized Wigner-Yanase skew information

Furuichi, Yanagi and Kuriyama gave three conjectures of trace inequalities on the Wigner-Yanase-Dyson skew information and a generalized Wigner-Yanase skew information (Furuichi et al. (2009) [1]) and Yanagi found a counterexample showing that two of the three conjectures don't hold (Yanagi (2010) [6]). In this note, we show that the last conjecture does not hold in general. In addition, we show that in the case of 2×2 matrices the conjecture is true.     

A possible combinatorial point for the XYZ spin chain

We formulate and discuss several conjectures related to the ground state vectors of odd-length XYZ spin chains with periodic boundary conditions and a special choice of the Hamiltonian parameters. In particular, we argue for the validity of a sum rule for the vector components that in a sense describes the degree of antiferromagneticity of the chain.     

On cycle permutation graphs

Permutation graphs were first introduced by Chartrand and Harary in 1967 [5]. The purpose of this paper is to study some properties of cycle permutation graphs. A determination of some of their crossing numbers, in keeping with the topological nature of the Chartrand and Harary paper is followed by the determination of all permutations yielding certain isomorphic permutation graphs, extending the algebraic results for planar graphs obtained by those authors.     

A characterization of finite nonsimple groups by the set of orders of their elements

It is proved that the permutation wreath product H of a simple Suzuki group Sz(2⁷) and a subgroup fo a symmetric group of degree 23, isomorphic to a Frobenius group of order 253, is (up to isomorphism) distinguished among all finite groups by the set of orders of its elements. Since H possesses a minimal normal subgroup N that contains an element of order equal to the exponent of N, this result furnishes a counterexample to one of the conjectures set forth by Shi [1]. In addition, we show that the direct square of a group Sz(2⁷) is also distinguished by the set of orders of its elements. Supported by RFFR grant No. 96-01-01893. Translated fromAlgebra i Logika, Vol. 36, No. 3, pp. 304–322, May–June, 1997.     

Large sets of Hamilton cycle and path decompositions

The existence spectrums for large sets of Hamilton cycle decompositions and Hamilton path decompositions are completed. Also, we show that the completion of large sets of directed Hamilton cycle decompositions and directed Hamilton path decompositions depends on the existence of certain special tuscan squares. Several conjectures about special tuscan squares are posed.     

有限个互素因子链上幂GCD矩阵与幂LCM矩阵的行列式的整除性

设S={x1,x2,...,xn}是由n个不同的正整数组成的集合,并设a为正整数.如果一个n阶矩阵的第i行j列元素是S中元素xi和xj的最大公因子的a次幂(xi,xj)a,则称该矩阵为定义在S上的a次幂最大公因子(GCD)矩阵,用(Sa)表示;类似定义a次幂LCM矩阵[Sa].如果存在{1,2,...,n}上的一个置换σ使得xσ(1)|xσ(2)|···|xσ(n),则称S为一个因子链.如果存在正整数k,使得S=S1∪S2∪···∪Sk,其中每一个Si(1ik)均为一个因子链,并且对所有的1i=jk,Si中的每个元素与Sj中的每个元素互素,则称S由有限个互素因子链构成.本文中,设S由有限个互素的因子链构成,并且1∈S.我们首先给出幂GCD矩阵与幂LCM矩阵的行列式的公式,然后证明:如果a|b,则det(Sa)|det(Sb),det[Sa]|det[Sb],det(Sa)|det[Sb].最后我们指出:如果构成S的有限个因子链不互素,则此结论一般不成立.     

Stanley's character polynomials and coloured factorisations in the symmetric group

In Stanley [R.P. Stanley, Irreducible symmetric group characters of rectangular shape, Sém. Lothar. Combin. 50 (2003) B50d, 11 p.] the author introduces polynomials which help evaluate symmetric group characters and conjectures that the coefficients of the polynomials are positive. In [R.P. Stanley, A conjectured combinatorial interpretation of the normalised irreducible character values of the symmetric group, math.CO/0606467, 2006] the same author gives a conjectured combinatorial interpretation for the coefficients of the polynomials. Here, we prove the conjecture for the terms of highest degree.