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 +1000Neighborhood Complexes of Some Exponential Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p26
<p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">In this article, we consider the bipartite graphs $K_2 \times K_n$. We first show that the connectedness of the neighborhood complex $\mathcal{N}(K_{n+1}^{K_n}) =0$. Further, we show that Hom$(K_2 \times K_{n}, K_{m})$ is homotopic to $S^{m-2}$, if $2\leq m <n$.</p>Nandini Nilakantan, Samir Shuklahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p26Fri, 13 May 2016 00:00:00 +1000A Family of Symmetric Graphs with Complete Quotients
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p27
A finite graph $\Gamma$ is $G$-symmetric if it admits $G$ as a group of automorphisms acting transitively on $V(\Gamma)$ and transitively on the set of ordered pairs of adjacent vertices of $\Gamma$. If $V(\Gamma)$ admits a nontrivial $G$-invariant partition ${\cal B}$ such that for blocks $B, C \in {\cal B}$ adjacent in the quotient graph $\Gamma_{{\cal B}}$ relative to ${\cal B}$, exactly one vertex of $B$ has no neighbour in $C$, then we say that $\Gamma$ is an almost multicover of $\Gamma_{{\cal B}}$. In this case there arises a natural incidence structure ${\cal D}(\Gamma, {\cal B})$ with point set ${\cal B}$. If in addition $\Gamma_{{\cal B}}$ is a complete graph, then ${\cal D}(\Gamma, {\cal B})$ is a $(G, 2)$-point-transitive and $G$-block-transitive $2$-$(|{\cal B}|, m+1, \lambda)$ design for some $m \geq 1$, and moreover either $\lambda=1$ or $\lambda=m+1$. In this paper we classify such graphs in the case when $\lambda = m+1$; this together with earlier classifications when $\lambda = 1$ gives a complete classification of almost multicovers of complete graphs.Teng Fang, Xin Gui Fang, Binzhou Xia, Sanming Zhouhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p27Fri, 13 May 2016 00:00:00 +1000Combinatorics Meets Potential Theory
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p28
<p><span style="color: #000000;">Using potential theoretic techniques, we show how it is possible to determine the dominant asymptotics for the number of walks of </span><span style="color: #000000;">length </span><span style="color: #008000;">$n$</span><span style="color: #000000;">, restricted to the </span><span style="color: #000000;">positive quadrant and </span>taking unit steps in a balanced set <span style="color: #008000;">$\Gamma$</span><span style="color: #000000;">. </span></p><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">T</span><span style="color: #000000;">he </span><span style="color: #000000;">approach </span><span style="color: #000000;">is </span><span style="color: #000000;">illustrated </span><span style="color: #000000;">through</span><span style="color: #000000;"> an example </span><span style="color: #000000;">of </span><span style="color: #000000;">inhomogeneous</span><span style="color: #000000;"> space</span><span style="color: #000000;"> walk</span><span style="color: #000000;">. </span><span style="color: #000000;">This </span><span style="color: #000000;">walk </span><span style="color: #000000;">takes </span><span style="color: #000000;">its </span><span style="color: #000000;">st</span><span style="color: #000000;">eps</span><span style="color: #000000;"> in </span><span style="color: #008000;">$\{ \leftarrow, \uparrow, \rightarrow, \downarrow \}$</span><span style="color: #000000;"> or </span><span style="color: #008000;">$\{ \swarrow, \leftarrow, \nwarrow, \uparrow,</span><span style="color: #008000;">\nearrow, \rightarrow, \searrow, \downarrow \}$</span><span>, </span><span>depending</span><span> on </span><span>the </span><span>parity </span><span>of</span><span> the </span><span>coordinates </span><span>of</span><span> its</span><span> positions.</span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;"> </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">The</span><span style="color: #000000;"> exponential</span><span style="color: #000000;"> growth </span><span style="color: #000000;">of </span><span style="color: #000000;">our</span><span style="color: #000000;"> model</span><span style="color: #000000;"> is </span><span style="color: #008000;">$(4\phi)^n$</span><span style="color: #000000;">, </span><span style="color: #000000;">where</span><span style="color: #008000;"> $\phi= \frac{1+\sqrt 5}{2}$</span><span style="color: #000000;">denotes</span><span style="color: #000000;"> the</span><span style="color: #000000;"> Golden ratio, while </span><span style="color: #000000;">the subexponential</span><span style="color: #000000;"> growth</span><span style="color: #000000;"> is</span><span style="color: #000000;"> like</span><span style="color: #008000;"> $1/n$</span><span style="color: #000000;">.<br /><br /></span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">As an application </span><span style="color: #000000;">of</span><span style="color: #000000;"> our</span><span style="color: #000000;"> approach</span><span style="color: #000000;"> we </span><span style="color: #000000;">prove </span><span style="color: #000000;">the</span><span style="color: #000000;"> non-D-</span><span style="color: #000000;">finiteness </span><span>in </span><span>two</span><span> dimensions of</span><span> the</span><span> length </span><span>generating </span><span>functions corresponding</span><span> to </span><span>nonsingular small step sets </span><span>with</span><span> an </span><span>infinite </span><span>group</span><span> and zero-</span><span>drift</span><span>. </span></pre>Philippe D'Arco, Valentina Lacivita, Sami Mustaphahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p28Fri, 13 May 2016 00:00:00 +1000Extremal Graph for Intersecting Odd Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p29
An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let $T_{n,r}$ be the Tur<span>á</span>n graph, which is the complete $r$-partite graph on $n$ vertices with part sizes that differ by at most one. The well-known Tur<span>á</span>n Theorem states that $T_{n,r}$ is the only extremal graph for complete graph $K_{r+1}$. Erd<span>ő</span>s et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.Xinmin Hou, Yu Qiu, Boyuan Liuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p29Fri, 13 May 2016 00:00:00 +1000Turán Numbers for 3-Uniform Linear Paths of Length 3
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p30
<p>In this paper we confirm a special, remaining case of a conjecture of F<span>ü</span>redi, Jiang, and Seiver, and determine an exact formula for the Tur<span>á</span>n number $\mathrm{ex}_3(n; P_3^3)$ of the 3-uniform linear path $P^3_3$ of length 3, valid for all $n$. It coincides with the analogous formula for the 3-uniform triangle $C^3_3$, obtained earlier by Frankl and F<span>ü</span>redi for $n\ge 75$ and Cs<span>á</span>k<span>á</span>ny and Kahn for all $n$. In view of this coincidence, we also determine a `conditional' Tur<span>á</span>n number, defined as the maximum number of edges in a $P^3_3$-free 3-uniform hypergraph on $n$ vertices which is <em>not</em> $C^3_3$-free.</p>Eliza Jackowska, Joanna Polcyn, Andrzej Rucińskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p30Fri, 13 May 2016 00:00:00 +1000On Decomposing Graphs of Large Minimum Degree into Locally Irregular Subgraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p31
A <em>locally irregular graph</em> is a graph whose adjacent vertices have distinct degrees. We say that a graph <em>G</em> <em>can be decomposed into</em> <em>k</em> <em>locally irregular subgraphs</em> if its edge set may be partitioned into <em>k </em>subsets each of which induces a locally irregular subgraph in <em>G</em>. It has been conjectured that apart from the family of exceptions which admit no such decompositions, i.e., odd paths, odd cycles and a special class of graphs of maximum degree <em>3</em>, every connected graph can be decomposed into <em>3</em> locally irregular subgraphs. Using a combination of a probabilistic approach and some known theorems on degree constrained subgraphs of a given graph, we prove this to hold for graphs of minimum degree at least $10^{10}$. This problem is strongly related to edge colourings distinguishing neighbours by the pallets of their incident colours and to the 1-2-3 Conjecture. In particular, the contribution of this paper constitutes a strengthening of a result of Addario-Berry, Aldred, Dalal and Reed [J. Combin. Theory Ser. B 94 (2005) 237-244].Jakub Przybyłohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p31Fri, 13 May 2016 00:00:00 +1000On Ultralimits of Sparse Graph Classes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p32
The notion of nowhere denseness is one of the central concepts of the recently developed theory of sparse graphs. We study the properties of nowhere dense graph classes by investigating appropriate limit objects defined using the ultraproduct construction. It appears that different equivalent definitions of nowhere denseness, for example via quasi-wideness or the splitter game, correspond to natural notions for the limit objects that are conceptually simpler and allow for less technically involved reasonings.Michał Pilipczuk, Szymon Toruńczykhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p32Thu, 05 May 2016 18:27:15 +1000A Simple Existence Criterion for Normal Spanning Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p33
<p>Halin proved in 1978 that there exists a normal spanning tree in every connected graph $G$ that satisfies the following two conditions: (i) $G$ contains no subdivision of a `fat' $K_{\aleph_0}$, one in which every edge has been replaced by uncountably many parallel edges; and (ii) $G$ has no $K_{\aleph_0}$ subgraph. We show that the second condition is unnecessary.</p>Reinhard Diestelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p33Fri, 13 May 2016 00:00:00 +1000Chung-Feller Property of Schröder Objects
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p34
<p>Large Schr<span>ö</span>der paths, sparse noncrossing partitions, partial horizontal strips, and $132$-avoiding alternating sign matrices are objects enumerated by Schr<span>ö</span>der numbers. In this paper we give formula for the number of Schr<span>ö</span>der objects with given type and number of connected components. The proofs are bijective using Chung-Feller style. A bijective proof for the number of Schr<span>ö</span>der objects with given type is provided. We also give a combinatorial interpretation for the number of small Schr<span>ö</span>der paths.</p>Youngja Park, Sangwook Kimhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p34Fri, 13 May 2016 00:00:00 +1000A New Near Octagon and the Suzuki Tower
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p35
<pre><!--StartFragment-->We construct and study a new near octagon of order <span>$(2,10)$</span> which has its full automorphism group isomorphic to the group <span>$G_2(4):2$ </span>and which contains <span>$416$</span> copies of the Hall-<span>Janko</span> near octagon as full <span>subgeometries</span>. Using this near octagon and its substructures we give geometric constructions of the <span>$G_2(4)$</span>-graph and the Suzuki graph, both of which are strongly regular graphs contained in the Suzuki tower. As a <span>subgeometry</span> of this octagon we have discovered another new near octagon, whose order is <span>$(2,4)$</span>.</pre><pre><br /><!--EndFragment--></pre><pre><br /><!--EndFragment--></pre>Anurag Bishnoi, Bart De Bruynhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p35Fri, 13 May 2016 00:00:00 +1000Some Probabilistic Trees with Algebraic Roots
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p36
<p>We consider several probabilistic processes defining a random graph. One of these processes appeared recently in connection with a factorization problem in the symmetric group. For each process, we prove that the probability for the random graph to be a tree has an unexpectedly simple expression, which is independent of most parameters of the problem. This raises many open questions.</p>Olivier Bernardi, Alejandro H. Moraleshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p36Fri, 13 May 2016 00:00:00 +10000-Sum and 1-Sum Flows in Regular Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p37
Let $G$ be a graph. Assume that $l$ and $k$ are two natural numbers. An $l$-sum flow on a graph $G$ is an assignment of non-zero real numbers to the edges of $G$ such that for every vertex $v$ of $G$ the sum of values of all edges incidence with $v$ equals $l$. An $l$-sum $k$-flow is an $l$-sum flow with values from the set $\{\pm 1,\ldots ,\pm(k-1)\}$. Recently, it was proved that for every $r, r\geq 3$, $r\neq 5$, every $r$-regular graph admits a $0$-sum $5$-flow. In this paper we settle a conjecture by showing that every $5$-regular graph admits a $0$-sum $5$-flow. Moreover, we prove that every $r$-regular graph of even order admits a $1$-sum $5$-flow.S. Akbari, M. Kano, S. Zarehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p37Fri, 27 May 2016 00:00:00 +1000A Combinatorial Approach to the $q,t$-Symmetry Relation in Macdonald Polynomials
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p38
<p>Using the combinatorial formula for the transformed Macdonald polynomials of Haglund, Haiman, and Loehr, we investigate the combinatorics of the symmetry relation $\widetilde{H}_\mu(\mathbf{x};q,t)=\widetilde{H}_{\mu^\ast}(\mathbf{x};t,q)$. We provide a purely combinatorial proof of the relation in the case of Hall-Littlewood polynomials ($q=0$) when $\mu$ is a partition with at most three rows, and for the coefficients of the square-free monomials in $\mathbf{x}$ for all shapes $\mu$. We also provide a proof for the full relation in the case when $\mu$ is a hook shape, and for all shapes at the specialization $t=1$. Our work in the Hall-Littlewood case reveals a new recursive structure for the cocharge statistic on words.</p>Maria Monks Gillespiehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p38Fri, 27 May 2016 00:00:00 +1000On Well-Covered, Vertex Decomposable and Cohen-Macaulay Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p39
<p>Let $G=(V,E)$ be a graph. If $G$ is a König graph or if $G$ is a graph without 3-cycles and 5-cycles, we prove that the following conditions are equivalent: $\Delta_{G}$ is pure shellable, $R/I_{\Delta}$ is Cohen-Macaulay, $G$ is unmixed vertex decomposable graph and $G$ is well-covered with a perfect matching of König type $e_{1},\dots,e_{g}$ without 4-cycles with two $e_i$'s. Furthermore, we study vertex decomposable and shellable (non-pure) properties in graphs without 3-cycles and 5-cycles. Finally, we give some properties and relations between critical, extendable and shedding vertices.</p>Iván D. Castrillón, Roberto Cruz, Enrique Reyeshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p39Fri, 27 May 2016 00:00:00 +1000Unimodality via Alternating Gamma Vectors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p40
For a polynomial with palindromic coefficients, unimodality is equivalent to having a nonnegative $g$-vector. A sufficient condition for unimodality is having a nonnegative $\gamma$-vector, though one can have negative entries in the $\gamma$-vector and still have a nonnegative $g$-vector.<br /><br />In this paper we provide combinatorial models for three families of $\gamma$-vectors that alternate in sign. In each case, the $\gamma$-vectors come from unimodal polynomials with straightforward combinatorial descriptions, but for which there is no straightforward combinatorial proof of unimodality. <br /><br />By using the transformation from $\gamma$-vector to $g$-vector, we express the entries of the $g$-vector combinatorially, but as an alternating sum. In the case of the $q$-analogue of $n!$, we use a sign-reversing involution to interpret the alternating sum, resulting in a manifestly positive formula for the $g$-vector. In other words, we give a combinatorial proof of unimodality. We consider this a "proof of concept" result that we hope can inspire a similar result for the other two cases, $\prod_{j=1}^n (1+q^j)$ and the $q$-binomial coefficient ${n\brack k}$.Charles Brittenham, Andrew T. Carroll, T. Kyle Petersen, Connor Thomashttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p40Fri, 27 May 2016 00:00:00 +1000A Ternary Square-free Sequence Avoiding Factors Equivalent to $abcacba$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p41
<p>We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern $xyzxzyx$. In fact, we</p><ul><li>characterize all the (two-way) infinite ternary square-free words avoiding letter pattern $xyzxzyx$</li><li>characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern $xyzxzyx$</li><li>show that the number of ternary square-free words of length $n$ avoiding letter pattern $xyzxzyx$ grows exponentially with $n$.</li></ul><p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </p>James Curriehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p41Fri, 27 May 2016 00:00:00 +1000Embedding Factorizations for 3-Uniform Hypergraphs II: $r$-Factorizations into $s$-Factorizations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p42
<p>Motivated by a 40-year-old problem due to Peter Cameron on extending partial parallelisms, we provide necessary and sufficient conditions under which one can extend an $r$-factorization of a complete $3$-uniform hypergraph on $m$ vertices, $K_m^3$, to an $s$-factorization of $K_n^3$. This generalizes an existing result of Baranyai and Brouwer — where they proved it for the case $r=s=1$.</p>Amin Bahmanian, Mike Newmanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p42Fri, 27 May 2016 00:00:00 +1000On Some Conjectures Concerning Critical Independent Sets of a Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p43
Let $G$ be a simple graph with vertex set $V(G)$. A set $S\subseteq V(G)$ is independent if no two vertices from $S$ are adjacent. For $X\subseteq V(G)$, the difference of $X$ is $d(X) = |X|-|N(X)|$ and an independent set $A$ is critical if $d(A) = \max \{d(X): X\subseteq V(G) \text{ is an independent set}\}$ (possibly $A=\emptyset$). Let $\text{nucleus}(G)$ and $\text{diadem}(G)$ be the intersection and union, respectively, of all maximum size critical independent sets in $G$. In this paper, we will give two new characterizations of Konig-Egervary graphs involving $\text{nucleus}(G)$ and $\text{diadem}(G)$. We also prove a related lower bound for the independence number of a graph. This work answers several conjectures posed by Jarden, Levit, and Mandrescu.Taylor Shorthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p43Fri, 10 Jun 2016 00:00:00 +1000Solutions to the T-Systems with Principal Coefficients
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p44
The $A_\infty$ T-system, also called the octahedron recurrence, is a dynamical recurrence relation. It can be realized as mutation in a coefficient-free cluster algebra (Kedem 2008, Di Francesco and Kedem 2009). We define T-systems with principal coefficients from cluster algebra aspect, and give combinatorial solutions with respect to any valid initial condition in terms of partition functions of perfect matchings, non-intersecting paths and networks. This also provides a solution to other systems with various choices of coefficients on T-systems including Speyer's octahedron recurrence (Speyer 2007), generalized lambda-determinants (Di Francesco 2013) and (higher) pentagram maps (Schwartz 1992, Ovsienko et al. 2010, Glick 2011, Gekhtman et al. 2016).Panupong Vichitkunakornhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p44Fri, 10 Jun 2016 00:00:00 +1000Lower Bounds for Cover-Free Families
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p45
<p>Let ${\cal F}$ be a set of blocks of a $t$-set $X$. A pair $(X,{\cal F})$ is called an $(w,r)$-cover-free family ($(w,r)-$CFF) provided that, the intersection of any $w$ blocks in ${\cal F}$ is not contained in the union of any other $r$ blocks in ${\cal F}$.</p><p>We give new asymptotic lower bounds for the number of minimum points $t$ in a $(w,r)$-CFF when $w\le r=|{\cal F}|^\epsilon$ for some constant $\epsilon\ge 1/2$.</p><p> </p>Ali Z. Abdi, Nader H. Bshoutyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p45Fri, 10 Jun 2016 00:00:00 +1000Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p46
<p>Given an $r$-uniform hypergraph $H=(V,E)$ and a weight function $\omega:E\to\{1,\dots,w\}$, a coloring of vertices of~$H$, induced by~$\omega$, is defined by $c(v) = \sum_{e\ni v} w(e)$ for all $v\in V$. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that $H$ is strongly $w$-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that $H$ is weakly $w$-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all $5$-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for $r\ge 6$ we show that almost all $r$-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for $r\ge 4$ almost all $r$-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are $r$-uniform hypergraphs which are not strongly $(r^2-r)$-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.</p>Patrick Bennett, Andrzej Dudek, Alan Frieze, Laars Heleniushttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p46Fri, 10 Jun 2016 00:00:00 +1000The Existence of a Maximal Green Sequence is not Invariant under Quiver Mutation
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p47
<span style="color: #000000; font-family: 'Lucida Grande', helvetica, arial, verdana, sans-serif; font-size: 14.3999996185303px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 20.1599998474121px; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none; background-color: #ffffff;">This note provides a quiver which does not admit a maximal green sequence, but which is mutation-equivalent to a quiver which does admit a maximal green sequence. The proof uses the `scattering diagrams' of Gross-Hacking-Keel-Kontsevich to show that a maximal green sequence for a quiver determines a maximal green sequence for any induced subquiver.</span>Greg Mullerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p47Fri, 10 Jun 2016 00:00:00 +1000Threshold and Hitting Time for High-Order Connectedness in Random Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p48
<p>We consider the following definition of connectedness in $k$-uniform hypergraphs: two $j$-sets (sets of $j$ vertices) are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. The hypergraph is $j$-connected if all $j$-sets are pairwise $j$-connected. We determine the threshold at which the random $k$-uniform hypergraph with edge probability $p$ becomes $j$-connected with high probability. We also deduce a hitting time result for the random hypergraph process <span>–</span> the hypergraph becomes $j$-connected at exactly the moment when the last isolated $j$-set disappears. This generalises the classical hitting time result of Bollob<span>á</span>s and Thomason for graphs.</p>Oliver Cooley, Mihyun Kang, Christoph Kochhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p48Fri, 10 Jun 2016 00:00:00 +1000Unsplittable Classes of Separable Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p49
A permutation class is splittable if it is contained in the merge of two of its proper subclasses. We characterise the unsplittable subclasses of the class of separable permutations both structurally and in terms of their bases.Michael Albert, Vít Jelínekhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p49Fri, 10 Jun 2016 00:00:00 +1000Painting Squares in $\Delta^2-1$ Shades
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p50
<p>Cranston and Kim conjectured that if $G$ is a connected graph with maximum degree $\Delta$ and $G$ is not a Moore Graph, then $\chi_{\ell}(G^2)\le \Delta^2-1$; here $\chi_{\ell}$ is the list chromatic number. We prove their conjecture; in fact, we show that this upper bound holds even for online list chromatic number.</p>Daniel W. Cranston, Landon Rabernhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p50Fri, 24 Jun 2016 00:00:00 +10002-Walk-Regular Dihedrants from Group-Divisible Designs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p51
<p>In this note, we construct bipartite $2$-walk-regular graphs with exactly 6 distinct eigenvalues as the point-block incidence graphs of group divisible designs with the dual property. For many of them, we show that they are 2-arc-transitive dihedrants. We note that some of these graphs are not described in Du et al. (2008), in which they classified the connected 2-arc transitive dihedrants. </p>Zhi Qiao, Shao Fei Du, Jack H Koolenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p51Fri, 24 Jun 2016 00:00:00 +1000Modeling Limits in Hereditary Classes: Reduction and Application to Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p52
<p>The study of limits of graphs led to elegant limit structures for sparse and dense graphs. This has been unified and generalized by the authors in a more general setting combining analytic tools and model theory to ${\rm FO}$-limits (and $X$-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.</p>Jaroslav Nešetřil, Patrice Ossona de Mendezhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p52Fri, 24 Jun 2016 00:00:00 +1000Decompositions of the Boolean Lattice into Rank-symmetric Chains
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p53
<p>The Boolean lattice $2^{[n]}$ is the power set of $[n]$ ordered by inclusion. A chain $c_{0}\subset\cdots\subset c_{k}$ in $2^{[n]}$ is rank-symmetric, if $|c_{i}|+|c_{k-i}|=n$ for $i=0,\ldots,k$; and it is symmetric, if $|c_{i}|=(n-k)/2+i$. We show that there exist a bijection $$p: [n]^{(\geq n/2)}\rightarrow [n]^{(\leq n/2)}$$ and a partial ordering $<$ on $[n]^{(\geq n/2)}$ satisfying the following properties:</p><ul><li>$\subset$ is an extension of $<$ on $[n]^{(\geq n/2)}$;</li><li>if $C\subset [n]^{(\geq n/2)}$ is a chain with respect to $<$, then $p(C)\cup C$ is a rank-symmetric chain in $2^{[n]}$, where $p(C)=\{p(x): x\in C\}$;</li><li>the poset $([n]^{(\geq n/2)},<)$ has the so called normalized matching property.</li></ul><p>We show two applications of this result.</p><p>A conjecture of <span> Füredi </span>asks if $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ chains such that the size of any two chains differ by at most 1. We prove an asymptotic version of this conjecture with the additional condition that every chain in the partition is rank-symmetric: $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ rank-symmetric chains, each of size $\Theta(\sqrt{n})$.</p><p>Our second application gives a lower bound for the number of symmetric chain partitions of $2^{[n]}$. We show that $2^{[n]}$ has at least $2^{\Omega(2^{n}\log n/\sqrt{n})}$ symmetric chain partitions.</p>István Tomonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p53Fri, 24 Jun 2016 00:00:00 +1000Distant Set Distinguishing Total Colourings of Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p54
The Total Colouring Conjecture suggests that $\Delta+3$ colours ought to suffice in order to provide a proper total colouring of every graph $G$ with maximum degree $\Delta$. Thus far this has been confirmed up to an additive constant factor, and the same holds even if one additionally requires every pair of neighbours in $G$ to differ with respect to the sets of their incident colours, so called <em>pallets</em>. Within this paper we conjecture that an upper bound of the form $\Delta+C$, for a constant $C>0$ still remains valid even after extending the distinction requirement to pallets associated with vertices at distance at most $r$, if only $G$ has minimum degree $\delta$ larger than a constant dependent on $r$. We prove that such assumption on $\delta$ is then unavoidable and exploit the probabilistic method in order to provide two supporting results for the conjecture. Namely, we prove the upper bound $(1+o(1))\Delta$ for every $r$, and show that for any fixed $\epsilon\in(0,1]$ and $r$, the conjecture holds if $\delta\geq \varepsilon\Delta$, i.e., in particular for regular graphs.Jakub Przybyłohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p54Fri, 24 Jun 2016 00:00:00 +1000The Total Acquisition Number of Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p55
<p>Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight on $v$ is at least as large as the weight on $u$. The total acquisition number of $G$, denoted by $a_t(G)$, is the minimum possible size of the set of vertices with positive weight at the end of the process.</p><p>LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of $p=p(n)$ such that $a_t(\mathcal{G}(n,p)) = 1$ with high probability, where $\mathcal{G}(n,p)$ is a binomial random graph. We show that $p = \frac{\log_2 n}{n} \approx 1.4427 \ \frac{\log n}{n}$ is a sharp threshold for this property. We also show that almost all trees $T$ satisfy $a_t(T) = \Theta(n)$, confirming a conjecture of West.</p>Deepak Bal, Patrick Bennett, Andrzej Dudek, Paweł Prałathttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p55Fri, 24 Jun 2016 00:00:00 +1000