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>beck@math.sfsu.edu (Matthias Beck)bdm@cs.anu.edu.au (Brendan McKay)Thu, 31 Mar 2016 22:59:13 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60Decompositions of Complete Graphs into Bipartite 2-Regular Subgraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p1
It is shown that if $G$ is any bipartite 2-regular graph of order at most $n/2$ or at least $n-2$, then the obvious necessary conditions are sufficient for the existence of a decomposition of the complete graph of order $n$ into a perfect matching and edge-disjoint copies of $G$.Darryn Bryant, Andrea Burgess, Peter Danzigerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p1Fri, 01 Apr 2016 00:00:00 +1100Enumeration of Hybrid Domino-Lozenge Tilings II: Quasi-Octagonal Regions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p2
We use the subgraph replacement method to prove a simple product formula for the tilings of an 8-vertex counterpart of Propp's quasi-hexagons (Problem 16 in <em>New Perspectives in Geometric Combinatorics</em>, Cambridge University Press, 1999), called quasi-octagon.Tri Laihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p2Fri, 01 Apr 2016 00:00:00 +1100On Mixed Almost Moore Graphs of Diameter Two
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p3
Mixed almost Moore graphs appear in the context of the Degree/Diameter problem as a class of extremal mixed graphs, in the sense that their order is one less than the Moore bound for mixed graphs. The problem of their existence has been considered before for directed graphs and undirected ones, but not for the mixed case, which is a kind of generalization. In this paper we give some necessary conditions for the existence of mixed almost Moore graphs of diameter two derived from the factorization in $\mathbb{Q}[x]$ of their characteristic polynomial. In this context, we deal with the irreducibility of $\Phi_i(x^2+x-(r-1))$, where $\Phi_i(x)$ denotes the i-th cyclotomic polynomial.Nacho López, Josep M. Mirethttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p3Fri, 01 Apr 2016 00:00:00 +1100Cyclic Sieving and Rational Catalan Theory
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p4
<p>Let $a < b$ be coprime positive integers. Armstrong, Rhoades, and Williams (2013) defined a set NC(a,b) of `rational noncrossing partitions', which form a subset of the ordinary noncrossing partitions of $\{1, 2, \dots, b-1\}$. Confirming a conjecture of Armstrong et. al., we prove that NC(a,b) is closed under rotation and prove an instance of the cyclic sieving phenomenon for this rotational action. We also define a rational generalization of the $\mathfrak{S}_a$-noncrossing parking functions of Armstrong, Reiner, and Rhoades.</p>Michelle Bodnar, Brendon Rhoadeshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p4Fri, 25 Mar 2016 14:33:01 +1100Blocking and Double Blocking Sets in Finite Planes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p5
<p>In this paper, by using properties of Baer subplanes, we describe the construction of a minimal blocking set in the Hall plane of order q<sup>2</sup> of size q<sup>2</sup>+2q+2 admitting $1-$, $2-$, $3-$, $4-$, $(q+1)-$ and $(q+2)-$secants. As a corollary, we obtain the existence of a minimal blocking set of a non-Desarguesian affine plane of order $q^2$ of size at most $4q^2/3+5q/3$, which is considerably smaller than $2q^2-1$, the Jamison bound for the size of a minimal blocking set in an affine Desarguesian plane of order $q^2$.</p><p>We also consider particular André planes of order $q$, where $q$ is a power of the prime $p$, and give a construction of a small minimal blocking set which admits a secant line not meeting the blocking set in $1$ mod $p$ points. Furthermore, we elaborate on the connection of this problem with the study of value sets of certain polynomials and with the construction of small double blocking sets in Desarguesian projective planes; in both topics we provide some new results.</p>Jan De Beule, Tamás Héger, Tamás Szőnyi, Geertrui Van de Voordehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p5Fri, 01 Apr 2016 00:00:00 +1100On Snarks that are far from being 3-Edge Colorable
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p6
In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices. Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.Jonas Hägglundhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p6Fri, 15 Apr 2016 00:00:00 +1000Evaluations of Hecke Algebra Traces at Kazhdan-Lusztig Basis Elements
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p7
For irreducible characters $\{ \chi_q^\lambda \,|\, \lambda \vdash n \}$, induced sign characters $\{ \epsilon_q^\lambda \,|\, \lambda \vdash n \}$, and induced trivial characters $\{ \eta_q^\lambda \,|\, \lambda \vdash n \}$ of the Hecke algebra $H_n(q)$, and Kazhdan-Lusztig basis elements $C'_w(q)$ with $w$ avoiding the patterns 3412 and 4231, we combinatorially interpret the polynomials $\smash{\chi_q^\lambda(q^{\ell(w)/2} C'_w(q))}$, $\smash{\epsilon_q^\lambda(q^{\ell(w)/2} C'_w(q))}$, and $\smash{\eta_q^\lambda(q^{\ell(w)/2} C'_w(q))}$. This gives a new algebraic interpretation of chromatic quasisymmetric functions of Shareshian and Wachs, and a new combinatorial interpretation of special cases of results of Haiman. We prove similar results for other $H_n(q)$-traces, and confirm a formula conjectured by Haiman.<br /><br /><br />Samuel Clearman, Matthew Hyatt, Brittany Shelton, Mark Skanderahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p7Fri, 15 Apr 2016 00:00:00 +1000Pairs of Quadratic Forms over Finite Fields
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p8
Let $\mathbb{F}_q$ be a finite field with $q$ elements and let $X$ be a set of matrices over $\mathbb{F}_q$. The main results of this paper are explicit expressions for the number of pairs $(A,B)$ of matrices in $X$ such that $A$ has rank $r$, $B$ has rank $s$, and $A+B$ has rank $k$ in the cases that (i) $X$ is the set of alternating matrices over $\mathbb{F}_q$ and (ii) $X$ is the set of symmetric matrices over $\mathbb{F}_q$ for odd $q$. Our motivation to study these sets comes from their relationships to quadratic forms. As one application, we obtain the number of quadratic Boolean functions that are simultaneously bent and negabent, which solves a problem due to Parker and Pott.Alexander Pott, Kai-Uwe Schmidt, Yue Zhouhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p8Fri, 15 Apr 2016 00:00:00 +1000Nice Reflection Arrangements
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p9
<p>The aim of this note is a classification of all nice and all inductively factored reflection arrangements. It turns out that apart from the supersolvable instances only the monomial groups $G(r,r,3)$ for $r \ge 3$ give rise to nice reflection arrangements. As a consequence of this and of the classification of all inductively free reflection arrangements from Hoge and Röhrle (2015) we deduce that the class of all inductively factored reflection arrangements coincides with the class of all supersolvable reflection arrangements. Moreover, we extend these classifications to hereditarily factored and hereditarily inductively factored reflection arrangements.</p>Torsten Hoge, Gerhard Röhrlehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p9Fri, 15 Apr 2016 00:00:00 +1000Locally Convex Words and Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p10
We introduce some new classes of words and permutations characterized by the second difference condition $\pi(i-1) + \pi(i+1) - 2\pi(i) \leq k$, which we call the $k$-convexity condition. We demonstrate that for any sized alphabet and convexity parameter $k$, we may find a generating function which counts $k$-convex words of length $n$. We also determine a formula for the number of 0-convex words on any fixed-size alphabet for sufficiently large $n$ by exhibiting a connection to integer partitions. For permutations, we give an explicit solution in the case $k = 0$ and show that the number of 1-convex and 2-convex permutations of length $n$ are $\Theta(C_1^n)$ and $\Theta(C_2^n)$, respectively, and use the transfer matrix method to give tight bounds on the constants $C_1$ and $C_2$. We also providing generating functions similar to the the continued fraction generating functions studied by Odlyzko and Wilf in the "coins in a fountain" problem.Christopher Coscia, Jonathan DeWitthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p10Fri, 15 Apr 2016 00:00:00 +1000An Improved Bound on the Sizes of Matchings Guaranteeing a Rainbow Matching
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p11
<pre>A conjecture by <span>Aharoni</span> and Berger states that every family of <span>$n$</span> matchings of size <span>$n+1$</span> in a bipartite <span>multigraph</span> contains a rainbow matching of size <span>$n$</span>. In this paper we prove that matching sizes of <span>$\left(\frac 3 2 + o(1)\right) n$</span> suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size <span>$n-1$</span>. This improves previous results by <span>Aharoni</span>, <span>Charbit</span> and Howard, and <span>Kotlar</span> and <span>Ziv</span>. </pre>Dennis Clemens, Julia Ehrenmüllerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p11Fri, 15 Apr 2016 00:00:00 +1000Weakly Distance-Regular Digraphs of Valency Three, I
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p12
Suzuki (2004) classified thin weakly distance-regular digraphs and proposed the project to classify weakly distance-regular digraphs of valency 3. The case of girth 2 was classified by the third author (2004) under the assumption of the commutativity. In this paper, we continue this project and classify these digraphs with girth more than 2 and two types of arcs.Yuefeng Yang, Benjian Lv, Kaishun Wanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p12Fri, 15 Apr 2016 00:00:00 +1000The Bondage Number of Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p13
A dominating set of a graph is a subset $D$ of its vertices such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number of a graph $G$ is the number of vertices in a smallest dominating set of $G$. The bondage number of a nonempty graph $G$ is the size of a smallest set of edges whose removal from $G$ results in a graph with domination number greater than the domination number of $G$. In this note, we study the bondage number of the binomial random graph $G(n,p)$. We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of $G(n,p)$ under certain restrictions.Dieter Mitsche, Xavier Pérez-Giménez, Paweł Prałathttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p13Fri, 15 Apr 2016 00:00:00 +1000The Peak Statistics on Simsun Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p14
In this paper, we study the relationship among left peaks, interior peaks and up-down runs of simsun permutations. Properties of the generating polynomials, including the recurrence relation, generating function and real-rootedness are studied. Moreover, we introduce and study simsun permutations of the second kind.Shi-Mei Ma, Yeong-Nan Yehhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p14Fri, 15 Apr 2016 00:00:00 +1000Increasing Paths in Edge-Ordered Graphs: The Hypercube and Random Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p15
An <em>edge-ordering</em> of a graph $G=(V,E)$ is a bijection $\phi:E\to\{1,2,\ldots,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\ldots,e_k$ is an <em>increasing path</em> if it is a path in $G$ which satisfies $\phi(e_i)<\phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $\ell$ such that every edge-ordering of $G$ contains an increasing path of length $\ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.Jessica De Silva, Theodore Molla, Florian Pfender, Troy Retter, Michael Taithttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p15Fri, 15 Apr 2016 00:00:00 +1000Graphs with no $\bar P_7$-Minor
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p16
<span style="color: #000000;">Let </span><span style="color: #008000;">$\bar P_7$</span><span style="color: #000000;"> denote the complement of a path on seven vertices. We determine all 4-connected graphs that do not contain </span><span style="color: #008000;">$\bar P_7$</span><span style="color: #000000;"> as a minor.</span>Guoli Ding, Chanun Lewchalermvongs, John Maharryhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p16Fri, 15 Apr 2016 00:00:00 +1000On the Staircases of Gyárfás
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p17
<p>In a 2011 paper, Gyárfás investigated a geometric Ramsey problem on convex, separated, balanced, geometric $K_{n,n}$. This led to appealing extremal problem on square 0-1 matrices. Gyárfás conjectured that any 0-1 matrix of size $n\times n$ has a staircase of size $n-1$.<br /><br />We introduce the non-symmetric version of Gyárfás' problem. We give upper bounds and in certain range matching lower bound on the corresponding extremal function. In the square/balanced case we improve the $(4/5+\epsilon)n$ lower bound of Cai, Gyárfás et al. to $5n/6-7/12$. We settle the problem when instead of considering maximum staircases we deal with the sum of the size of the longest $0$- and $1$-staircases.</p>János Csányi, Peter Hajnal, Gábor V. Nagyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p17Fri, 15 Apr 2016 00:00:00 +1000Locally 3-Arc-Transitive Regular Covers of Complete Bipartite Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p18
<span>In this paper, locally $3$-arc-transitive regular covers of complete bipartite graphs are studied, and results are obtained that apply to arbitrary covering transformation groups. In particular, methods are obtained for classifying the locally $3$-arc-transitive graphs with a prescribed covering transformation group, and these results are applied to classify the locally $3$-arc-transitive regular covers of complete bipartite graphs with covering transformation group isomorphic to a cyclic group or an elementary abelian group of order $p^2$.</span>Eric Swartzhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p18Fri, 29 Apr 2016 00:00:00 +1000Abelian Cayley Digraphs with Asymptotically Large Order for Any Given Degree
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p19
Abelian Cayley digraphs can be constructed by using a generalization to $\mathbb{Z}^n$ of the concept of congruence in $\mathbb{Z}$. <span style="font-size: 10px;">Here we use this approach to present a family of such digraphs, which, for every fixed value of the degree, have asymptotically large number of vertices as the diameter increases. Up to now, the best known large dense results were all non-constructive.</span>Francesc Aguiló, Miquel Àngel Fiol, Sonia Pérezhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p19Fri, 29 Apr 2016 00:00:00 +1000Inverse Expander Mixing for Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p20
We formulate and prove inverse mixing lemmas in the settings of simplicial complexes and $k$-uniform hypergraphs. In the hypergraph setting, we extend results of Bilu and Linial for graphs. In the simplicial complex setting, our results answer a question of Parzanchevski et al.Emma Cohen, Dhruv Mubayi, Peter Ralli, Prasad Tetalihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p20Fri, 29 Apr 2016 00:00:00 +1000Multi-Eulerian Tours of Directed Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p21
<span>Not every graph has an Eulerian tour. But every finite, strongly connected graph has a multi-Eulerian tour, which we define as a closed path that uses each directed edge at least once, and uses edges e and f the same number of times whenever tail(e)=tail(f). This definition leads to a simple generalization of the BEST Theorem. We then show that the minimal length of a multi-Eulerian tour is bounded in terms of the Pham index, a measure of 'Eulerianness'.</span>Matthew Farrell, Lionel Levinehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p21Fri, 29 Apr 2016 00:00:00 +1000On Isomorphisms of Vertex-transitive Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p22
The isomorphism problem of Cayley graphs has been well studied in the literature, such as characterizations of CI (DCI)-graphs and CI (DCI)-groups. In this paper, we generalize these to vertex-transitive graphs and establish parallel results. Some interesting vertex-transitive graphs are given, including a first example of connected symmetric non-Cayley non-GI-graph. Also, we initiate the study for GI and DGI-groups, defined analogously to the concept of CI and DCI-groups.Jing Chen, Binzhou Xiahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p22Fri, 29 Apr 2016 00:00:00 +1000Completing Partial Latin Squares with One Nonempty Row, Column, and Symbol
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p23
<p>Let $r,c,s\in\{1,2,\ldots,n\}$ and let $P$ be a partial latin square of order $n$ in which each nonempty cell lies in row $r$, column $c$, or contains symbol $s$. We show that if $n\notin\{3,4,5\}$ and row $r$, column $c$, and symbol $s$ can be completed in $P$, then a completion of $P$ exists. As a consequence, this proves a conjecture made by Casselgren and Häggkvist. Furthermore, we show exactly when row $r$, column $c$, and symbol $s$ can be completed.</p>Jaromy Kuhl, Michael W. Schroederhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p23Fri, 29 Apr 2016 00:00:00 +1000Variations on a theme of Kasteleyn, with Application to the Totally Nonnegative Grassmannian
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p24
We provide a short proof of a classical result of Kasteleyn, and prove several variants thereof. One of these results has become key in the parametrization of positroid varieties, and thus deserves the short direct proof which we provide.<br /><br />David E Speyerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p24Fri, 29 Apr 2016 00:00:00 +1000Brick Manifolds and Toric Varieties of Brick Polytopes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p25
<p>Bott-Samelson varieties are a twisted product of $\mathbb{C}\mathbb{P}^1$'s with a map into $G/B$. These varieties are mostly studied in the case in which the map into $G/B$ is birational to the image; however in this paper we study a fiber of this map when it is not birational. We prove that in some cases the general fiber, which we christen a brick manifold, is a toric variety. In order to do so we use the moment map of a Bott-Samelson variety to translate this problem into one in terms of the "subword complexes" of Knutson and Miller. Pilaud and Stump realized certain subword complexes as the dual of the boundary of a polytope which generalizes the brick polytope defined by Pilaud and Santos. For a nice family of words, the brick polytope is the generalized associahedron realized by Hohlweg, Lange and Thomas. These stories connect in a nice way: we show that the moment polytope of the brick manifold is the brick polytope. In particular, we give a nice description of the toric variety of the associahedron. We give each brick manifold a stratification dual to the subword complex. In addition, we relate brick manifolds to Brion's resolutions of Richardon varieties.</p>Laura Escobarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p25Fri, 29 Apr 2016 00:00:00 +1000