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 (Andre Kundgen)bdm@cs.anu.edu.au (Brendan McKay)Fri, 16 Oct 2015 12:28:18 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60The Spectrum for $3$-Way $k$-Homogeneous Latin Trades
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p1
<p>A $\mu$-way $k$-homogeneous Latin trade was defined by Bagheri Gh, Donovan, Mahmoodian (2012), where the existence of $3$-way $k$-homogeneous Latin trades was specifically investigated. We investigate the existence of a certain class of $\mu$-way $k$-homogeneous Latin trades with an idempotent like property. We present a number of constructions for $\mu$-way $k$-homogeneous Latin trades with this property, and show that these can be used to fill in the spectrum of $3$-way $k$-homogeneous Latin trades for all but $196$ possible exceptions.</p><p> </p>Trent G. Marbach, Lijun Jihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p1Fri, 16 Oct 2015 00:00:00 +1100Genus of the Cartesian Product of Triangles.
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p2
We investigate the orientable genus of $G_n$, the cartesian product of $n$ triangles, with a particular attention paid to the two smallest unsolved cases $n=4$ and $5$. Using a lifting method we present a general construction of a low-genus embedding of $G_n$ using a low-genus embedding of $G_{n-1}$. Combining this method with a computer search and a careful analysis of face structure we show that $30\le \gamma(G_4) \le 37$ and $133 \le\gamma(G_5) \le 190$. Moreover, our computer search resulted in more than $1300$ non-isomorphic minimum-genus embeddings of $G_3$. We also introduce genus range of a group and (strong) symmetric genus range of a Cayley graph and of a group. The (strong) symmetric genus range of irredundant Cayley graphs of $Z_p^n$ is calculated for all odd primes $p$.Michal Kotrbčík, Tomaž Pisanskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p2Fri, 16 Oct 2015 00:00:00 +1100An Exact Turán Result for Tripartite 3-Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p3
<p>Mantel's theorem says that among all triangle-free graphs of a given order the balanced complete bipartite graph is the unique graph of maximum size. We prove an analogue of this result for 3-graphs. Let $K_4^-=\{123,124,134\}$, $F_6=\{123,124,345,156\}$ and $\mathcal{F}=\{K_4^-,F_6\}$: for $n\neq 5$ the unique $\mathcal{F}$-free 3-graph of order $n$ and maximum size is the balanced complete tripartite 3-graph $S_3(n)$ (for $n=5$ it is $C_5^{(3)}=\{123,234,345,145,125\}$). This extends an old result of Bollobás that $S_3(n) $ is the unique 3-graph of maximum size with no copy of $K_4^-=\{123,124,134\}$ or $F_5=\{123,124,345\}$.</p>Adam Sanitt, John Talbothttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p3Fri, 16 Oct 2015 00:00:00 +1100The Page-Rényi Parking Process
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p4
In the Page parking (or packing) model on a discrete interval (also known as the <em>discrete Rényi packing</em> problem or the <em>unfriendly seating problem</em>), cars of length two successively park uniformly at random on pairs of adjacent places, until only isolated places remain.<br /><br />We use a probabilistic construction of the Page parking to give a short proof of the (known) fact that the proportion of the interval occupied by cars goes to $1-e^{-2}$, when the length of the interval goes to infinity. We also obtain some new consequences on both finite and infinite parkings.Lucas Gerinhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p4Fri, 16 Oct 2015 00:00:00 +1100Bounding Tree-Width via Contraction on the Projective Plane and Torus.
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p5
If $X$ is a collection of edges in a graph $G$, let $G/X$ denote the contraction of $X$. Following a question of Oxley and a conjecture of Oporowski, we prove that every projective planar graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three. We prove that every toroidal graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three and four, respectively.Evan Morgan, Bogdan Oporowskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p5Fri, 16 Oct 2015 00:00:00 +1100Identifying Codes in Vertex-Transitive Graphs and Strongly Regular Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p6
We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and $2\ln(|V|)+1$ where $V$ is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order $|V|^{\alpha}$ with $\alpha \in \{\frac{1}{4},\frac{1}{3},\frac{2}{5}\}$. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.Sylvain Gravier, Aline Parreau, Sara Rottey, Leo Storme, Élise Vandommehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p6Fri, 16 Oct 2015 00:00:00 +1100A Generalization of Graham’s Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p7
<p>Let $G$ be a finite Abelian group of order $|G|=n$, and let $S=g_1\cdot\ldots\cdot g_{n-1}$ be a sequence over $G$ such that all nonempty zero-sum subsequences of $S$ have the same length. In this paper, we completely determine the structure of these sequences.</p><p> </p>Huanhuan Guan, Pingzhi Yuan, Xiangneng Zenghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p7Fri, 16 Oct 2015 00:00:00 +1100HOMFLY Polynomials of Torus Links as Generalized Fibonacci Polynomials
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p8
<p>The focus of this paper is to study the HOMFLY polynomial of $(2,n)$-torus link as a generalized Fibonacci polynomial. For this purpose, we first introduce a form of generalized Fibonacci and Lucas polynomials and provide their some fundamental properties. We define the HOMFLY polynomial of $ (2,n) $-torus link with a way similar to our generalized Fibonacci polynomials and provide its fundamental properties. We also show that the HOMFLY polynomial of $ (2,n) $-torus link can be obtained from its Alexander-Conway polynomial or the classical Fibonacci polynomial. We finally give the matrix representations and prove important identities, which are similar to the Fibonacci identities, for the our generalized Fibonacci polynomial and the HOMFLY polynomial of $ (2,n) $-torus link.</p>Kemal Taşköprü, İsmet Altıntaşhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p8Fri, 16 Oct 2015 00:00:00 +1100Random-Player Maker-Breaker games
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p9
<p>In a $(1:b)$ Maker-Breaker game, one of the central questions is to find the maximal value of $b$ that allows Maker to win the game (that is, the critical bias $b^*$). Erd<span>ő</span>s conjectured that the critical bias for many Maker-Breaker games played on the edge set of $K_n$ is the same as if both players claim edges randomly. Indeed, in many Maker-Breaker games, "Erd<span>ő</span>s Paradigm" turned out to be true. Therefore, the next natural question to ask is the (typical) value of the critical bias for Maker-Breaker games where only one player claims edges randomly. A random-player Maker-Breaker game is a two-player game, played the same as an ordinary (biased) Maker-Breaker game, except that one player plays according to his best strategy and claims one element in each round, while the other plays randomly and claims $b$ (or $m$) elements. In fact, for every (ordinary) Maker-Breaker game, there are two different random-player versions; the $(1:b)$ random-Breaker game and the $(m:1)$ random-Maker game. We analyze the random-player version of several classical Maker-Breaker games such as the Hamilton cycle game, the perfect-matching game and the $k$-vertex-connectivity game (played on the edge set of $K_n$). For each of these games we find or estimate the asymptotic values of the bias (either $b$ or $m$) that allow each player to typically win the game. In fact, we provide the "smart" player with an explicit winning strategy for the corresponding value of the bias.</p>Michael Krivelevich, Gal Kronenberghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p9Fri, 16 Oct 2015 00:00:00 +1100Walks, Partitions, and Normal Ordering
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p10
<p>We describe the relation between graph decompositions into walks and the normal ordering of differential operators in the $n$-th Weyl algebra. Under several specifications, we study new types of restricted set partitions, and a generalization of Stirling numbers, which we call the $\lambda$-Stirling numbers.</p>Askar Dzhumadil'daev, Damir Yeliussizovhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p10Fri, 16 Oct 2015 00:00:00 +1100Fractional Coloring of Triangle-Free Planar Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p11
<p>We prove that every planar triangle-free graph on $n$ vertices has fractional chromatic number at most $3-3/(3n+1)$.</p>Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volechttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p11Fri, 16 Oct 2015 00:00:00 +1100On the Real-Rootedness of the Descent Polynomials of $(n-2)$-Stack Sortable Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p12
<p>Bóna conjectured that the descent polynomials on $(n-2)$-stack sortable permutations have only real zeros. Brändén proved this conjecture by establishing a more general result. In this paper, we give another proof of Brändén's result by using the theory of $s$-Eulerian polynomials recently developed by Savage and Visontai.</p>Philip B. Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p12Fri, 16 Oct 2015 00:00:00 +1100Wilf-Classification of Mesh Patterns of Short Length
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p13
<p>This paper starts the Wilf-classification of mesh patterns of length 2. Although there are initially 1024 patterns to consider we introduce automatic methods to reduce the number of potentially different Wilf-classes to at most 65. By enumerating some of the remaining classes we bring that upper-bound further down to 56. Finally, we conjecture that the actual number of Wilf-classes of mesh patterns of length 2 is 46.</p>Ísak Hilmarsson, Ingibjörg Jónsdóttir, Steinunn Sigurðardóttir, Lína Viðarsdóttir, Henning Ulfarssonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p13Fri, 16 Oct 2015 00:00:00 +1100Thin Edges in Braces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p14
The <em>bicontraction</em> of a vertex $v$ of degree two in a graph, with precisely two neighbours $v_1$ and $v_2$, consists of shrinking the set $\{v_1,v,v_2\}$ to a single vertex. The <em>retract</em> of a matching covered graph $G$, denoted by $\widehat{G}$, is the graph obtained from $G$ by repeatedly bicontracting vertices of degree two. Up to isomorphism, the retract of a matching covered graph $G$ is unique. If $G$ is a brace on six or more vertices, an edge $e$ of $G$ is <em>thin</em> if $\widehat{G-e}$ is a brace. A thin edge $e$ in a simple brace $G$ is <em>strictly thin</em> if $\widehat{G-e}$ is a simple brace. Theorems concerning the existence of strictly thin edges have been used (implicitly by McCuaig (Pólya's Permanent Problem, <em>Electron. J. of Combin.</em>, 11, 2004) and explicitly by the authors (On the Number of Perfect Matchings in a Bipartite Graph, <em>SIAM J. Discrete Math.</em>, <strong>27</strong>, 940-958, 2013)) as inductive tools for establishing properties of braces.<br /><br />Let $G$ and $J$ be two distinct braces, where $G$ is of order six or more and $J$ is a simple matching minor of $G$. It follows from a theorem of McCuaig (Brace Generation, <em>J. Graph Theory</em>, <strong>38</strong>, 124-169, 2001) that $G$ has a thin edge $e$ such that $J$ is a matching minor of $G-e$. In Section 2, we give an alternative, and simpler proof, of this assertion. Our method of proof lends itself to proving stronger results concerning thin edges.<br /><br />Let ${\cal G}^+$ denote the family of braces consisting of all prisms, all Möbius ladders, all biwheels, and all extended biwheels. Strengthening another result of McCuaig on brace generation, we show that every simple brace of order six or more which is not a member of ${\cal G}^+$ has at least two strictly thin edges. We also give examples to show that this result is best possible.<br /><br /><br />Cláudio L. Lucchesi, Marcelo H. de Carvalho, U. S. R. Murtyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p14Fri, 30 Oct 2015 00:00:00 +1100The Maximal Length of a Gap between $r$-Graph Turán Densities
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p15
<p>The Tur<span>á</span>n density $\pi(\cal F)$ of a family $\cal F$ of $r$-graphs is the limit as $n\to\infty$ of the maximum edge density of an $\cal F$-free $r$-graph on $n$ vertices. Erd<span>ő</span>s [Israel J. Math, 2 (1964):183—190] proved that no Tur<span>á</span>n density can lie in the open interval $(0,r!/r^r)$. Here we show that any other open subinterval of $[0,1]$ avoiding Tur<span>á</span>n densities has strictly smaller length. In particular, this implies a conjecture of Grosu [<a href="http://arxiv.org/abs/1403.4653">arXiv:1403.4653</a>, 2014].</p>Oleg Pikhurkohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p15Fri, 30 Oct 2015 00:00:00 +1100Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p16
<p>In a first part, we are concerned with the relationships between polynomials in the two generators of the algebra of Heisenberg—Weyl, its Bargmann—Fock representation with differential operators and the associated one-parameter group.</p><p>Upon this basis, the paper is then devoted to the groups of Riordan matrices associated to the related transformations of matrices (i.e., substitutions with prefunctions). Thereby, various properties are studied arising in Riordan arrays, in the Riordan group and, more specifically, in the "striped" Riordan subgroups; further, a striped quasigroup and a semigroup are also examined. A few applications to combinatorial structures are also briefly addressed in the Appendix.</p>Silvia Goodenough, Christian Lavaulthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p16Fri, 30 Oct 2015 00:00:00 +1100Rank and Crank Analogs for some Colored Partitions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p17
<p>We establish some rank and crank analogs for partitions into distinct colors and give combinatorial interpretations for colored partitions such as partitions defined by Toh, Zhang and Wang congruences modulo 5, 7.</p>Roberta R. Zhou, Wenlong Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p17Fri, 30 Oct 2015 00:00:00 +1100$h$-Polynomials via Reduced Forms
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p18
The flow polytope $F_{\widetilde{G}}$ is the set of nonnegative unit flows on the graph $\widetilde{G}$. The subdivision algebra of flow polytopes prescribes a way to dissect a flow polytope $F_{\widetilde{G}}$ into simplices. Such a dissection is encoded by the terms of the so called reduced form of the monomial $\prod_{(i,j)\in E(G)}x_{ij}$. We prove that we can use the subdivision algebra of flow polytopes to construct not only dissections, but also regular flag triangulations of flow polytopes. We prove that reduced forms in the subdivision algebra are generalizations of $h$-polynomials of the triangulations of flow polytopes. We deduce several corollaries of the above results, most notably proving certain cases of a conjecture of Kirillov about the nonnegativity of reduced forms in the noncommutative quasi-classical Yang-Baxter algebra.Karola Meszaroshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p18Fri, 30 Oct 2015 00:00:00 +1100Local Finiteness, Distinguishing Numbers, and Tucker's Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p19
<pre><!--StartFragment-->A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial automorphism preserves the colouring. Tucker conjectured that if every non-trivial automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing <span>2</span>-colouring.</pre><pre> </pre><pre>We show that the requirement of local finiteness is necessary by giving a non-locally finite graph for which no finite number of colours suffices.<!--EndFragment--></pre>Florian Lehner, Rögnvaldur G. Möllerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p19Fri, 30 Oct 2015 00:00:00 +1100Reconstructing Permutations from Identification Minors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p20
We consider the problem whether a permutation of a finite set is uniquely determined by its identification minors. While there exist non-reconstructible permutations of every set with two, three, or four elements, we show that every permutation of a finite set with at least five elements is reconstructible from its identification minors. Moreover, we provide an algorithm for recovering a permutation from its deck. We also discuss a generalization of this reconstruction problem, as well as the related set-reconstruction problem.Erkko Lehtonenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p20Fri, 30 Oct 2015 00:00:00 +1100Normally Regular Digraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p21
<p>A normally regular digraph with parameters $(v,k,\lambda,\mu)$ is a directed graph on $v$ vertices whose adjacency matrix $A$ satisfies the equation $AA^t=k I+\lambda (A+A^t)+\mu(J-I-A-A^t)$. This means that every vertex has out-degree $k$, a pair of non-adjacent vertices have $\mu$ common out-neighbours, a pair of vertices connected by an edge in one direction have $\lambda$ common out-neighbours and a pair of vertices connected by edges in both directions have $2\lambda-\mu$ common out-neighbours. We often assume that two vertices can not be connected in both directions. <br /><br />We prove that the adjacency matrix of a normally regular digraph is normal. A connected $k$-regular digraph with normal adjacency matrix is a normally regular digraph if and only if all eigenvalues other than $k$ are on one circle in the complex plane. We prove several non-existence results, structural characterizations, and constructions of normally regular digraphs. In many cases these graphs are Cayley graphs of abelian groups and the construction is then based on a generalization of difference sets.</p><p>We also show connections to other combinatorial objects: strongly regular graphs, symmetric 2-designs and association schemes.<br /><br /></p>Leif K Jørgensenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p21Fri, 30 Oct 2015 00:00:00 +1100Enumeration of Lozenge Tilings of Halved Hexagons with a Boundary Defect
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p22
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span>We generalize a special case of a theorem of Proctor on the enumeration of lozenge tilings of a hexagon with a maximal staircase removed using Kuo’s graphical condensation method. Additionally, we prove a formula for a weighted version of the given region. The result also extends work of Ciucu and Fischer. By applying the factorization theorem of Ciucu, we are also able to generalize a special case of MacMahon’s boxed plane partition formula. </span></p></div></div></div>Ranjan Rohatgihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p22Fri, 30 Oct 2015 00:00:00 +1100Words with many Palindrome Pair Factors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p23
Motivated by a conjecture of Frid, Puzynina, and Zamboni, we investigate infinite words with the property that for infinitely many $n$, every length-$n$ factor is a product of two palindromes. We show that every Sturmian word has this property, but this does not characterize the class of Sturmian words. We also show that the Thue—Morse word does not have this property. We investigate finite words with the maximal number of distinct palindrome pair factors and characterize the binary words that are not palindrome pairs but have the property that every proper factor is a palindrome pair.Adam Borchert, Narad Rampersadhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p23Fri, 30 Oct 2015 00:00:00 +1100Clustered Planarity Testing Revisited
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p24
The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani–Tutte theorem in the case when each cluster induces a connected subgraph.<br /><br />Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.Radoslav Fulek, Jan Kynčl, Igor Malinović, Dömötör Pálvölgyihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p24Fri, 13 Nov 2015 00:00:00 +1100Cataloguing PL 4-Manifolds by Gem-Complexity
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p25
<p>We describe an algorithm to subdivide automatically a given set of PL $n$-manifolds (via <em>coloured triangulations</em> or, equivalently, via <em>crystallizations</em>) into classes whose elements are PL-homeomorphic. The algorithm, implemented in the case <em>n=4</em>, succeeds to solve completely the PL-homeomorphism problem among the catalogue of all closed connected PL 4-manifolds up to gem-complexity 8 (i.e., which admit a coloured triangulation with at most 18 4-simplices).<br /><br />Possible interactions with the (not completely known) relationship among different classification in TOP and DIFF=PL categories are also investigated. As a first consequence of the above PL classification, the non-existence of exotic PL 4-manifolds up to gem-complexity 8 is proved. Further applications of the tool are described, related to possible PL-recognition of different triangulations of the <em>K3</em>-surface.</p>Maria Rita Casali, Paola Cristoforihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p25Fri, 13 Nov 2015 00:00:00 +1100A Linear Bound towards the Traceability Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p26
A digraph is <em>k</em>-traceable if its order is at least <em>k</em> and each of its subdigraphs of order <em>k</em> is traceable. An oriented graph is a digraph without 2-cycles. The 2-traceable oriented graphs are exactly the nontrivial tournaments, so <em>k</em>-traceable oriented graphs may be regarded as generalized tournaments. It is well-known that all tournaments are traceable. We denote by <em>t</em>(<em>k</em>) the smallest integer bigger than or equal to <em>k</em> such that every <em>k</em>-traceable oriented graph of order at least <em>t</em>(<em>k</em>) is traceable. The Traceability Conjecture states that <em>t</em>(<em>k</em>) ≤ <em>2k-1</em> for every <em>k </em>≥ <em>2</em> [van Aardt, Dunbar, Frick, Nielsen and Oellermann, A traceability conjecture for oriented graphs, Electron. J. Combin., 15(1):#R150, 2008]. We show that for <em>k </em>≥ 2, every <em>k</em>-traceable oriented graph with independence number 2 and order at least 4<em>k-</em>12 is traceable. This is the last open case in giving an upper bound for <em>t</em>(<em>k</em>) that is linear in <em>k</em>.Susan A. van Aardt, Jean E. Dunbar, Marietjie Frick, Nicolas Lichiardopolhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p26Fri, 13 Nov 2015 00:00:00 +1100On Generalizations of the Petersen Graph and the Coxeter Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p27
<p>In this note we consider two related infinite families of graphs, which generalize the Petersen and the Coxeter graph. The main result proves that these graphs are cores. It is determined which of these graphs are vertex/edge/arc-transitive or distance-regular. Girths and odd girths are computed. A problem on hamiltonicity is posed.</p>Marko Orelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p27Fri, 13 Nov 2015 00:00:00 +1100Inversion Formulae on Permutations Avoiding 321
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p28
<p>We will study the inversion statistic of $321$-avoiding permutations, and obtain that the number of $321$-avoiding permutations on $[n]$ with $m$ inversions is given by<br />\[<br />|\mathcal {S}_{n,m}(321)|=\sum_{b \vdash m}{n-\frac{\Delta(b)}{2}\choose l(b)}.<br />\]<br />where the sum runs over all compositions $b=(b_1,b_2,\ldots,b_k)$ of $m$, i.e.,<br />\[<br />m=b_1+b_2+\cdots+b_k \quad{\rm and}\quad b_i\ge 1,<br />\]<br />$l(b)=k$ is the length of $b$, and $\Delta(b):=|b_1|+|b_2-b_1|+\cdots+|b_k-b_{k-1}|+|b_k|$. We obtain a new bijection from $321$-avoiding permutations to Dyck paths which establishes a relation on inversion number of $321$-avoiding permutations and valley height of Dyck paths.</p>Pingge Chen, Zhousheng Mei, Suijie Wanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p28Fri, 13 Nov 2015 00:00:00 +1100Exact Forbidden Subposet Results using Chain Decompositions of the Cycle
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p29
We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of $[n]$ not containing one or more given posets as a subposet. De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.Abhishek Methuku, Casey Tompkinshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p29Fri, 27 Nov 2015 00:00:00 +1100Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p30
In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.Petr Kolman, Martin Kouteckýhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p30Fri, 27 Nov 2015 00:00:00 +1100Digraph Representations of 2-closed Permutation Groups with a Normal Regular Cyclic Subgroup
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p31
<p>In this paper, we classify 2-closed (in Wielandt's sense) permutation groups which contain a normal regular cyclic subgroup and prove that for each such group $G$, there exists a circulant $\Gamma$ such that $\mathrm{Aut} (\Gamma)=G$.</p>Jing Xuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p31Fri, 27 Nov 2015 00:00:00 +1100Developments in the Khintchine-Meinardus Probabilistic Method for Asymptotic Enumeration
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p32
<p>A theorem of Meinardus provides asymptotics of the number of weighted partitions under certain assumptions on associated ordinary and Dirichlet generating functions. The ordinary generating functions are closely related to Euler's generating function $\prod_{k=1}^\infty S(z^k)$ for partitions, where $S(z)=(1-z)^{-1}$. By applying a method due to Khintchine, we extend Meinardus' theorem to find the asymptotics of the Taylor coefficients of generating functions of the form $\prod_{k=1}^\infty S(a_kz^k)^{b_k}$ for sequences $a_k$, $b_k$ and general $S(z)$. We also reformulate the hypotheses of the theorem in terms of the above generating functions. This allows novel applications of the method. In particular, we prove rigorously the asymptotics of Gentile statistics and derive the asymptotics of combinatorial objects with distinct components.<br /><br /></p>Boris L. Granovsky, Dudley Starkhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p32Fri, 27 Nov 2015 00:00:00 +1100On the Existence of Certain Optimal Self-Dual Codes with Lengths Between 74 and 116
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p33
The existence of optimal binary self-dual codes is a long-standing research problem. In this paper, we present some results concerning the decomposition of binary self-dual codes with a dihedral automorphism group $D_{2p}$, where $p$ is a prime. These results are applied to construct new self-dual codes with length $78$ or $116$. We obtain $16$ inequivalent self-dual $[78,39,14]$ codes, four of which have new weight enumerators. We also show that there are at least $141$ inequivalent self-dual $[116,58,18]$ codes, most of which are new up to equivalence. Meanwhile, we give some restrictions on the weight enumerators of singly even self-dual codes. We use these restrictions to exclude some possible weight enumerators of self-dual codes with lengths $74$, $76$, $82$, $98$ and $100$.Tao Zhang, Jerod Michel, Tao Feng, Gennian Gehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p33Fri, 27 Nov 2015 00:00:00 +1100Semi-Degree Threshold for Anti-Directed Hamiltonian Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p34
In 1960 Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if $D$ is a directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$, then $D$ contains a directed Hamiltonian cycle. For directed graphs one may ask for other orientations of a Hamiltonian cycle and in 1980 Grant initiated the problem of determining minimum degree conditions for a directed graph $D$ to contain an anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even $n$, if $D$ is a directed graph on $n$ vertices with minimum out-degree and in-degree at least $\frac{n}{2}+1$, then $D$ contains an anti-directed Hamiltonian cycle. In fact, we prove the stronger result that $\frac{n}{2}$ is sufficient unless $D$ is one of two counterexamples. This result is sharp.Louis DeBiasio, Theodore Mollahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p34Fri, 27 Nov 2015 00:00:00 +1100Applications of Integer Programming Methods to Cages
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p35
<p>The aim of this paper is to construct new small regular graphs with girth $7$ using integer programming techniques. Over the last two decades solvers for integer programs have become more and more powerful and have proven to be a useful aid for many hard combinatorial problems. Despite successes in many related fields, these optimisation tools have so far been absent in the quest for small regular graphs with a given girth. Here we illustrate the power of these solvers as an aid to construct small regular girth $7$ graphs from girth $8$ cages.</p>Frans J.C.T. de Ruiter, Norman L. Biggshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p35Fri, 27 Nov 2015 00:00:00 +1100Lifespan in a Primitive Boolean Linear Dynamical System
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p36
<p>Let $\mathcal F$ be a set of $k$ by $k$ nonnegative matrices such that every "long" product of elements of $\mathcal F$ is positive. Cohen and Sellers (1982) proved that, then, every such product of length $2^k-2$ over $\mathcal F$ must be positive. They suggested to investigate the minimum size of such $\mathcal F$ for which there exists a non-positive product of length $2^k-3$ over $\mathcal F$ and they constructed one example of size $2^k-2$. We construct one of size $k$ and further discuss relevant basic problems in the framework of Boolean linear dynamical systems. We also formulate several primitivity properties for general discrete dynamical systems.<br /><br /><br /></p>Yaokun Wu, Yinfeng Zhuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p36Fri, 27 Nov 2015 00:00:00 +1100