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