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, 02 Oct 2014 06:05:01 +1000OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60The Optimal Drawings of $K_{5,n}$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p1
<p>Zarankiewicz's Conjecture (ZC) states that the crossing number cr$(K_{m,n})$ equals $Z(m,n):=\lfloor{\frac{m}{2}}\rfloor \lfloor{\frac{m-1}{2}}\rfloor \lfloor{\frac{n}{2}}\rfloor \lfloor{\frac{n-1}{2}}\rfloor$. Since Kleitman's verification of ZC for $K_{5,n}$ (from which ZC for $K_{6,n}$ easily follows), very little progress has been made around ZC; the most notable exceptions involve computer-aided results. With the aim of gaining a more profound understanding of this notoriously difficult conjecture, we investigate the <em>optimal</em> (that is, crossing-minimal) drawings of $K_{5,n}$. The widely known natural drawings of $K_{m,n}$ (the so-called <em>Zarankiewicz drawings</em>) with $Z(m,n)$ crossings contain <em>antipodal</em> vertices, that is, pairs of degree-$m$ vertices such that their induced drawing of $K_{m,2}$ has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr$(K_{5,n}) = Z(5,n)$. We explore in depth the role of antipodal vertices in optimal drawings of $K_{5,n}$, for $n$ even. We prove that if {$n \equiv 2$ (mod $4$)}, then every optimal drawing of $K_{5,n}$ has antipodal vertices. We also exhibit a two-parameter family of optimal drawings $D_{r,s}$ of $K_{5,4(r+s)}$ (for $r,s\ge 0$), with no antipodal vertices, and show that if $n\equiv 0$ (mod $4$), then every optimal drawing of $K_{5,n}$ without antipodal vertices is (vertex rotation) isomorphic to $D_{r,s}$ for some integers $r,s$. As a corollary, we show that if $n$ is even, then every optimal drawing of $K_{5,n}$ is the superimposition of Zarankiewicz drawings with a drawing isomorphic to $D_{r,s}$ for some nonnegative integers $r,s$.</p>César Hernández-Vélez, Carolina Medina, Gelasio Salazarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p1Thu, 02 Oct 2014 00:00:00 +1000Limits of Boolean Functions on $\mathbb{F}_p^n$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p2
<p>We study sequences of functions of the form $\mathbb{F}_p^n \to \{0,1\}$ for varying $n$, and define a notion of convergence based on the induced distributions from restricting the functions to a random affine subspace. Using a decomposition theorem and a recently proven equi-distribution theorem from higher order Fourier analysis, we prove that the limits of such convergent sequences can be represented by certain measurable functions. We also show that every such limit object arises as the limit of some sequence of functions. These results are in the spirit of similar results which have been developed for limits of graph sequences. A more general, albeit substantially more sophisticated, limit object was recently constructed by Balázs Szegedy [Gowers norms, regularization and limits of functions on abelian groups. 2010. arXiv:1010.6211].</p>Hamed Hatami, Pooya Hatami, James Hirsthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p2Thu, 02 Oct 2014 00:00:00 +1000Permutation Reconstruction from Differences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3
We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is $\sf{NP}$-complete. As an intermediate step we first prove the $\sf{NP}$-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.Marzio De Biasihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3Thu, 02 Oct 2014 00:00:00 +1000Isometric Embeddings of Half-Cube Graphs in Half-Spin Grassmannians
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p4
Let $\Pi$ be a polar space of type $\textsf{D}_{n}$. Denote by ${\mathcal G}_{\delta}(\Pi)$, $\delta\in \{+,-\}$ the associated half-spin Grassmannians and write $\Gamma_{\delta}(\Pi)$ for the corresponding half-spin Grassmann graphs. In the case when $n\ge 4$ is even, the apartments of ${\mathcal G}_{\delta}(\Pi)$ will be characterized as the images of isometric embeddings of the half-cube graph $\frac{1}{2}H_n$ in $\Gamma_{\delta}(\Pi)$. As an application, we describe all isometric embeddings of $\Gamma_{\delta}(\Pi)$ in the half-spin Grassmann graphs associated to a polar space of type $\textsf{D}_{n'}$ under the assumption that $n\ge 6$ is even.Mark Pankovhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p4Thu, 02 Oct 2014 00:00:00 +1000An Extension of Turán's Theorem, Uniqueness and Stability
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p5
We determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $M\subset V(G)$. For $(r-1)|M|\ge n$, the $(r-1)$-partite Turán graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguethttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p5Thu, 02 Oct 2014 00:00:00 +1000Coxeter-Knuth Graphs and a Signed Little Map for Type B Reduced Words
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p6
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span>We define an analog of David Little’s algorithm for reduced words in type B, and investigate its main properties. In particular, we show that our algorithm preserves the recording tableau of Kra<span>ś</span>kiewicz insertion, and that it provides a bijective realization of the Type B transition equations in Schubert calculus. Many other aspects of type A theory carry over to this new setting. Our primary tool is a shifted version of the dual equivalence graphs defined by Assaf and further developed by Roberts. We provide an axiomatic characterization of shifted dual equivalence graphs, and use them to prove a structure theorem for the graph of Type B Coxeter-Knuth relations. </span></p></div></div></div>Sara Billey, Zachary Hamaker, Austin Roberts, Benjamin Younghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p6Thu, 02 Oct 2014 00:00:00 +1000Enumerating Hamiltonian Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7
<p style="-qt-block-indent: 0; text-indent: 0px; -qt-user-state: 0; margin: 0px;">A dynamic programming method for enumerating hamiltonian cycles in arbitrary graphs is presented. The method is applied to grid graphs, king's graphs, triangular grids, and three-dimensional grid graphs, and results are obtained for larger cases than previously published. The approach can easily be modified to enumerate hamiltonian paths and other similar structures.</p>Ville H. Petterssonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7Thu, 09 Oct 2014 00:00:00 +1100New Infinite Families of Congruences Modulo 8 for Partitions with Even Parts Distinct
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p8
Let $ped(n)$ denote the number of partitions of an integer $n$ wherein even parts are distinct. Recently, Andrews, Hirschhorn and Sellers, Chen, and Cui and Gu have derived a number of interesting congruences modulo 2, 3 and 4 for $ped(n)$. In this paper we prove several new infinite families of congruences modulo 8 for $ped(n)$. For example, we prove that for $ \alpha \geq 0$ and $n\geq 0$,<br />\[<br /> ped\left(3^{4\alpha+4}n+\frac{11\times 3^{4\alpha+3}-1}{8}\right)\equiv 0 \ ({\rm mod \ 8}).<br />\]Ernest X. W. Xiahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p8Thu, 09 Oct 2014 00:00:00 +1100Graph Homomorphisms between Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p9
<p>In this paper we study several problems concerning the number of homomorphisms of trees. We begin with an algorithm for the number of homomorphisms from a tree to any graph. By using this algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization and a dual of <span>Bollobás</span> and Tyomkyn's result concerning the number of walks in trees.</p><p>Some other main results of the paper are the following. Denote by $\hom(H,G)$ the number of homomorphisms from a graph $H$ to a graph $G$. For any tree $T_m$ on $m$ vertices we give a general lower bound for $\hom(T_m,G)$ by certain entropies of Markov chains defined on the graph $G$. As a particular case, we show that for any graph $G$, <br />$$\exp(H_{\lambda}(G))\lambda^{m-1}\leq\hom(T_m,G),$$ <br />where $\lambda$ is the largest eigenvalue of the adjacency matrix of $G$ and $H_{\lambda}(G)$ is a certain constant depending only on $G$ which we call the spectral entropy of $G$. We also show that if $T_m$ is any fixed tree and<br />$$\hom(T_m,P_n)>\hom(T_m,T_n),$$for some tree $T_n$ on $n$ vertices, then $T_n$ must be the tree obtained from a path $P_{n-1}$ by attaching a pendant vertex to the second vertex of $P_{n-1}$.</p><p>All the results together enable us to show that among all trees with fixed number of vertices, the path graph has the fewest number of endomorphisms while the star graph has the most.</p>Péter Csikvári, Zhicong Linhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p9Thu, 09 Oct 2014 00:00:00 +1100The Range of a Simple Random Walk on $\mathbb{Z}$: An Elementary Combinatorial Approach
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p10
<p>Two different elementary approaches for deriving an explicit formula for the distribution of the range of a simple random walk on $\mathbb{Z}$ of length $n$ are presented. Both of them rely on Hermann Weyl's discrepancy norm, which equals the maximal partial sum of the elements of a sequence. By this the original combinatorial problem on $\mathbb{Z}$ can be turned into a known path-enumeration problem on a bounded lattice. The solution is provided by means of the adjacency matrix $\mathbf Q_d$ of the walk on a bounded lattice $(0,1,\ldots,d)$. The second approach is algebraic in nature, and starts with the adjacency matrix $\mathbf{Q_d}$. The powers of the adjacency matrix are expanded in terms of products of non-commutative left and right shift matrices. The representation of such products by means of the discrepancy norm reveals the solution directly.</p>Bernhard A. Moserhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p10Thu, 09 Oct 2014 00:00:00 +1100Operators of Equivalent Sorting Power and Related Wilf-equivalences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p11
We study sorting operators $\mathbf{A}$ on permutations that are obtained composing Knuth's stack sorting operator $\mathbf{S}$ and the reversal operator $\mathbf{R}$, as many times as desired. For any such operator $\mathbf{A}$, we provide a size-preserving bijection between the set of permutations sorted by $\mathbf{S} \circ \mathbf{A}$ and the set of those sorted by $\mathbf{S} \circ \mathbf{R} \circ \mathbf{A}$, proving that these sets are enumerated by the same sequence, but also that many classical permutation statistics are equidistributed across these two sets. The description of this family of bijections is based on a bijection between the set of permutations avoiding the pattern $231$ and the set of those avoiding $132$ which preserves many permutation statistics. We also present other properties of this bijection, in particular for finding pairs of Wilf-equivalent permutation classes.<br /><br />Michael Albert, Mathilde Bouvelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p11Thu, 09 Oct 2014 00:00:00 +1100$k$-Fold Sidon Sets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p12
Let $k \geq 1$ be an integer. A set $A \subset \mathbb{Z}$ is a $k$<em>-fold Sidon set </em>if $A$ has only trivial solutions to each equation of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 = 0$ where $0 \leq |c_i | \leq k$, and $c_1 + c_2 + c_3 + c_4 = 0$. We prove that for any integer $k \geq 1$, a $k$-fold Sidon set $A \subset [N]$ has at most $(N/k)^{1/2} + O((Nk)^{1/4})$ elements. Indeed we prove that given any $k$ positive integers $c_1<\cdots <c_k$, any set $A\subset [N]$ that contains only trivial solutions to $c_i(x_1-x_2)=c_j(x_3-x_4)$ for each $1 \le i \le j \le k$, has at most $(N/k)^{1/2}+O((c_k^2N/k)^{1/4})$ elements. On the other hand, for any $k \geq 2$ we can exhibit $k$ positive integers $c_1,\dots, c_k$ and a set $A\subset [N]$ with $|A|\ge (\frac 1k+o(1))N^{1/2}$, such that $A$ has only trivial solutions to $c_i(x_1 - x_2) = c_j (x_3 - x_4)$ for each $1 \le i \le j\le k$.Javier Cilleruelo, Craig Timmonshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p12Thu, 09 Oct 2014 00:00:00 +1100On Sets with Few Intersection Numbers in Finite Projective and Affine Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p13
<p>In this paper we study sets $X$ of points of both affine and projective spaces over the Galois field $\mathop{\rm{GF}}(q)$ such that every line of the geometry that is neither contained in $X$ nor disjoint from $X$ meets the set $X$ in a constant number of points and we determine all such sets. This study has its main motivation in connection with a recent study of neighbour transitive codes in Johnson graphs by Liebler and Praeger [<em>Designs, Codes and Crypt.</em>, 2014]. We prove that, up to complements, in $\mathop{\rm{PG}}(n,q)$ such a set $X$ is either a subspace or $n=2,q$ is even and $X$ is a maximal arc of degree $m$. In $\mathop{\rm{AG}}(n,q)$ we show that $X$ is either the union of parallel hyperplanes or a cylinder with base a maximal arc of degree $m$ (or the complement of a maximal arc) or a cylinder with base the projection of a quadric. Finally we show that in the affine case there are examples (different from subspaces or their complements) in $\mathop{\rm{AG}}(n,4)$ and in $\mathop{\rm{AG}}(n,16)$ giving new neighbour transitive codes in Johnson graphs.</p>Nicola Durantehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p13Thu, 16 Oct 2014 00:00:00 +1100Mutations of Fake Weighted Projective Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p14
We characterise mutations between fake weighted projective spaces, and give explicit formulas for how the weights and multiplicity change under mutation. In particular, we prove that multiplicity-preserving mutations between fake weighted projective spaces are mutations over edges of the corresponding simplices. As an application, we analyse the canonical and terminal fake weighted projective spaces of maximal degree.Tom Coates, Samuel Gonshaw, Alexander Kasprzyk, Navid Nabijouhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p14Thu, 16 Oct 2014 00:00:00 +1100The Combinatorial Nullstellensätze Revisited
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p15
We revisit and further explore the celebrated Combinatorial Nullstellensätze of N. Alon in several different directions.Pete L. Clarkhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p15Thu, 16 Oct 2014 00:00:00 +1100Decomposing Labeled Interval Orders as Pairs of Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p16
We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.Anders Claesson, Stuart A. Hannahhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p16Thu, 16 Oct 2014 00:00:00 +1100Chromatic Bounds on Orbital Chromatic Roots
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p17
<p><!--StartFragment-->Given a group $G$ of automorphisms of a graph $\Gamma$, the orbital chromatic polynomial $OP_{\Gamma,G}(x)$ is the polynomial whose value at a positive integer $k$ is the number of orbits of $G$ on proper $k$-colorings of $\Gamma.$ Cameron and Kayibi introduced this polynomial as a means of understanding roots of chromatic polynomials. In this light, they posed a problem asking whether the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root of its chromatic polynomial. We resolve this problem in a resounding negative by not only constructing a counterexample, but by providing a process for generating families of counterexamples. We additionally begin the program of finding classes of graphs whose orbital chromatic polynomials have real roots bounded above by the largest real root of their chromatic polynomials; in particular establishing this for many outerplanar graphs.<!--EndFragment--></p>Dae Hyun Kim, Alexander H. Mun, Mohamed Omarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p17Thu, 23 Oct 2014 00:00:00 +1100Enumerating Permutations by their Run Structure
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p18
<p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">Motivated by a problem in quantum field theory, we study the up and down structure of circular and linear permutations. In particular, we count the length of the (alternating) runs of permutations by representing them as monomials and find that they can always be decomposed into so-called 'atomic' permutations introduced in this work. This decomposition allows us to enumerate the (circular) permutations of a subset of $\mathbb{N}$ by the length of their runs. Furthermore, we rederive, in an elementary way and using the methods developed here, a result due to Kitaev on the enumeration of valleys.</p>Christopher J. Fewster, Daniel Siemssenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p18Thu, 23 Oct 2014 00:00:00 +1100Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19
<p>Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width.</p><p>This extends known results on rapid mixing for the Tutte polynomial, adjacency-rank ($R_2$-)polynomial and interlace polynomial. In particular Glauber dynamics for the $R_2$-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.</p>Magnus Bordewich, Ross J. Kanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19Thu, 23 Oct 2014 00:00:00 +1100