The Electronic Journal of Combinatorics
http://www.combinatorics.org/ojs/index.php/eljc
<p>The Electronic Journal of Combinatorics (E-JC) is a fully-refereed electronic journal with <em>very high standards,</em> publishing papers of substantial content and interest in all branches of discrete mathematics, including combinatorics, graph theory, and algorithms for combinatorial problems. The journal is <em>completely free</em> for both authors and readers. Authors retain the copyright of their articles. Articles published in E-JC are reviewed on MathSciNet and ZBMath, and are indexed by Web of Science. The latest papers are always available by clicking on the tab marked "Current" near the top of the page. You can also locate papers using the search facility on the right hand side of this page.</p><p>E-JC was founded in 1994 by Herbert S. Wilf and Neil Calkin, making it one of the oldest electronic journals.</p>en-US<p>The copyright of published papers remains with the authors. We only require your agreement that we publish it, as described in the following publication release agreement:</p><ol><li>This is an agreement between the Electronic Journal of Combinatorics (the "Journal"), and the copyright owner (the "Owner") of a work (the "Work") to be published in the Journal.</li><li>The Owner warrants that s/he has the full power and authority to enter into this Agreement and to grant the rights granted in this Agreement.</li><li>The Owner hereby grants to the Journal a worldwide, irrevocable, royalty free license to publish or distribute the Work, to enter into arrangements with others to publish or distribute the Work, and to archive the Work.</li><li>The Owner agrees that further publication of the Work, with the same or substantially the same content as appears in the Journal, will include an acknowledgement of prior publication in the Journal.</li></ol>akundgen@csusm.edu (André Kündgen)bdm@cs.anu.edu.au (Brendan McKay)Fri, 02 Jan 2015 11:36:01 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60Periodic Rigidity on a Variable Torus Using Inductive Constructions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p1
In this paper we prove a recursive characterisation of generic rigidity for frameworks periodic with respect to a partially variable lattice. We follow the approach of modelling periodic frameworks as frameworks on a torus and use the language of gain graphs for the finite counterpart of a periodic graph. In this setting we employ variants of the Henneberg operations used frequently in rigidity theory.Anthony Nixon, Elissa Rosshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p1Fri, 02 Jan 2015 00:00:00 +1100Evaluating the Numbers of some Skew Standard Young Tableaux of Truncated Shapes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p2
<p>In this paper the number of standard Young tableaux (SYT) is evaluated by the methods of multiple integrals and combinatorial summations. We obtain the product formulas of the numbers of skew SYT of certain truncated shapes, including the skew SYT $((n+k)^{r+1},n^{m-1}) / (n-1)^r $ truncated by a rectangle or nearly a rectangle, the skew SYT of truncated shape $((n+1)^3,n^{m-2}) / (n-2) \backslash \; (2^2)$, and the SYT of truncated shape $((n+1)^2,n^{m-2}) \backslash \; (2)$.</p>Ping Sunhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p2Fri, 02 Jan 2015 00:00:00 +1100Some Enumerations on Non-Decreasing Dyck Paths
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p3
We construct a formal power series on several variables that encodes many statistics on non-decreasing Dyck paths. In particular, we use this formal power series to count peaks, pyramid weights, and indexed sums of pyramid weights for all non-decreasing Dyck paths of length $2n.$ We also show that an indexed sum on pyramid weights depends only on the size and maximum element of the indexing set.Éva Czabarka, Rigoberto Flórez, Leandro Juneshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p3Fri, 02 Jan 2015 00:00:00 +1100Group Homomorphisms as Error Correcting Codes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p4
<p>We investigate the minimum distance of the error correcting code formed by the homomorphisms between two finite groups $G$ and $H$. We prove some general structural results on how the distance behaves with respect to natural group operations, such as passing to subgroups and quotients, and taking products. Our main result is a general formula for the distance when $G$ is solvable or $H$ is nilpotent, in terms of the normal subgroup structure of $G$ as well as the prime divisors of $|G|$ and $|H|$. In particular, we show that in the above case, the distance is independent of the subgroup structure of $H$. We complement this by showing that, in general, the distance depends on the subgroup structure of $H$.</p>Alan Guohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p4Fri, 02 Jan 2015 00:00:00 +1100Vertically Symmetric Alternating Sign Matrices and a Multivariate Laurent Polynomial Identity
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p5
In 2007, the first author gave an alternative proof of the refined alternating sign matrix theorem by introducing a linear equation system that determines the refined ASM numbers uniquely. Computer experiments suggest that the numbers appearing in a conjecture concerning the number of vertically symmetric alternating sign matrices with respect to the position of the first 1 in the second row of the matrix establish the solution of a linear equation system similar to the one for the ordinary refined ASM numbers. In this paper we show how our attempt to prove this fact naturally leads to a more general conjectural multivariate Laurent polynomial identity. Remarkably, in contrast to the ordinary refined ASM numbers, we need to extend the combinatorial interpretation of the numbers to parameters which are not contained in the combinatorial admissible domain. Some partial results towards proving the conjectured multivariate Laurent polynomial identity and additional motivation why to study it are presented as well.Ilse Fischer, Lukas Rieglerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p5Fri, 02 Jan 2015 00:00:00 +1100On-Line Choice Number of Complete Multipartite Graphs: an Algorithmic Approach
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p6
This paper studies the on-line choice number on complete multipartite graphs with independence number $m$. We give a unified strategy for every prescribed $m$. Our main result leads to several interesting consequences comparable to known results. (1) If $k_1-\sum_{p=2}^m\left(\frac{p^2}{2}-\frac{3p}{2}+1\right)k_p\geq 0$, where $k_p$ denotes the number of parts of cardinality $p$, then $G$ is on-line chromatic-choosable. (2) If $|V(G)|\leq\frac{m^2-m+2}{m^2-3m+4}\chi(G)$, then $G$ is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs $K_{m\star k}$ is at most<br />$\left(m+\frac{1}{2}-\sqrt{2m-2}\right)k$ for $m\geq 3$.Fei-Huang Chang, Hong-Bin Chen, Jun-Yi Guo, Yu-Pei Huanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p6Fri, 02 Jan 2015 00:00:00 +1100On Computing the Degree of Convexity of Polyominoes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p7
<p>In this paper we present an algorithm which has as input a convex polyomino $P$ and computes its degree of convexity, defined as the smallest integer $k$ such that any two cells of $P$ can be joined by a monotone path inside $P$ with at most $k$ changes of direction. The algorithm uses space $O(m + n)$ to represent a polyomino $P$ with $n$ rows and $m$ columns, and has a running time $O(min(m; r k))$, where $r$ is the number of corners of $P$. Moreover, the algorithm leads naturally to a decomposition of $P$ into simpler polyominoes.</p>Stefano Brocchi, Giuseppa Castiglione, Paolo Massazzahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p7Fri, 09 Jan 2015 00:00:00 +1100The Concavity and Convexity of the Boros-Moll Sequences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p8
In their study of a quartic integral, Boros and Moll discovered a special class of sequences, which is called the Boros<em>–</em>Moll sequences. In this paper, we consider the concavity and convexity of the Boros<em>–</em>Moll sequences $\{d_i(m)\}_{i=0}^m$. We show that for any integer $m\geq 6$, there exist two positive integers $t_0(m)$ and $t_1(m)$ such that $d_i(m)+d_{i+2}(m)>2d_{i+1}(m)$ for $i\in [0,t_0(m)]\bigcup[t_1(m),m-2]$ and $d_i(m)+d_{i+2}(m) < 2d_{i+1}(m)$ for $i\in [t_0(m)+1,t_1(m)-1]$. When $m$ is a square, we find $t_0(m)=\frac{m-\sqrt{m}-4}{2}$ and $t_1(m) =\frac{m+\sqrt{m}-2}{2}$. As a corollary of our results, we show that<br /> \[<br />\lim_{m\rightarrow +\infty }\frac{{\rm card}\{i|d_i(m)+d_{i+2}(m)< 2d_{i+1}(m), 0\leq i \leq m-2\}}{\sqrt{m}}=1.<br /> \]Ernest X.W. Xiahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p8Fri, 09 Jan 2015 00:00:00 +1100Proof of a Conjecture of Amdeberhan and Moll on a Divisibility Property of Binomial Coefficients
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p9
Let $a,b$ and $n$ be positive integers with $a>b$. In this note, we prove that $$(2bn+1)(2bn+3){2bn \choose bn}\bigg|3(a-b)(3a-b){2an \choose an}{an\choose bn}.$$ This confirms a recent conjecture of Amdeberhan and Moll.Quan-Hui Yanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p9Fri, 09 Jan 2015 00:00:00 +1100Discrete Dirac Operators, Critical Embeddings and Ihara-Selberg Functions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p10
<p>The aim of the paper is to formulate a discrete analogue of the claim made by Alvarez-Gaume et al., realizing the partition function of the free fermion on a closed Riemann surface of genus $g$ as a linear combination of $2^{2g}$ Pfaffians of Dirac operators. Let $G=(V,E)$ be a finite graph embedded in a closed Riemann surface $X$ of genus $g$, $x_e$ the collection of independent variables associated with each edge $e$ of $G$ (collected in one vector variable $x$) and $\S$ the set of all $2^{2g}$ spin-structures on $X$. We introduce $2^{2g}$ rotations $rot_s$ and $(2|E|\times 2|E|)$ matrices $\Delta(s)(x)$, $s\in \Sigma$, of the transitions between the oriented edges of $G$ determined by rotations $rot_s$. We show that the generating function of the even sets of edges of $G$, i.e., the Ising partition function, is a linear combination of the square roots of $2^{2g}$ Ihara-Selberg functions $I(\Delta(s)(x))$ also called Feynman functions. By a result of Foata and Zeilberger $I(\Delta(s)(x))=\det(I-\Delta'(s)(x))$, where $\Delta'(s)(x)$ is obtained from $\Delta(s)(x)$ by replacing some entries by $0$. Thus each Feynman function is computable in a polynomial time. We suggest that in the case of critical embedding of a bipartite graph $G$, the Feynman functions provide suitable discrete analogues for the Pfaffians of Dirac operators.</p>Martin Loebl, Petr Somberghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p10Fri, 09 Jan 2015 00:00:00 +1100Maximum 4-Degenerate Subgraph of a Planar Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p11
<p>A graph $G$ is $k$-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree $k$ or less. We prove that every connected planar graph with average degree $d \ge 2$ has a $4$-degenerate induced subgraph containing at least $ (38 - d)/36$ of its vertices. This shows that every planar graph of order $n$ has a $4$-degenerate induced subgraph of order more than $8/9 \cdot n$. We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.</p>Robert Lukot'ka, Ján Mazák, Xuding Zhuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p11Tue, 20 Jan 2015 00:00:00 +1100Characterizations of Regularity for certain $Q$-Polynomial Association Schemes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p12
It was shown that linked systems of symmetric designs with $a_1^*=0$ and mutually unbiased bases (MUBs) are triply regular association schemes. In this paper, we characterize triple regularity of linked systems of symmetric designs by its Krein number. And we prove that a maximal set of MUBs carries a quadruply regular association scheme and characterize the quadruple regularity of MUBs by its parameter.Sho Sudahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p12Tue, 20 Jan 2015 00:00:00 +1100Spanning $k$-trees of Bipartite Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p13
A tree is called a $k$-tree if its maximum degree is at most $k$. We prove the following theorem. Let $k \geq 2$ be an integer, and $G$ be a connected bipartite graph with bipartition $(A,B)$ such that $|A| \le |B| \le (k-1)|A|+1$. If $\sigma_k(G) \ge |B|$, then $G$ has a spanning $k$-tree, where $\sigma_k(G)$ denotes the minimum degree sum of $k$ independent vertices of $G$. Moreover, the condition on $\sigma_k(G)$ is sharp. It was shown by Win (Abh. Math. Sem. Univ. Hamburg, 43, 263–267, 1975) that if a connected graph $H$ satisfies $\sigma_k(H) \ge |H|-1$, then $H$ has a spanning $k$-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.Mikio Kano, Kenta Ozeki, Kazuhiro Suzuki, Masao Tsugaki, Tomoki Yamashitahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p13Tue, 20 Jan 2015 00:00:00 +1100Crossings and Nestings for Arc-Coloured Permutations and Automation
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p14
Symmetric joint distribution between crossings and nestings was established in several combinatorial objects. Recently, Marberg extended Chen and Guo's result on coloured matchings to coloured set partitions following a multi-dimensional generalization of the bijection and enumerative methods from Chen, Deng, Du, Stanley, and Yan. We complete the study for arc-coloured permutations by establishing symmetric joint distribution for crossings and nestings and by showing that the ordinary generating functions for $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations according to size $n$ are rational functions. Finally, we automate the generation of these rational functions and analyse the first $70$ series.Lily Yenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p14Tue, 20 Jan 2015 00:00:00 +1100On-line Ramsey Numbers of Paths and Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p15
Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the <em>on-line Ramsey number</em> $\tilde{r}(G,H)$. In this paper, we consider the case where $G$ is a path $P_k$. We prove that $\tilde{r}(P_3,P_{\ell+1}) = \lceil 5\ell/4\rceil = \tilde{r}(P_3,C_{\ell})$ for all $\ell \ge 5$, and determine $\tilde{r}(P_4,P_{\ell+1})$ up to an additive constant for all $\ell \ge 3$. We also prove some general lower bounds for on-line Ramsey numbers of the form $\tilde{r}(P_{k+1},H)$.Joanna Cyman, Tomasz Dzido, John Lapinskas, Allan Lohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p15Tue, 20 Jan 2015 00:00:00 +1100On Keller’s Conjecture in Dimension Seven
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p16
<p>A cube tiling of $\mathbb{R}^d$ is a family of pairwise disjoint cubes $[0,1)^d+T=\{[0,1)^d+t:t\in T\}$ such that $\bigcup_{t\in T}([0,1)^d+t=\mathbb{R}^d$. Two cubes $[0,1)^d+t$, $[0,1)^d+s$ are called a twin pair if $|t_j-s_j|=1$ for some $j\in [d]=\{1,\ldots, d\}$ and $t_i=s_i$ for every $i\in [d]\setminus \{j\}$. In $1930$, Keller conjectured that in every cube tiling of $\mathbb{R}^d$ there is a twin pair. Keller's conjecture is true for dimensions $d\leq 6$ and false for all dimensions $d\geq 8$. For $d=7$ the conjecture is still open. Let $x\in \mathbb{R}^d$, $i\in [d]$, and let $L(T,x,i)$ be the set of all $i$th coordinates $t_i$ of vectors $t\in T$ such that $([0,1)^d+t)\cap ([0,1]^d+x)\neq \emptyset$ and $t_i\leq x_i$. Let $r^-(T)=\min_{x\in \mathbb{R}^d}\; \max_{1\leq i\leq d}|L(T,x,i)|$ and $r^+(T)=\max_{x\in \mathbb{R}^d}\; \max_{1\leq i\leq d}|L(T,x,i)|$. <span style="font-size: 10px;">It is known that if $r^-(T)\leq 2$ or $r^+(T)\geq 6$, then Keller's conjecture is true for $d=7$. In the present paper we show that it is also true for $d=7$ if $r^+(T)=5$. Thus, if $[0,1)^d+T$ is a counterexample to Keller's conjecture in dimension seven, then $r^-(T),r^+(T)\in \{3,4\}$.</span></p>Andrzej P. Kisielewicz, Magdalena Łysakowskahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p16Tue, 20 Jan 2015 00:00:00 +1100Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p17
We present new functional equations connecting the counting series of plane and planar (in the sense of Harary and Palmer) dissections. Simple rigorous expressions for counting symmetric $r$-dissections of polygons and planar $S$-dissections are obtained.Evgeniy Krasko, Alexander Omelchenkohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p17Tue, 27 Jan 2015 00:00:00 +1100Multiple Coverings with Closed Polygons
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p18
A planar set $P$ is said to be cover-decomposable if there is a constant $k=k(P)$ such that every $k$-fold covering of the plane with translates of $P$ can be decomposed into two coverings. It is known that open convex polygons are cover-decomposable. Here we show that closed, centrally symmetric convex polygons are also cover-decomposable. We also show that an <em>infinite-fold</em> covering of the plane with translates of $P$ can be decomposed into two infinite-fold coverings. Both results hold for coverings of any subset of the plane. <br /><br />István Kovács, Géza Tóthhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p18Tue, 27 Jan 2015 00:00:00 +1100On the Codes Related to the Higman-Sims Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p19
<p>All linear codes of length $100$ over a field $F$ which admit the Higman-Sims simple group HS in its rank $3$ representation are determined. By group representation theory it is proved that they can all be understood as submodules of the permutation module $F\Omega$ where $\Omega$ denotes the vertex set of the Higman-Sims graph. This module is semisimple if $\mathrm{char} F\neq 2,5$ and absolutely indecomposable otherwise. Also if $\mathrm{char} F \in \{2, 5\}$ the submodule lattice is determined explicitly. The binary case $F = \mathbb{F}_2$ is studied in detail under coding theoretic aspects. The HS-orbits in the subcodes of dimension $\leq 23$ are computed explicitly and so also the weight enumerators are obtained. The weight enumerators of the dual codes are determined by MacWilliams transformation. Two fundamental methods are used: Let $v$ be the endomorphism determined by an adjacency matrix. Then in $H_{22} = \mathrm{Im} v $ the HS-orbits are determined as $v$-images of certain low weight vectors in $F\Omega$ which carry some special graph configurations. The second method consists in using the fact that $H_{23}/H_{21}$ is a Klein four group under addition, if $H_{23}$ denotes the code generated by $H_{22}$ and a "Higman vector" $x(m)$ of weight 50 associated to a heptad $m$ in the shortened Golay code $G_{22}$, and $H_{21}$ denotes the doubly even subcode of $H_{22}\leq H_{78} = {H_{22}}^\perp$. Using the mentioned observation about $H_{23}/H_{21}$ and the results on the HS-orbits in $H_{23}$ a model of G. Higman's geometry is constructed, which leads to a direct geometric proof that G. Higman's simple group is isomorphic to HS. Finally, it is shown that almost all maximal subgroups of the Higman-Sims group can be understood as stabilizers in HS of codewords in $H_{23}$.</p>Wolfgang Knapp, Hans-Jörg Schaefferhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p19Tue, 27 Jan 2015 00:00:00 +1100On a Refinement of Wilf-equivalence for Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p20
<p>Recently, Dokos et al. conjectured that for all $k, m\geq 1$, the patterns $ 12\ldots k(k+m+1)\ldots (k+2)(k+1) $ and $(m+1)(m+2)\ldots (k+m+1)m\ldots 21$ are $maj$-Wilf-equivalent. In this paper, we confirm this conjecture for all $k\geq 1$ and $m=1$. In fact, we construct a descent set preserving bijection between $ 12\ldots k (k-1) $-avoiding permutations and $23\ldots k1$-avoiding permutations for all $k\geq 3$. As a corollary, our bijection enables us to settle a conjecture of Gowravaram and Jagadeesan concerning the Wilf-equivalence for permutations with given descent sets.</p>Sherry H.F. Yan, Huiyun Ge, Yaqiu Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p20Mon, 09 Feb 2015 00:00:00 +1100On Commuting Graphs for Elements of Order 3 in Symmetric Groups
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p21
The commuting graph $\mathcal{C}(G,X)$, where $G$ is a group and $X$ is a subset of $G$, is the graph with vertex set $X$ and distinct vertices being joined by an edge whenever they commute. Here the diameter of $\mathcal{C}(G,X)$ is studied when $G$ is a symmetric group and $X$ a conjugacy class of elements of order $3$.Athirah Nawawi, Peter Rowleyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p21Mon, 09 Feb 2015 00:00:00 +1100A Characterization of the Hermitian Variety in Finite 3-Dimensional Projective Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p22
A combinatorial characterization of a non-singular Hermitian variety of the finite 3-dimensional projective space via its intersection numbers with respect to lines and planes is given.Vito Napolitanohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p22Mon, 09 Feb 2015 00:00:00 +1100Faster Rumor Spreading With Multiple Calls
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p23
<p>We consider the random phone call model introduced by Demers et al., which is a well-studied model for information dissemination on networks. One basic protocol in this model is the so-called Push protocol which proceeds in synchronous rounds. Starting with a single node which knows of a rumor, every informed node calls in each round a random neighbor and informs it of the rumor. The Push-Pull protocol works similarly, but additionally every uninformed node calls a random neighbor and may learn the rumor from it.</p><p>It is well-known that both protocols need $\Theta(\log n)$ rounds to spread a rumor on a complete network with $n$ nodes. Here we are interested in how much the spread can be speeded by enabling nodes to make more than one call in each round. We propose a new model where the number of calls of a node is chosen independently according to a probability distribution $R$. We provide both lower and upper bounds on the rumor spreading time depending on statistical properties of $R$ such as the mean or the variance (if they exist). In particular, if $R$ follows a power law distribution with exponent $\beta \in (2,3)$, we show that the Push-Pull protocol spreads a rumor in $\Theta(\log \log n)$ rounds. Moreover when $\beta=3$, the Push-Pull protocol spreads a rumor in $\Theta(\frac{ \log n}{\log\log n})$ rounds.</p>Konstantinos Panagiotou, Ali Pourmiri, Thomas Sauerwaldhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p23Mon, 09 Feb 2015 00:00:00 +1100Polygons as Sections of Higher-Dimensional Polytopes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p24
<p>We show that every heptagon is a section of a $3$-polytope with $6$ vertices. This implies that every $n$-gon with $n\geq 7$ can be obtained as a section of a $(2+\lfloor\frac{n}{7}\rfloor)$-dimensional polytope with at most $\lceil\frac{6n}{7}\rceil$ vertices; and provides a geometric proof of the fact that every nonnegative $n\times m$ matrix of rank $3$ has nonnegative rank not larger than $\lceil\frac{6\min(n,m)}{7}\rceil$. This result has been independently proved, algebraically, by Shitov (J. Combin. Theory Ser. A 122, 2014).</p>Arnau Padrol, Julian Pfeiflehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p24Mon, 09 Feb 2015 00:00:00 +1100On a Certain Vector Crank Modulo 7
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p25
We define a vector crank to provide a combinatorial interpretation for a certain Ramanujan type congruence modulo 7.Michael D. Hirschhorn, Pee Choon Tohhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p25Mon, 09 Feb 2015 00:00:00 +1100Wieland Drift for Triangular Fully Packed Loop Configurations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p26
Triangular fully packed loop configurations (TFPLs) emerged as auxiliary objects in the study of fully packed loop configurations on a square (FPLs) corresponding to link patterns with a large number of nested arches. Wieland gyration, on the other hand, was invented to show the rotational invariance of the numbers $A_\pi$ of FPLs corresponding to a given link pattern $\pi$. The focus of this article is the definition and study of Wieland drift on TFPLs. We show that the repeated application of this operation eventually leads to a configuration that is left invariant. We also provide a characterization of such stable configurations. Finally we apply Wieland drift to the study of TFPL configurations, in particular giving new and simple proofs of several results.Sabine Beil, Ilse Fischer, Philippe Nadeauhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p26Mon, 09 Feb 2015 00:00:00 +1100A New Approach to the 2-Regularity of the $\ell$-Abelian Complexity of 2-Automatic Sequences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p27
<p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">We prove that a sequence satisfying a certain symmetry property is $2$-regular in the sense of Allouche and Shallit, i.e., the $\mathbb{Z}$-module generated by its $2$-kernel is finitely generated. We apply this theorem to develop a general approach for studying the $\ell$-abelian complexity of $2$-automatic sequences. In particular, we prove that the period-doubling word and the Thue-Morse word have $2$-abelian complexity sequences that are $2$-regular. Along the way, we also prove that the $2$-block codings of these two words have $1$-abelian complexity sequences that are $2$-regular.</p>Aline Parreau, Michel Rigo, Eric Rowland, Élise Vandommehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p27Mon, 09 Feb 2015 00:00:00 +1100Density of Gallai Multigraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p28
Diwan and Mubayi asked how many edges of each color could be included in a $3$-edge-colored multigraph containing no rainbow triangle. We answer this question under the modest assumption that the multigraphs in question contain at least one edge between every pair of vertices. We also conjecture that this assumption is, in fact, without loss of generality.Colton Magnanthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p28Mon, 16 Feb 2015 00:00:00 +1100Power of $k$ Choices and Rainbow Spanning Trees in Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p29
<p>We consider the Erd<span>ő</span>s-R<span>é</span>nyi random graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let $\mathcal{G}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,\ldots, m$) of $\mathcal{G}(n,m)$ independently chooses precisely $k \in\mathbb{N}$ colours, uniformly at random, from a given set of $n-1$ colours (one may view $e_i$ as a multi-edge). We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{G}(n,M)$ is connected and every colour occurs at least once ($M={n \choose 2}$ if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{G}(n,M)$ has a rainbow spanning tree (that is, multicoloured tree on $n$ vertices). Clearly, both properties are necessary for the desired tree to exist.</p><p>In 1994, Frieze and McKay investigated the case $k=1$ and the answer to this question is "yes" (asymptotically almost surely). However, since the sharp threshold for connectivity is $\frac {n}{2} \log n$ and the sharp threshold for seeing all the colours is $\frac{n}{k} \log n$, the case $k=2$ is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is "yes" also for $k \ge 2$.</p>Deepak Bal, Patrick Bennett, Alan Frieze, Paweł Prałathttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p29Mon, 16 Feb 2015 00:00:00 +1100Induced and Non-induced Forbidden Subposet Problems
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p30
<p>The problem of determining the maximum size $La(n,P)$ that a $P$-free subposet of the Boolean lattice $B_n$ can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of $La^*(n,P)$, the maximum size that an induced $P$-free subposet of the Boolean lattice $B_n$ can have for the case when $P$ is the complete two-level poset $K_{r,t}$ or the complete multi-level poset $K_{r,s_1,\dots,s_j,t}$ when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when $P$ is the complete three-level poset $K_{r,s,t}$. These bounds determine the asymptotics of $La(n,K_{r,s,t})$ for some values of $s$ independently of the values of $r$ and $t$.</p>Balázs Patkóshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p30Mon, 16 Feb 2015 00:00:00 +1100Maximal Clades in Random Binary Search Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p31
We study maximal clades in random phylogenetic trees with the Yule-Harding model or, equivalently, in binary search trees. We use probabilistic methods to reprove and extend earlier results on moment asymptotics and asymptotic normality. In particular, we give an explanation of the curious phenomenon observed by Drmota, Fuchs and Lee (2014) that asymptotic normality holds, but one should normalize using half the variance.Svante Jansonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p31Mon, 16 Feb 2015 00:00:00 +1100An improved lower bound related to the Furstenberg-Sárközy theorem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p32
Let $D(n)$ denote the cardinality of the largest subset of the set $\{1,2,\ldots,n\}$ such that the difference of no pair of distinct elements is a square. A well-known theorem of Furstenberg and S<span>ár</span>k<span>ö</span>zy states that $D(n)=o(n)$. In the other direction, Ruzsa has proven that $D(n) \gtrsim n^{\gamma}$ for $\gamma = \frac{1}{2}\left( 1 + \frac{\log 7}{\log 65} \right) \approx 0.733077$. We improve this to $\gamma = \frac{1}{2}\left( 1 + \frac{\log 12}{\log 205} \right) \approx 0.733412$.Mark Lewkohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p32Mon, 16 Feb 2015 00:00:00 +1100Exchangeable Pairs, Switchings, and Random Regular Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p33
<p>We consider the distribution of cycle counts in a random regular graph, which is closely linked to the graph's spectral properties. We broaden the asymptotic regime in which the cycle counts are known to be approximately Poisson, and we give an explicit bound in total variation distance for the approximation. Using this result, we calculate limiting distributions of linear eigenvalue statistics for random regular graphs.<br /> <br /> Previous results on the distribution of cycle counts by McKay, Wormald, and Wysocka (2004) used the method of switchings, a combinatorial technique for asymptotic enumeration. Our proof uses Stein's method of exchangeable pairs and demonstrates an interesting connection between the two techniques.</p>Tobias Johnsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p33Mon, 16 Feb 2015 00:00:00 +1100Between 2- and 3-Colorability
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p34
We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n$, $1<c\leq 4$. We show that for any positive integer $\ell$, there exists $\epsilon=\epsilon(\ell)$ such that if $c=1+\epsilon$ then w.h.p. $G_{n,p}$ has a homomorphism from $G_{n,p}$ to $C_{2\ell+1}$ so long as its odd-girth is at least $2\ell+1$. On the other hand, we show that if $c=4$ then w.h.p. there is no homomorphism from $G_{n,p}$ to $C_5$. Note that in our range of interest, $\chi(G_{n,p})=3$ w.h.p., implying that there is a homomorphism from $G_{n,p}$ to $C_3$. These results imply the existence of random graphs with circular chromatic numbers $\chi_c$ satisfying $2<\chi_c(G)<2+\delta$ for arbitrarily small $\delta$, and also that $2.5\leq \chi_c(G_{n,\frac 4 n})<3$ w.h.p.Alan Frieze, Wesley Pegdenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p34Mon, 16 Feb 2015 00:00:00 +1100On Limits of Dense Packing of Equal Spheres in a Cube
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p35
<p>We examine packing of $n$ congruent spheres in a cube when $n$ is close but less than the number of spheres in a regular cubic close-packed (ccp) arrangement of $\lceil p^{3}/2\rceil$ spheres. For this family of packings, the previous best-known arrangements were usually derived from a ccp by omission of a certain number of spheres without changing the initial structure. In this paper, we show that better arrangements exist for all $n\leq\lceil p^{3}/2\rceil-2$. We introduce an optimization method to reveal improvements of these packings, and present many new improvements for $n\leq4629$.</p>Milos Tatarevichttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p35Mon, 16 Feb 2015 00:00:00 +1100Conditions for the Parameters of the Block Graph of Quasi-Symmetric Designs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p36
<p>A quasi-symmetric design (QSD) is a 2-$(v,k,\lambda)$ design with intersection numbers $x$ and $y$ with $x< y$. The block graph of such a design is formed on its blocks with two distinct blocks being adjacent if they intersect in $y$ points. It is well known that the block graph of a QSD is a strongly regular graph (SRG) with parameters $(b,a,c,d)$ with smallest eigenvalue $ -m =-\frac{k-x}{y-x}$.</p><p>The classification result of SRGs with smallest eigenvalue $-m$, is used to prove that for a fixed pair $(\lambda\ge 2,m\ge 2)$, there are only finitely many QSDs. This gives partial support towards Marshall Hall Jr.'s conjecture, that for a fixed $\lambda\ge 2$, there exist finitely many symmetric $(v, k, \lambda)$-designs.</p><p>We classify QSDs with $m=2$ and characterize QSDs whose block graph is the complete multipartite graph with $s$ classes of size $3$. We rule out the possibility of a QSD whose block graph is the Latin square graph $LS_m (n)$ or complement of $LS_m (n)$, for $m=3,4$.</p><p>SRGs with no triangles have long been studied and are of current research interest. The characterization of QSDs with triangle-free block graph for $x=1$ and $y=x+1$ is obtained and the non-existence of such designs with $x=0$ or $\lambda > 2(x+2)$ or if it is a $3$-design is proven. The computer algebra system Mathematica is used to find parameters of QSDs with triangle-free block graph for $2\le m \le 100$. We also give the parameters of QSDs whose block graph parameters are $(b,a,c,d)$ listed in Brouwer's table of SRGs.</p>Rajendra M. Pawale, Mohan S. Shrikhande, Shubhada M. Nyayatehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p36Mon, 16 Feb 2015 00:00:00 +1100Modular Statistics for Subgraph Counts in Sparse Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p37
Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1,\dots, G_k$, if $p=p(n) $ is such that $\Pr(G_{n,p}\supseteq G_i)\rightarrow 1$ $\forall i$, then, with $\xi_i$ the number of copies of $G_i$ in $G_{n,p}$, $(\xi_1,\dots, \xi_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$.<br /><br />Bobby DeMarco, Jeff Kahn, Amanda Redlichhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p37Mon, 16 Feb 2015 00:00:00 +1100A Generalization of the $k$-Bonacci Sequence from Riordan Arrays
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38
<p>In this article, we introduce a family of weighted lattice paths, whose step set is $\{H=(1,0), V=(0,1), D_1=(1,1), \dots, D_{m-1}=(1,m-1)\}$. Using these lattice paths, we define a family of Riordan arrays whose sum on the rising diagonal is the $k$-bonacci sequence. This construction generalizes the Pascal and Delannoy Riordan arrays, whose sum on the rising diagonal is the Fibonacci and tribonacci sequence, respectively. From this family of Riordan arrays we introduce a generalized $k$-bonacci polynomial sequence, and we give a lattice path combinatorial interpretation of these polynomials. In particular, we find a combinatorial interpretation of tribonacci and tribonacci-Lucas polynomials.</p>José L. Ramírez, Víctor F. Sirventhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38Mon, 16 Feb 2015 00:00:00 +1100Leapfrog Constructions: From Continuant Polynomials to Permanents of Matrices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p39
<p>We study noncommutative continuant polynomials via a new leapfrog construction. This needs the introduction of new indeterminates and leads to generalizations of Fibonacci polynomials, Lucas polynomials and other families of polynomials. We relate these polynomials to various topics such as quiver algebras and tilings. Finally, we use permanents to give a broad perspective on the subject.</p>Alberto Facchini, André Leroyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p39Mon, 16 Feb 2015 00:00:00 +1100A Note on Goldbach Partitions of Large Even Integers
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p40
Let $\Sigma_{2n}$ be the set of all partitions of the even integers from the interval $(4,2n], n>2,$ into two odd prime parts. We show that $|\Sigma_{2n}| \sim 2n^2/\log^2{n}$ as $n\to\infty$. We also assume that a partition is selected uniformly at random from the set $\Sigma_{2n}$. Let $2X_n\in (4,2n]$ be the size of this partition. We prove a limit theorem which establishes that $X_n/n$ converges weakly to the maximum of two random variables which are independent copies of a uniformly distributed random variable in the interval $(0,1)$. Our method of proof is based on a classical Tauberian theorem due to Hardy, Littlewood and Karamata. We also show that the same asymptotic approach can be applied to partitions of integers into an arbitrary and fixed number of odd prime parts.Ljuben Mutafchievhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p40Wed, 25 Feb 2015 00:00:00 +1100The Maximum Difference between the Number of Atoms and Number of Coatoms of a Bruhat Interval of the Symmetric Group
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p41
<pre>We determine the largest difference between the number of atoms and number of <span>coatoms</span> of a <span>Bruhat</span> interval of the symmetric group <span>$S_n$</span>. We then pose the question of describing such <span>extremal</span> intervals <span>$[u,v] \subset S_n$</span> and give a partial description by specifying the elements <span>$v$</span> that can occur. </pre>Emmanuel Tsukermanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p41Wed, 25 Feb 2015 00:00:00 +1100Backward Jeu de Taquin Slides for Composition Tableaux and a Noncommutative Pieri Rule
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p42
<pre><span>We give a backward </span><span>jeu </span><span>de </span><span>taquin</span><span> slide analogue on </span><span>semistandard</span><span> reverse composition tableaux. These tableaux were first studied by </span><span>Haglund</span><span>, </span><span>Luoto</span><span>, Mason and van </span><span>Willigenburg</span><span> when defining quasisymmetric Schur functions. Our algorithm for performing backward </span><span>jeu </span><span>de </span><span>taquin</span><span> slides on </span><span>semistandard</span><span> reverse composition tableaux results in a natural operator on compositions that we call the </span><span>jdt</span><span> operator. This operator in turn gives rise to a new </span><span>poset</span><span> structure on compositions whose maximal chains we enumerate. As an application, we also give a noncommutative </span><span>Pieri</span><span> rule for noncommutative Schur functions that uses the </span><span>jdt</span><span> operators.</span></pre><pre><!--EndFragment--></pre>Vasu Tewarihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p42Wed, 25 Feb 2015 00:00:00 +1100Forcing Finite Minors in Sparse Infinite Graphs by Large-Degree Assumptions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p43
<p>Developing further Stein's recent notion of relative end degrees in infinite graphs, we investigate which degree assumptions can force a locally finite graph to contain a given finite minor, or a finite subgraph of given minimum or average degree. This is part of a wider project which seeks to develop an extremal theory of sparse infinite graphs.</p>Reinhard Diestelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p43Wed, 25 Feb 2015 00:00:00 +1100On Graph Parameters Guaranteeing Fast Sandpile Diffusion
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p44
<p>The Abelian Sandpile Model (Dhar 1990) is a discrete diffusion process, defined on graphs, which serves as the standard model of <em>self-organized criticality</em>. One is allowed to add <em>sand particles</em> on the nodes of the graph such that each node can stably hold at most some bounded number of particles. The particles flow through the graph as a consequence of surpassing the node capacities, until they reach a special <em>sink</em> node possessing infinite capacity. These simple dynamics give rise to a very interesting Markovian system. The transience class of a sandpile is defined as the maximum number of particles that can be added without making the system recurrent. We identify a small set of key graph properties that guarantee polynomial bounds on transience classes of the sandpile families satisfying them. These properties governing the speed of sandpile diffusion process are volume growth parameters, boundary regularity type properties and non-empty interior type constraints.</p><p>This generalizes a previous result by Babai and Gorodezky (2007), in which they establish polynomial bounds on the $n\times n$ grid. Indeed the properties we show are based on ideas extracted from their proof as well as the continuous analogs in the theory of harmonic functions.</p>Ayush Choure, Sundar Vishwanathanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p44Wed, 25 Feb 2015 00:00:00 +1100Some Results on the Structure of Multipoles in the Study of Snarks
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p45
<div>Multipoles are the pieces we obtain by cutting some edges of a cubic graph in one or more points. As a result of the cut, a multipole $M$ has vertices attached to a dangling edge with one free end, and isolated edges with two free ends. We refer to such free ends as semiedges, and to isolated edges as free edges. Every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which satisfies the Parity Lemma. Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable. Some results on the states and structure of the so-called color complete and color closed multipoles are presented. In particular, we give lower and upper linear bounds on the minimum order of a color complete multipole, and compute its exact number of states. Given two multipoles $M_1$ and $M_2$ with the same number of semiedges, we say that $M_1$ is reducible to $M_2$ if the state set of $M_2$ is a non-empty subset of the state set of $M_1$ and $M_2$ has less vertices than $M_1$. The function $v(m)$ is defined as the maximum number of vertices of an irreducible multipole with $m$ semiedges. The exact values of $v(m)$ are only known for $m\le 5$. We prove that tree and cycle multipoles are irreducible and, as a byproduct, that $v(m)$ has a linear lower bound.</div>M. A. Fiol, J. Vilaltellahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p45Wed, 25 Feb 2015 00:00:00 +1100Bipartite Graphs whose Squares are not Chromatic-Choosable
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p46
<p>The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Let $\chi(H)$ and $\chi_{\ell}(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called <em>chromatic-choosable</em> if $\chi_{\ell} (H) = \chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable.</p><p>Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that $G^2$ is chromatic-choosable for every graph $G$. Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs and are not chromatic choosable. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. Hence a natural question is whether $G^2$ is chromatic-choosable or not for every bipartite graph $G$.</p><p>In this paper, we give a bipartite graph $G$ such that $\chi_{\ell} (G^2) \neq \chi(G^2)$. Moreover, we show that the value $\chi_{\ell}(G^2) - \chi(G^2)$ can be arbitrarily large.</p>Seog-Jin Kim, Boram Parkhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p46Wed, 25 Feb 2015 00:00:00 +1100On Maltsev Digraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p47
<div class="page" title="Page 3"><div class="layoutArea"><div class="column"><p>We study digraphs preserved by a Maltsev operation: <em>Maltsev digraphs</em>. We show that these digraphs retract either onto a directed path or to the disjoint union of directed cycles, showing in this way that the constraint satisfaction problem for Maltsev digraphs is in logspace, L. We then generalize results from Kazda (2011) to show that a Maltsev digraph is preserved not only by a majority operation, but by a class of other operations (e.g., minority, Pixley) and obtain a $O(|V_G|^4)$-time algorithm to recognize Maltsev digraphs. We also prove analogous results for digraphs preserved by conservative Maltsev operations which we use to establish that the list homomorphism problem for Maltsev digraphs is in L. We then give a polynomial time characterisation of Maltsev digraphs admitting a conservative 2-semilattice operation. Finally, we give a simple inductive construction of directed acyclic digraphs preserved by a Maltsev operation, and relate them with series parallel digraphs. </p></div></div></div>Catarina Carvalho, Laszlo Egri, Marcel Jackson, Todd Nivenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p47Wed, 25 Feb 2015 00:00:00 +1100On the Longest $k$-Alternating Subsequence
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p48
We show that the longest $k$-alternating substring of a random permutation has length asymptotic to $2(n-k)/3$.<br /><br />Igor Pak, Robin Pemantlehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p48Wed, 25 Feb 2015 00:00:00 +1100Characterisations of Elementary Pseudo-Caps and Good Eggs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p49
<pre><!--StartFragment-->In this note, we use the theory of Desarguesian spreads to investigate good eggs. Thas showed that an egg in <span>$PG(4n-1,q)$</span>, <span>$q$</span> odd, with two good elements is elementary. By a short combinatorial argument, we show that a similar statement holds for large pseudo-caps, in odd and even characteristic. As a corollary, this improves and extends the result of Thas, Thas and Van Maldeghem (2006) where one needs at least <span>$4$</span> good elements of an egg in even characteristic to obtain the same conclusion. We rephrase this corollary to obtain a characterisation of the generalised quadrangle <span>$T_3(O)$</span> of Tits.</pre><pre> </pre><pre>Lavrauw (2005) characterises elementary eggs in odd characteristic as those good eggs containing a space that contains at least <span>$5$</span> elements of the egg, but not the good element. We provide an adaptation of this characterisation for weak eggs in odd and even characteristic. As a corollary, we obtain a direct geometric proof for the theorem of Lavrauw.<!--EndFragment--></pre>Sara Rottey, Geertrui Van de Voordehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p49Wed, 25 Feb 2015 00:00:00 +1100Decomposing Dense Bipartite Graphs into 4-Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p50
Let $G$ be an even bipartite graph with partite sets $X$ and $Y$ such that $|Y|$ is even and the minimum degree of a vertex in $Y$ is at least $95|X|/96$. Suppose furthermore that the number of edges in $G$ is divisible by $4$. Then $G$ decomposes into 4-cycles.Nicholas Cavenaghhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p50Wed, 25 Feb 2015 00:00:00 +1100Small Snarks with Large Oddness
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p51
<p>We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph $G$ with oddness $\omega(G)$ other than the Petersen graph has at least $5.41\, \omega(G)$ vertices, and for each integer $k$ with $2\le k\le 6$ we construct an infinite family of cubic graphs with cyclic connectivity $k$ and small oddness ratio $|V(G)|/\omega(G)$. In particular, for cyclic connectivity $2$, $4$, $5$, and $6$ we improve the upper bounds on the oddness ratio of snarks to $7.5$, $13$, $25$, and $99$ from the known values $9$, $15$, $76$, and $118$, respectively. In addition, we construct a cyclically $4$-connected snark of girth $5$ with oddness $4$ on $44$ vertices, improving the best previous value of $46$.</p>Robert Lukoťka, Edita Máčajová, Ján Mazák, Martin Škovierahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p51Wed, 25 Feb 2015 00:00:00 +1100Asymptotic Expansion of the Multi-Orientable Random Tensor Model
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p52
Three-dimensional random tensor models are a natural generalization of the celebrated matrix models. The associated tensor graphs, or 3D maps, can be classified with respect to a particular integer or half-integer, the degree of the respective graph. In this paper we analyze the general term of the asymptotic expanion in $N$, the size of the tensor, of a particular random tensor model, the multi-orientable tensor model. We perform their enumeration and we establish which are the dominant configurations of a given degree.Eric Fusy, Adrian Tanasahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p52Fri, 06 Mar 2015 00:00:00 +1100Infinite Gammoids
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p53
<p>Finite strict gammoids, introduced in the early 1970's, are matroids defined via finite digraphs equipped with some set of sinks: a set of vertices is independent if it admits a linkage to these sinks. In particular, an independent set is maximal (i.e. a base) precisely if it is linkable onto the sinks.</p><p>In the infinite setting, this characterization of the maximal independent sets need not hold. We identify a type of substructure as the unique obstruction. This allows us to prove that the sets linkable onto the sinks form the bases of a (possibly non-finitary) matroid if and only if this substructure does not occur.</p>Seyed Hadi Afzali Borujeni, Hiu-Fai Law, Malte Müllerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p53Fri, 06 Mar 2015 00:00:00 +1100Gammoids, Pseudomodularity and Flatness Degree
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p54
We introduce the concept of flatness degree for matroids, as a generalization of submodularity. This represents weaker variations of the concept of flatness which characterize strict gammoids for finite matroids. We prove that having flatness degree 3, which is the smallest non-trivial flatness degree, implies pseudomodularity on the lattice of flats of the matroid. We show however an example of a gammoid for which the converse is not true. We also show examples of gammoids with each possible flatness degree. All of this examples show that pseudomodular gammoids are not necessarily strict.Jorge Alberto Olartehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p54Fri, 06 Mar 2015 00:00:00 +1100On Shuffling of Infinite Square-Free Words
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p55
In this paper we answer two recent questions from Charlier et al. (2014) and Harju (2013) about self-shuffling words. An infinite word $w$ is called self-shuffling, if $w=\prod_{i=0}^\infty U_iV_i=\prod_{i=0}^\infty U_i=\prod_{i=0}^\infty V_i$ for some finite words $U_i$, $V_i$. Harju recently asked whether square-free self-shuffling words exist. We answer this question affirmatively. Besides that, we build an infinite word such that no word in its shift orbit closure is self-shuffling, answering positively a question of E. Charlier et al.Mike Müller, Svetlana Puzynina, Michaël Raohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p55Fri, 06 Mar 2015 00:00:00 +1100Distributions Defined by $q$-Supernomials, Fusion Products, and Demazure Modules
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p56
<p class="p1"><span class="s1">We prove asymptotic normality of the distributions defined </span><span class="s2">by $q$-supernomials, which implies asymptotic normality of the distributions given by the central string functions and the basic specialization of fusion modules of the current algebra of $\frak{sl}_</span><span class="s3">2$</span><span class="s2">. The limit is taken over </span>linearly scaled fusion powers of a fixed collection of irreducible repre<span class="s2">sentations. This includes as special instances all Demazure modules of </span><span class="s1">the affine Kac-Moody algebra associated to $\frak{</span><span class="s2">sl}_</span><span class="s3">2$</span><span class="s1">. Along with an available </span><span class="s2">complementary result on the asymptotic normality of the basic special</span>ization of graded tensors of the type $<span class="s2">A$ </span>standard representation, our <span class="s2">result is a central limit theorem for a serious class of graded tensors. It </span><span class="s1">therefore serves as an indication towards universal behavior: The central string functions and the basic specialization of fusion and, in particular, </span>Demazure modules behave asymptotically normal, as the number of <span class="s2">fusions scale linearly in an asymptotic parameter, $N$ say.</span></p>Stavros Kousidis, Ernst Schulte-Geershttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p56Fri, 06 Mar 2015 00:00:00 +1100Near-Colorings: Non-Colorable Graphs and NP-Completeness
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p57
<p>A graph $G$ is $(d_1,...,d_l)$-colorable if the vertex set of $G$ can be partitioned into subsets $V_1,\ldots ,V_l$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i \leq l$. In this paper, we focus on complexity aspects of such colorings when $l=2,3$. More precisely, we prove that, for any fixed integers $k,j,g$ with $(k,j) \neq (0,0)$ and $g\geq3$, either every planar graph with girth at least $g$ is $(k,j)$-colorable or it is NP-complete to determine whether a planar graph with girth at least $g$ is $(k,j)$-colorable. Also, for any fixed integer $k$, it is NP-complete to determine whether a planar graph that is either $(0,0,0)$-colorable or non-$(k,k,1)$-colorable is $(0,0,0)$-colorable. Additionally, we exhibit non-$(3,1)$-colorable planar graphs with girth 5 and non-$(2,0)$-colorable planar graphs with girth 7.</p><p> </p>M. Montassier, P. Ochemhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p57Fri, 06 Mar 2015 00:00:00 +1100Ascent Sequences Avoiding Pairs of Patterns
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p58
Ascent sequences were introduced by Bousquet-Melou et al. in connection with (2+2)-avoiding posets and their pattern avoidance properties were first considered by Duncan and Steingr<span>í</span>msson. In this paper, we consider ascent sequences of length $n$ avoiding two patterns of length 3, and we determine an exact enumeration for 16 different pairs of patterns. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erd<span>ő</span>s-Szekeres Theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.Andrew M. Baxter, Lara K. Pudwellhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p58Fri, 06 Mar 2015 00:00:00 +1100Summation of Rational Series Twisted by Strongly $B$-multiplicative Coefficients
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p59
<p>We evaluate in closed form series of the type $\sum u(n) R(n)$, with $(u(n))_n$ a strongly $B$-multiplicative sequence and $R(n)$ a (well-chosen) rational function. A typical example is:<br />$$<br />\sum_{n \geq 1} (-1)^{s_2(n)} \frac{4n+1}{2n(2n+1)(2n+2)} = -\frac{1}{4}<br />$$<br />where $s_2(n)$ is the sum of the binary digits of the integer $n$. Furthermore closed formulas for series involving automatic sequences that are not strongly $B$-multiplicative, such as the regular paperfolding and Golay-Shapiro-Rudin sequences, are obtained; for example, for integer $d \geq 0$:<br />$$<br />\sum_{n \geq 0} \frac{v(n)}{(n+1)^{2d+1}} = \frac{\pi^{2d+1} |E_{2d}|}{(2^{2d+2}-2)(2d)!}<br />$$<br />where $(v(n))_n$ is the $\pm 1$ regular paperfolding sequence and $E_{2d}$ is an Euler number.</p>Jean-Paul Allouche, Jonathan Sondowhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p59Fri, 06 Mar 2015 00:00:00 +1100Keeping Avoider's Graph Almost Acyclic
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p60
<p>We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$. By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non-$k$-colorability game, and the $K_t$-minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojakovi<span>ć</span>, and Szab<span>ó</span>. Moreover, we give a slight improvement for the lower bound in the non-planarity game.</p>Dennis Clemens, Julia Ehrenmüller, Yury Person, Tuan Tranhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p60Fri, 06 Mar 2015 00:00:00 +1100Closing Gaps in Problems related to Hamilton Cycles in Random Graphs and Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p61
<p>We show how to adjust a very nice coupling argument due to McDiarmid in order to prove/reprove in a novel way results concerning Hamilton cycles in various models of random graph and hypergraphs. In particular, we firstly show that for $k\geq 3$, if $pn^{k-1}/\log n$ tends to infinity, then a random $k$-uniform hypergraph on $n$ vertices, with edge probability $p$, with high probability (w.h.p.) contains a loose Hamilton cycle, provided that $(k-1)|n$. This generalizes results of Frieze, Dudek and Frieze, and reproves a result of Dudek, Frieze, Loh and Speiss. Secondly, we show that there exists $K>0$ such for every $p\geq (K\log n)/n$ the following holds: Let $G_{n,p}$ be a random graph on $n$ vertices with edge probability $p$, and suppose that its edges are being colored with $n$ colors uniformly at random. Then, w.h.p. the resulting graph contains a Hamilton cycle with for which all the colors appear (a rainbow Hamilton cycle). Bal and Frieze proved the latter statement for graphs on an even number of vertices, where for odd $n$ their $p$ was $\omega((\log n)/n)$. Lastly, we show that for $p=(1+o(1))(\log n)/n$, if we randomly color the edge set of a random directed graph $D_{n,p}$ with $(1+o(1))n$ colors, then w.h.p. one can find a rainbow Hamilton cycle where all the edges are directed in the same way.</p>Asaf Ferberhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p61Fri, 06 Mar 2015 00:00:00 +1100Lai's Conditions for Spanning and Dominating Closed Trails
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p62
<p>A graph is supereulerian if it has a spanning closed trail. For an integer $r$, let ${\cal Q}_0(r)$ be the family of 3-edge-connected nonsupereulerian graphs of order at most $r$. For a graph $G$, define $\delta_L(G)=\min\{\max\{d(u), d(v) \}| \ \mbox{ for any $uv\in E(G)$} \}$. For a given integer $p\ge 2$ and a given real number $\epsilon$, a graph $G$ of order $n$ is said to satisfy a Lai's condition if $\delta_L(G)\ge \frac{n}{p}-\epsilon$. In this paper, we show that if $G$ is a 3-edge-connected graph of order $n$ with $\delta_L(G)\ge \frac{n}{p}-\epsilon$, then there is an integer $N(p, \epsilon)$ such that when $n> N(p,\epsilon)$, $G$ is supereulerian if and only if $G$ is not a graph obtained from a graph $G_p$ in the finite family ${\cal Q}_0(3p-5)$ by replacing some vertices in $G_p$ with nontrivial graphs. Results on the best possible Lai's conditions for Hamiltonian line graphs of 3-edge-connected graphs or 3-edge-connected supereulerian graphs are given, which are improvements of the results in [J. Graph Theory 42(2003) 308-319] and in [Discrete Mathematics, 310(2010) 2455-2459].</p>Wei-Guo Chen, Zhi-Hong Chen, Mei Luhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p62Fri, 06 Mar 2015 00:00:00 +1100A Criterion for a Monomial Ideal to have a Linear Resolution in Characteristic 2
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p63
In this paper we give a necessary and sufficient combinatorial condition for a monomial ideal to have a linear resolution over fields of characteristic 2.E. Connon, Sara Faridihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p63Fri, 13 Mar 2015 00:00:00 +1100On the Number of Walks in a Triangular Domain
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p64
<p>We consider walks on a triangular domain that is a subset of the triangular lattice. We then specialise this by dividing the lattice into two directed sublattices with different weights. Our central result is an explicit formula for the generating function of walks starting at a fixed point in this domain and ending anywhere within the domain. Intriguingly, the specialisation of this formula to walks starting in a fixed corner of the triangle shows that these are equinumerous to two-coloured Motzkin paths, and two-coloured three-candidate Ballot paths, in a strip of finite height.</p>Paul R.G. Mortimer, Thomas Prellberghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p64Fri, 13 Mar 2015 00:00:00 +1100Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p65
<pre>Let <span>$X_{2k}$</span> be a set of <span>$2k$</span> labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. Two such matchings, $M$ and $M'$, are <em>disjoint compatible </em>if they do not have common edges, and no edge of $M$ crosses an edge of $M'$. Denote by $\rm{DCM}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each $k \geq 9$, the connected components of $\rm{DCM}_k$ form exactly three isomorphism classes - namely, there is a certain number of isomorphic <em>small</em> components, a certain number of isomorphic <em>medium</em> components, and one <em>big</em> component. The number and the structure of small and medium components is determined precisely.</pre>Oswin Aichholzer, Andrei Asinowski, Tillmann Miltzowhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p65Fri, 13 Mar 2015 00:00:00 +1100Sandpiles and Dominos
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p66
<p>We consider the subgroup of the abelian sandpile group of the grid graph consisting of configurations of sand that are symmetric with respect to central vertical and horizontal axes. We show that the size of this group is (i) the number of domino tilings of a corresponding weighted rectangular checkerboard; (ii) a product of special values of Chebyshev polynomials; and (iii) a double-product whose factors are sums of squares of values of trigonometric functions. We provide a new derivation of the formula due to Kasteleyn and to Temperley and Fisher for counting the number of domino tilings of a $2m \times 2n$ rectangular checkerboard and a new way of counting the number of domino tilings of a $2m \times 2n$ checkerboard on a Möbius strip.</p>Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p66Fri, 13 Mar 2015 00:00:00 +1100Faces of Birkhoff Polytopes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p67
<p>The Birkhoff polytope $B_n$ is the convex hull of all $(n\times n)$ permutation matrices, i.e., matrices where precisely one entry in each row and column is one, and zeros at all other places. This is a widely studied polytope with various applications throughout mathematics.<br /><br />In this paper we study combinatorial types $\mathcal L$ of faces of a Birkhoff polytope. The Birkhoff dimension $\mathrm{bd}(\mathcal L)$ of $\mathcal L$ is the smallest $n$ such that $B_n$ has a face with combinatorial type $\mathcal L$.<br /><br />By a result of Billera and Sarangarajan, a combinatorial type $\mathcal L$ of a $d$-dimensional face appears in some $\mathcal B_k$ for $k\le 2d$, so $\mathrm{bd}(\mathcal L)\le 2d$. We will characterize those types with $\mathrm{bd}(\mathcal L)\ge 2d-3$, and we prove that any type with $\mathrm{bd}(\mathcal L)\ge d$ is either a product or a wedge over some lower dimensional face. Further, we computationally classify all $d$-dimensional combinatorial types for $2\le d\le 8$.</p>Andreas Paffenholzhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p67Fri, 13 Mar 2015 00:00:00 +1100A Bijective Proof of the Alladi-Andrews-Gordon Partition Theorem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p68
<p>Based on the combinatorial proof of Schur's partition theorem given by Bressoud, and the combinatorial proof of Alladi's partition theorem given by Padmavathamma, Raghavendra and Chandrashekara, we obtain a bijective proof of a partition theorem of Alladi, Andrews and Gordon.</p>James J.Y. Zhaohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p68Fri, 13 Mar 2015 00:00:00 +1100On the Strength of Connectedness of a Random Hypergraph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p69
Bollob<span>á</span>s and Thomason (1985) proved that for each $k=k(n) \in [1, n-1]$, with high probability, the random graph process, where edges are added to vertex set $V=[n]$ uniformly at random one after another, is such that the stopping time of having minimal degree $k$ is equal to the stopping time of becoming $k$-(vertex-)connected. We extend this result to the $d$-uniform random hypergraph process, where $k$ and $d$ are fixed. Consequently, for $m=\frac{n}{d}(\ln n +(k-1)\ln \ln n +c)$ and $p=(d-1)! \frac{\ln n + (k-1) \ln \ln n +c}{n^{d-1}}$, the probability that the random hypergraph models $H_d(n, m)$ and $H_d(n, p)$ are $k$-connected tends to $e^{-e^{-c}/(k-1)!}.$Daniel Poolehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p69Mon, 23 Mar 2015 00:00:00 +1100A De Bruijn–Erdős Theorem for Chordal Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p70
A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chávtal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces induced by connected chordal graphs.Laurent Beaudou, Adrian Bondy, Xiaomin Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Vašek Chvátal, Nicolas Fraiman, Yori Zwolshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p70Mon, 23 Mar 2015 00:00:00 +1100Solution to a Conjecture on the Maximum Skew-Spectral Radius of Odd-Cycle Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p71
<p>Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Linear Algebra Appl. 436(12):4512-1829, 2012] showed that the spectral radius of $G^\sigma$ is the same for every orientation $\sigma$ of $G$, and equals the maximum matching root of $G$. They proposed a conjecture that the graphs which attain the maximum skew spectral radius among the odd-cycle graphs $G$ of order $n$ are isomorphic to the odd-cycle graph with one vertex degree $n-1$ and size $m=\lfloor 3(n-1)/2\rfloor$. By using the Kelmans transformation, we give a proof to the conjecture. Moreover, sharp upper bounds of the maximum matching roots of the odd-cycle graphs with given order $n$ and size $m$ are given and extremal graphs are characterized.</p>Xiaolin Chen, Xueliang Li, Huishu Lianhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p71Mon, 23 Mar 2015 00:00:00 +1100A Quantitative Approach to Perfect One-Factorizations of Complete Bipartite Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p72
<p>Given a one-factorization $\mathcal{F}$ of the complete bipartite graph $K_{n,n}$, let ${\sf pf}(\mathcal{F})$ denote the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in $\mathcal{F}$. Let ${\sf pf}(n)$ be the maximum of ${\sf pf}(\mathcal{F})$ over all one-factorizations $\mathcal{F}$ of $K_{n,n}$. In this work we prove that ${\sf pf}(n)\geq n^2/4$, for all $n\geq 2$.</p>Natacha Astromujoff, Martin Matamalahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p72Mon, 23 Mar 2015 00:00:00 +1100Crystal Structure on Rigged Configurations and the Filling Map
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p73
<p><!--StartFragment-->In this paper, we extend work of the first author on a crystal structure on rigged configurations of simply-laced type to all non-exceptional affine types using the technology of virtual rigged configurations and crystals. Under the bijection between rigged configurations and tensor products of Kirillov--Reshetikhin crystals specialized to a single tensor factor, we obtain a new tableaux model for Kirillov--Reshetikhin crystals. This is related to the model in terms of Kashiwara--Nakashima tableaux via a filling map, generalizing the recently discovered filling map in type $D_n^{(1)}$.</p>Anne Schilling, Travis Scrimshawhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p73Mon, 23 Mar 2015 00:00:00 +1100Heffter Arrays and Biembedding Graphs on Surfaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p74
<p><!--StartFragment-->A Heffter array is an $m \times n$ matrix with nonzero entries from $\mathbb{Z}_{2mn+1}$ such that<em> i)</em> every row and column sum to 0, and<em> ii)</em> exactly one of each pair $\{x,-x\}$ of nonzero elements appears in the array. We construct some Heffter arrays. These arrays are used to build current graphs used in topological graph theory. In turn, the current graphs are used to embed the complete graph $K_{2mn+1}$ so that the faces can be 2-colored, called a biembedding. Under certain conditions each color class forms a cycle system. These generalize biembeddings of Steiner triple systems. We discuss some variations including Heffter arrays with empty cells, embeddings on nonorientable surfaces, complete multigraphs, and using integer arithmetic in place of modular arithmetic.<!--EndFragment--></p>Dan Archdeaconhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p74Mon, 23 Mar 2015 00:00:00 +1100Simplicial Complexes of Whisker Type
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p75
Let $I\subset K[x_1,\ldots,x_n]$ be a zero-dimensional monomial ideal, and $\Delta(I)$ be the simplicial complex whose Stanley--Reisner ideal is the polarization of $I$. It follows from a result of Soleyman Jahan that $\Delta(I)$ is shellable. We give a new short proof of this fact by providing an explicit shelling. Moreover, we show that $\Delta(I)$ is even vertex decomposable. The ideal $L(I)$, which is defined to be the Stanley--Reisner ideal of the Alexander dual of $\Delta(I)$, has a linear resolution which is cellular and supported on a regular CW-complex. All powers of $L(I)$ have a linear resolution. We compute $\mathrm{depth}\ L(I)^k$ and show that $\mathrm{depth}\ L(I)^k=n$ for all $k\geq n$.Mina Bigdeli, Jürgen Herzog, Takayuki Hibi, Antonio Macchiahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p75Mon, 23 Mar 2015 00:00:00 +1100Vertex-Transitive Digraphs of Order $p^5$ are Hamiltonian
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p76
We prove that connected vertex-transitive digraphs of order $p^{5}$ (where $p$ is a prime) are Hamiltonian, and a connected digraph whose automorphism group contains a finite vertex-transitive subgroup $G$ of prime power order such that $G'$ is generated by two elements or elementary abelian is Hamiltonian.Jun-Yang Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p76Mon, 23 Mar 2015 00:00:00 +1100Generalized Cages
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p77
<p>Let $2 \leq k_1 < k_2 < \ldots < k_t $, $3 \leq g_1 < g_2 < \ldots < g_s < N$ be integer parameters. A $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph is a graph that contains vertices of degrees $k_1,k_2,\ldots,k_t$ but no other degrees and cycles of lengths $g_1,g_2,\dots,g_s$ but no other cycles of length $< N$. For any given set of parameters satisfying the above conditions, we present an explicit construction of $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graphs and extend the concept of a cage (a smallest graph of given degree and girth) to that of a generalized cage -- a smallest $(k_1,k_2,\ldots,k_t;g_1,g_2,\dots,g_s;N)$-graph. We introduce several infinite families of generalized cages and study their basic properties in the context of connected, bipartite, and vertex-transitive graphs, as well as combinatorial configurations (in the context of multilaterals).</p>Marko Boben, Robert Jajcay, Tomaz Pisanskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p77Mon, 23 Mar 2015 00:00:00 +1100The Distinguishing Index of Infinite Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p78
<p>The distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to vertex colourings.</p><p>We derive several bounds for infinite graphs, in particular, we prove the general bound $D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the infinite random graph and for uncountable tree-like graphs.</p><p>We also investigate the concept of the motion of edges and its relationship with the Infinite Motion Lemma.</p><p> </p>Izak Broere, Monika Pilśniakhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p78Mon, 30 Mar 2015 00:00:00 +1100Linear Relations for a Generalized Tutte Polynomial
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p79
Brylawski proved the coefficients of the Tutte polynomial of a matroid satisfy a set of linear relations. We extend these relations to a generalization of the Tutte polynomial that includes greedoids and antimatroids. This leads to families of new identities for antimatroids, including trees, posets, chordal graphs and finite point sets in $\mathbb{R}^n$. It also gives a "new" linear relation for matroids that is implied by Brylawski's identities.Gary Gordonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p79Mon, 30 Mar 2015 00:00:00 +1100Most Probably Intersecting Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p80
<p>The celebrated Erdős-Ko-Rado theorem shows that for $n \ge 2k$ the largest intersecting $k$-uniform set family on $[n]$ has size $\binom{n-1}{k-1}$. It is natural to ask how far from intersecting larger set families must be. Katona, Katona and Katona introduced the notion of most probably intersecting families, which maximise the probability of random subfamilies being intersecting.</p><p>We consider the most probably intersecting problem for $k$-uniform set families. We provide a rough structural characterisation of the most probably intersecting families and, for families of particular sizes, show that the initial segment of the lexicographic order is optimal.</p>Shagnik Das, Benny Sudakovhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p80Mon, 30 Mar 2015 00:00:00 +1100Maximal Partial Latin Cubes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p81
We prove that each maximal partial Latin cube must have more than $29.289\%$ of its cells filled and show by construction that this is a nearly tight bound. We also prove upper and lower bounds on the number of cells containing a fixed symbol in maximal partial Latin cubes and hypercubes, and we use these bounds to determine for small orders $n$ the numbers $k$ for which there exists a maximal partial Latin cube of order $n$ with exactly $k$ entries. Finally, we prove that maximal partial Latin cubes of order $n$ exist of each size from approximately half-full ($n^3/2$ for even $n\geq 10$ and $(n^3+n)/2$ for odd $n\geq 21$) to completely full, except for when either precisely $1$ or $2$ cells are empty.<br /><br />Thomas Britz, Nicholas J. Cavenagh, Henrik Kragh Sørensenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p81Mon, 30 Mar 2015 00:00:00 +1100On Graphs Having no Flow Roots in the Interval $(1,2)$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p82
For any graph $G$, let $W(G)$ be the set of vertices in $G$ of degrees larger than 3. We show that for any bridgeless graph $G$, if $W(G)$ is dominated by some component of $G - W(G)$, then $F(G,\lambda)$ has no roots in the interval (1,2), where $F(G,\lambda)$ is the flow polynomial of $G$. This result generalizes the known result that $F(G,\lambda)$ has no roots in (1,2) whenever $|W(G)| \leq 2$. We also give some constructions to generate graphs whose flow polynomials have no roots in $(1,2)$.F.M. Donghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p82Mon, 30 Mar 2015 00:00:00 +1100On the Number of Maximal Intersecting $k$-Uniform Families and Further Applications of Tuza's Set Pair Method
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p83
<p>We study the function $M(n,k)$ which denotes the number of maximal $k$-uniform intersecting families $\mathcal{F}\subseteq \binom{[n]}{k}$. Improving a bound of Balogh, Das, Delcourt, Liu and Sharifzadeh on $M(n,k)$, we determine the order of magnitude of $\log M(n,k)$ by proving that for any fixed $k$, $M(n,k) =n^{\Theta(\binom{2k}{k})}$ holds. Our proof is based on Tuza's set pair approach.</p><p>The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters.</p>Zoltán Lóránt Nagy, Balázs Patkóshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p83Mon, 30 Mar 2015 00:00:00 +1100A Deza–Frankl Type Theorem for Set Partitions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p84
<p>A set partition of $[n]$ is a collection of pairwise disjoint nonempty subsets (called blocks) of $[n]$ whose union is $[n]$. Let $\mathcal{B}(n)$ denote the family of all set partitions of $[n]$. A family $\mathcal{A} \subseteq \mathcal{B}(n)$ is said to be $m$-intersecting if any two of its members have at least $m$ blocks in common. For any set partition $P \in \mathcal{B}(n)$, let $\tau(P) = \{x: \{x\} \in P\}$ denote the union of its singletons. Also, let $\mu(P) = [n] -\tau(P)$ denote the set of elements that do not appear as a singleton in $P$. Let <br /> \begin{align*} <br />{\mathcal F}_{2t} & =\left\{P \in \mathcal{B}(n)\ : \ \vert \mu (P)\vert\leq t\right\};\\<br />{\mathcal F}_{2t+1}(i_0) & =\left\{P \in \mathcal{B}(n)\ : \ \vert\mu (P)\cap ([n]\setminus \{i_0\})\vert\leq t\right\}.<br />\end{align*} <br /> In this paper, we show that for $r\geq 3$, there exists a $n_0=n_0(r)$ depending on $r$ such that for all $n\geq n_0$, if $\mathcal{A} \subseteq\mathcal{B}(n)$ is $(n-r)$-intersecting, then <br />\[ |\mathcal{A}| \leq \begin{cases} \vert {\mathcal F}_{2t} \vert, & \text{if $r=2t$};\\<br /> \vert {\mathcal F}_{2t+1}(1) \vert, & \text{if $r=2t+1$}.<br />\end{cases}<br />\]<br />Moreover, equality holds if and only if <br />\[ \mathcal{A}= \begin{cases} {\mathcal F}_{2t}, & \text{if $r=2t$};\\<br /> {\mathcal F}_{2t+1}(i_0), & \text{if $r=2t+1$},<br />\end{cases}<br />\]<br />for some $i_0\in [n]$.</p>Cheng Yeaw Ku, Kok Bin Wonghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p84Mon, 30 Mar 2015 00:00:00 +1100