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 +1100