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)Thu, 03 Jul 2014 13:35:40 +1000OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60A Spectral Equivalent Condition of the $P$-polynomial Property for Association Schemes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p1
We give two equivalent conditions of the $P$-polynomial property of a symmetric association scheme. The first equivalent condition shows that the $P$-polynomial property is determined only by the first and second eigenmatrices of the symmetric association scheme. The second equivalent condition is another expression of the first using predistance polynomials.Hiroshi Nozaki, Hirotake Kuriharahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p1Thu, 03 Jul 2014 00:00:00 +1000Consecutive Up-down Patterns in Up-down Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p2
<p>In this paper, we study the distribution of the number of consecutive pattern matches of the five up-down permutations of length four, $1324$, $2314$, $2413$, $1432$, and $3412$, in the set of up-down permutations. We show that for any such $\tau$, the generating function for the distribution of the number of consecutive pattern matches of $\tau$ in the set of up-down permutations can be expressed in terms of what we call the generalized maximum packing polynomials of $\tau$. We then provide some systematic methods to compute the generalized maximum packing polynomials for such $\tau$.</p>Jeffrey B. Remmelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p2Thu, 03 Jul 2014 00:00:00 +1000A Characteristic Factor for the 3-term IP Roth Theorem in $\mathbb{Z}_3^\mathbb{N}$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p3
<p>Let $\Omega = \bigoplus_{i=1}^\infty \mathbb{Z}_3$ and $e_i = (0, \dots, 0 , 1, 0, \dots)$ where the $1$ occurs in the $i$-th coordinate. Let $\mathscr{F}=\{ \alpha \subset \mathbb{N} : \varnothing \neq \alpha, \alpha \text{ is finite} \}$. <span style="font-size: 10px;">There is a natural inclusion of $\mathscr{F}$ into $\Omega$ where $\alpha \in \mathscr{F}$ is mapped to $e_\alpha = \sum_{i \in \alpha} e_i$. We give a new proof that if $E \subset \Omega$ with $d^*(E) >0$ then there exist $\omega \in \Omega$ and $\alpha \in \mathscr{F}$ such that \[ </span><span style="font-size: 10px;">\{ \omega, \omega+ e_\alpha, \omega + 2 e_\alpha \} \subset E.\]</span><span style="font-size: 10px;">Our proof establishes that for the ergodic reformulation of the problem there is a characteristic factor that is a one step compact extension of the Kronecker factor.</span></p>Randall McCutcheon, Alistair Windsorhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p3Thu, 03 Jul 2014 00:00:00 +1000On Fence Patrolling by Mobile Agents
http://www.combinatorics.org/ojs/index.php/eljc/article/view/4063
Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the <em>idle time</em>, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.<br /><br />In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their algorithm ${\mathcal A}_2$ for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.<br /><br /><br /><br />Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóthhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/4063Thu, 10 Jul 2014 00:00:00 +1000Arc-Transitive Dihedral Regular Covers of Cubic Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p5
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span>A regular covering projection is called </span><span><em>dihedral</em> </span><span>or </span><span><em>abelian</em> </span><span>if the covering transformation group is dihedral or abelian. A lot of work has been done with regard to the classification of arc-transitive abelian (or elementary abelian, or cyclic) covers of symmetric graphs. In this paper, we investigate arc-transitive dihedral regular covers of symmetric (arc-transitive) cubic graphs. In particular, we classify all arc-transitive dihedral regular covers of $</span><span>K_</span><span>4$</span><span>, $</span><span>K_{</span><span>3</span><span>,</span><span>3}$</span><span>, the 3-cube $</span><span>Q_</span><span>3$ </span><span>and the Petersen graph.</span></p></div></div></div>Jicheng Mahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p5Thu, 10 Jul 2014 00:00:00 +1000Nordhaus-Gaddum Type Inequalities for Laplacian and Signless Laplacian Eigenvalues
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p6
<p>Let $G$ be a graph with $n$ vertices. We denote the largest signless Laplacian eigenvalue of $G$ by $q_1(G)$ and Laplacian eigenvalues of $G$ by $\mu_1(G)\ge\cdots\ge\mu_{n-1}(G)\ge\mu_n(G)=0$. It is a conjecture on Laplacian spread of graphs that $\mu_1(G)-\mu_{n-1}(G)\le n-1$ or equivalently $\mu_1(G)+\mu_1(\overline G)\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph $G$, $\mu_1(G)\mu_1(\overline G)\le n(n-1)$. Aouchiche and Hansen [<em>Discrete Appl. Math.</em> 2013] conjectured that $q_1(G)+q_1(\overline G)\le3n-4$ and $q_1(G)q_1(\overline G)\le2n(n-2)$. We prove the former and disprove the latter by constructing a family of graphs $H_n$ where $q_1(H_n)q_1(\overline{H_n})$ is about $2.15n^2+O(n)$.</p>F. Ashraf, B. Tayfeh-Rezaiehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p6Thu, 10 Jul 2014 00:00:00 +1000The Minimum Number of Nonnegative Edges in Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p7
<p>An $r$-uniform $n$-vertex hypergraph $H$ is said to have the Manickam-Miklós-Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of $H$. In this paper we show that for $n>10r^3$, every $r$-uniform $n$-vertex hypergraph with equal codegrees has the MMS property, and the bound on $n$ is essentially tight up to a constant factor. This result has two immediate corollaries. First it shows that every set of $n>10k^3$ real numbers with nonnegative sum has at least $\binom{n-1}{k-1}$ nonnegative $k$-sums, verifying the Manickam-Miklós-Singhi conjecture for this range. More importantly, it implies the vector space Manickam-Miklós-Singhi conjecture which states that for $n \ge 4k$ and any weighting on the $1$-dimensional subspaces of $\mathbb{F}_{q}^n$ with nonnegative sum, the number of nonnegative $k$-dimensional subspaces is at least ${n-1 \brack k-1}_q$. We also discuss two additional generalizations, which can be regarded as analogues of the <span>Erdős</span><span>-</span><span>Ko</span><span>-</span><span>Rado </span>theorem on $k$-intersecting families.</p>Hao Huang, Benny Sudakovhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p7Thu, 10 Jul 2014 00:00:00 +1000On the Cayley Isomorphism Problem for Cayley Objects of Nilpotent Groups of Some Orders
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p8
<p>We give a necessary condition to reduce the Cayley isomorphism problem for Cayley objects of a nilpotent or abelian group $G$ whose order satisfies certain arithmetic properties to the Cayley isomorphism problem of Cayley objects of the Sylow subgroups of $G$ in the case of nilpotent groups, and in the case of abelian groups to certain natural subgroups. As an application of this result, we show that ${\mathbb Z}_q\times{\mathbb Z}_p^2\times{\mathbb Z}_m$ is a CI-group with respect to digraphs, where $q$ and $p$ are primes with $p^2 < q$ and $m$ is a square-free integer satisfying certain arithmetic conditions (but there are no other restrictions on $q$ and $p$).</p>Edward Dobsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p8Mon, 21 Jul 2014 00:00:00 +1000Ascent-Descent Young Diagrams and Pattern Avoidance in Alternating Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p9
<p><span style="color: #000000;">We investigate pattern avoidance in alternating permutations and an alternating analogue of Young diagrams. </span><span style="color: #000000;">In particular, using an extension of </span><span style="color: #000000; text-decoration: underline;">Babson</span><span style="color: #000000;"> and West's notion of shape-</span><span style="color: #000000; text-decoration: underline;">Wilf</span><span style="color: #000000;"> equivalence </span><span style="color: #000000;">described in our recent paper (with N. </span><span style="color: #000000; text-decoration: underline;">Gowravaram</span><span style="color: #000000;">), we generalize results of </span><span style="color: #000000; text-decoration: underline;">Backelin</span><span style="color: #000000;">, West, and </span><span style="color: #000000; text-decoration: underline;">Xin </span><span style="color: #000000;">and </span><span style="color: #000000; text-decoration: underline;">Ouchterlony </span><span style="color: #000000;">to alternating permutations. Unlike </span><span style="color: #000000; text-decoration: underline;">Ouchterlony</span><span style="color: #000000;"> and Bóna</span><span style="color: #000000;">'s </span><span style="color: #000000; text-decoration: underline;">bijections</span><span style="color: #000000;">, our </span><span style="color: #000000; text-decoration: underline;">bijections</span><span style="color: #000000;"> are not the restrictions of </span><span style="color: #000000; text-decoration: underline;">Backelin</span><span style="color: #000000;">, West, and </span><span style="color: #000000; text-decoration: underline;">Xin's </span><span style="color: #000000; text-decoration: underline;">bijections</span><span style="color: #000000;"> to alternating permutations. </span><span style="color: #000000;">This paper is the second of a two-paper series presenting the work of </span><span style="color: #000000;"><em>Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux </em>(with N. </span><span style="color: #000000; text-decoration: underline;">Gowravaram</span><span style="color: #000000;">, <a href="http://arxiv.org/abs/1301.6796v1">arXiv:</a></span><a href="http://arxiv.org/abs/1301.6796v1"><span style="color: #000000;">1301.</span><span style="color: #000000; text-decoration: underline;">6796v1</span></a><span style="color: #000000;">). The first</span><span style="color: #000000;"> paper in the series is </span><span style="color: #000000;"><em>Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux</em> (with N. </span><span style="color: #000000; text-decoration: underline;">Gowravaram</span><span style="color: #000000;">, </span><span style="color: #000000;"><em>Electronic Journal of </em></span><em><span style="color: #000000;">Combinatorics </span></em><a href="/ojs/index.php/eljc/article/view/v20i4p17" target="_blank"><span style="color: #000000;">20(4):#</span></a><span style="color: #800000;"><a href="/ojs/index.php/eljc/article/view/v20i4p17" target="_blank">P17</a>,</span><span style="color: #000000;"> 2013).</span><span style="color: #000000;"><br /></span></p>Ravi Jagadeesanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p9Mon, 21 Jul 2014 00:00:00 +1000The Expected Characteristic and Permanental Polynomials of the Random Gram Matrix
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p10
<p>A $t \times n$ random matrix $A$ can be formed by sampling $n$ independent random column vectors, each containing $t$ components. The <em>random Gram matrix</em> of size $n$, $G_{n}=A^{T}A$, contains the dot products between all pairs of column vectors in the randomly generated matrix $A$, and has characteristic roots coinciding with the singular values of $A$. Furthermore, the sequences $\det{(G_{i})}$ and $\text{perm}(G_{i})$ (for $i = 0, 1, \dots, n$) are factors that comprise the expected coefficients of the characteristic and permanental polynomials of $G_{n}$. We prove theorems that relate the generating functions and recursions for the traces of matrix powers, expected characteristic coefficients, expected determinants $E(\det{(G_{n})})$, and expected permanents $E(\text{perm}(G_{n}))$ in terms of each other. Using the derived recursions, we exhibit the efficient computation of the expected determinant and expected permanent of a random Gram matrix $G_{n}$, formed according to any underlying distribution. These theoretical results may be used both to speed up numerical algorithms and to investigate the numerical properties of the expected characteristic and permanental coefficients of any matrix comprised of independently sampled columns.</p>Jacob G. Martin, E. Rodney Canfieldhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p10Mon, 21 Jul 2014 00:00:00 +1000A Counterexample to a Question of Hof, Knill and Simon
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p11
<p>In this article, we give a negative answer to a question of Hof, Knill and Simon (1995) concerning purely morphic sequences obtained from primitive morphism containing an infinite number of palindromes. Their conjecture states that such palindromic sequences arise from substitutions that are in class $\mathcal{P}$. The conjecture was proven for the binary alphabet by B. Tan in 2007. We give here a counterexample for a ternary alphabet.<br /><br /></p>Sébastien Labbéhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p11Mon, 21 Jul 2014 00:00:00 +1000Counting Results for Thin Butson Matrices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p12
A partial Butson matrix is a matrix $H\in M_{M\times N}(\mathbb Z_q)$ having its rows pairwise orthogonal, where $\mathbb Z_q\subset\mathbb C^\times$ is the group of $q$-th roots of unity. We investigate here the counting problem for these matrices in the "thin" regime, where $M=2,3,\ldots$ is small, and where $N\to\infty$ (subject to the condition $N\in p\mathbb N$ when $q=p^k>2$). The proofs are inspired from the de Launey-Levin and Richmond-Shallit counting results.Teo Banicahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p12Mon, 21 Jul 2014 00:00:00 +1000Trivial Meet and Join within the Lattice of Monotone Triangles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p13
The lattice of monotone triangles $(\mathfrak{M}_n,\leq)$ ordered by entry-wise comparisons is studied. Let $\tau_{\min}$ denote the unique minimal element in this lattice, and $\tau_{\max}$ the unique maximum. The number of $r$-tuples of monotone triangles $(\tau_1,\ldots,\tau_r)$ with minimal infimum $\tau_{\min}$ (maximal supremum $\tau_{\max}$, resp.) is shown to asymptotically approach $r|\mathfrak{M}_n|^{r-1}$ as $n \to \infty$. Thus, with high probability this event implies that one of the $\tau_i$ is $\tau_{\min}$ ($\tau_{\max}$, resp.). Higher-order error terms are also discussed.John Engbers, Adam Hammetthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p13Mon, 21 Jul 2014 00:00:00 +1000On the Strong Partition Dimension of Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p14
<p>We present a new style of metric generator in graphs. Specifically we introduce a metric generator based on a partition of the vertex set of a graph. The sets of the partition will work as the elements which will uniquely determine the position of each single vertex of the graph. A set $W$ of vertices of a connected graph $G$ strongly resolves two different vertices $x,y\notin W$ if either $d_G(x,W)=d_G(x,y)+d_G(y,W)$ or $d_G(y,W)=d_G(y,x)+d_G(x,W)$, where $d_G(x,W)=\min\left\{d(x,w)\;:\;w\in W\right\}$. An ordered vertex partition $\Pi=\left\{U_1,U_2,...,U_k\right\}$ of a graph $G$ is a strong resolving partition for $G$ if every two different vertices of $G$ belonging to the same set of the partition are strongly resolved by some set of $\Pi$. A strong resolving partition of minimum cardinality is called a strong partition basis and its cardinality the strong partition dimension. In this article we introduce the concepts of strong resolving partition and strong partition dimension and we begin with the study of its mathematical properties.</p>Ismael González Yerohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p14Fri, 25 Jul 2014 00:00:00 +1000The Weak Order on Pattern-avoiding Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p15
The weak order on the symmetric group is a well-known partial order which is also a lattice. We consider subposets of the weak order consisting of permutations avoiding a single pattern, characterizing the patterns for which the subposet is a lattice. These patterns have only a single small ascent or descent. We prove that all patterns for which the subposet is a sublattice have length at most three.Brian Drakehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p15Fri, 25 Jul 2014 00:00:00 +1000An Erdős-Ko-Rado Theorem for Permutations with Fixed Number of Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p16
<p>Let $S_{n}$ denote the set of permutations of $[n]=\{1,2,\dots, n\}$. For a positive integer $k$, define $S_{n,k}$ to be the set of all permutations of $[n]$ with exactly $k$ disjoint cycles, i.e.,<br />\[ S_{n,k} = \{\pi \in S_{n}: \pi = c_{1}c_{2} \cdots c_{k}\},\] <br />where $c_1,c_2,\dots ,c_k$ are disjoint cycles. The size of $S_{n,k}$ is $\left [ \begin{matrix}n\\ k \end{matrix}\right]=(-1)^{n-k}s(n,k)$, where $s(n,k)$ is the Stirling number of the first kind. A family $\mathcal{A} \subseteq S_{n,k}$ is said to be $t$-<em>cycle-intersecting</em> if any two elements of $\mathcal{A}$ have at least $t$ common cycles. In this paper we show that, given any positive integers $k,t$ with $k\geq t+1$, if $\mathcal{A} \subseteq S_{n,k}$ is $t$-cycle-intersecting and $n\ge n_{0}(k,t)$ where $n_{0}(k,t) = O(k^{t+2})$, then <br />\[ |\mathcal{A}| \le \left [ \begin{matrix}n-t\\ k-t \end{matrix}\right],\]<br />with equality if and only if $\mathcal{A}$ is the stabiliser of $t$ fixed points.</p>Cheng Yeaw Ku, Kok Bin Wonghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p16Fri, 25 Jul 2014 00:00:00 +1000Some Identities involving the Partial Sum of $q$-Binomial Coefficients
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p17
We give some identities involving sums of powers of the partial sum of $q$-binomial coefficients, which are $q$-analogues of Hirschhorn's identities [<em>Discrete Math.</em> 159 (1996), 273-278] and Zhang's identity [<em>Discrete Math.</em> 196 (1999), 291-298].Bing Hehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p17Fri, 25 Jul 2014 00:00:00 +1000