Quasisymmetric and Schur expansions of cycle index polynomials

Given a subgroup $G$ of the symmetric group $S_n$, the cycle index polynomial ${\mathrm{cyc}}_G$ is the average of the power-sum symmetric polynomials indexed by the cycle types of permutations in $G$. By Pólya’s Theorem, the monomial expansion of ${\mathrm{cyc}}_G$ is the generating function for weighted colorings of $n$ objects, where we identify colorings related by one of the symmetries in $G$. This paper develops combinatorial formulas for the fundamental quasisymmetric expansions and Schur expansions of certain cycle index polynomials. We give explicit bijective proofs based on standardization algorithms applied to equivalence classes of colorings. Subgroups studied here include Young subgroups of $S_n$, the alternating groups $A_n$, direct products, conjugate subgroups, and certain cyclic subgroups of $S_n$ generated by $(1,2,\dots ,k)$. The analysis of these cyclic subgroups when $k$ is prime reveals an unexpected connection to perfect matchings on a hypercube with certain vertices identified.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

A species approach to Rota’s twelvefold way

An introduction to Joyal’s theory of combinatorial species is given and through it an alternative view of Rota’s twelvefold way emerges.     

Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles

A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281-300].     

脉冲爆轰发动机的系统性能分析

采用简化的脉冲爆轰推进装置模型,利用热循环效率分析方法,推导了包含进气道总压恢复系数的热循环效率公式. 并在特定来流条件下,考察了一个爆轰循环中进气道总压恢复系数和燃烧室初始温度对热循环效率和比冲的影响. 研究发现,降低来流总压损失有助于提高热循环效率,而提高燃烧室初始温度能更有效地提高热循环效率. 据此,提出了多级重起爆脉冲爆轰发动机概念,利用在突扩截面上解耦的爆轰波的前导激波去再次压缩工质,进一步提高工质的热力学参数,从而提高脉冲爆轰装置的热循环效率. 推导了此种构型PDE的热循环效率计算公式,并对多级重起爆脉冲爆轰发动机进行了原理性论证. 研究结果表明,多级重起爆方法提高了燃烧室的爆前温度,从而有效地提高脉冲爆轰发动机热循环效率. 最后,关于出口工质的非完全膨胀的情况,做了定性的阐述,认为只有降低工质的出口压力,才能更有效增加工质的出口动能,从而提高热循环效率.      

Edge-swapping algorithms for the minimum fundamental cycle basis problem

We consider the problem of finding a fundamental cycle basis with minimum total cost in an undirected graph. This problem is NP-hard and has several interesting applications. Since fundamental cycle bases correspond to spanning trees, we propose a local search algorithm, a tabu search and variable neighborhood search in which edge swaps are iteratively applied to a current spanning tree. We also present a mixed integer programming formulation of the problem whose linear relaxation yields tighter lower bounds than other known formulations. Computational results obtained with our algorithms are compared with those from the best available constructive heuristic on several types of graphs. This article extends the conference paper (Amaldi et al. 2004).