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, 08 Jul 2016 11:21:05 +1000OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss604-Factor-Criticality of Vertex-Transitive Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p1
<p>A graph of order $n$ is $p$-factor-critical, where $p$ is an integer of the same parity as $n$, if the removal of any set of $p$ vertices results in a graph with a perfect matching. 1-factor-critical graphs and 2-factor-critical graphs are well-known factor-critical graphs and bicritical graphs, respectively. It is known that if a connected vertex-transitive graph has odd order, then it is factor-critical, otherwise it is elementary bipartite or bicritical. In this paper, we show that a connected vertex-transitive non-bipartite graph of even order at least 6 is 4-factor-critical if and only if its degree is at least 5. This result implies that each connected non-bipartite Cayley graph of even order and degree at least 5 is 2-extendable.</p>Wuyang Sun, Heping Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p1Fri, 08 Jul 2016 00:00:00 +1000Ramsey Numbers of Trees Versus Odd Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p2
Burr, Erd<span>ő</span>s, Faudree, Rousseau and Schelp initiated the study of Ramsey numbers of trees versus odd cycles, proving that $R(T_n, C_m) = 2n - 1$ for all odd $m \ge 3$ and $n \ge 756m^{10}$, where $T_n$ is a tree with $n$ vertices and $C_m$ is an odd cycle of length $m$. They proposed to study the minimum positive integer $n_0(m)$ such that this result holds for all $n \ge n_0(m)$, as a function of $m$. In this paper, we show that $n_0(m)$ is at most linear. In particular, we prove that $R(T_n, C_m) = 2n - 1$ for all odd $m \ge 3$ and $n \ge 25m$. Combining this with a result of Faudree, Lawrence, Parsons and Schelp yields $n_0(m)$ is bounded between two linear functions, thus identifying $n_0(m)$ up to a constant factor.Matthew Brennanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p2Fri, 08 Jul 2016 00:00:00 +1000Chip Games and Paintability
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p3
<p>We prove that the paint number of the complete bipartite graph $K_{N,N}$ is $\log N + O(1)$. As a consequence, we get that the difference between the paint number and the choice number of $K_{N,N}$ is $\Theta(\log \log N)$. This answers in the negative the question of Zhu (2009) whether this difference, for all graphs, can be bounded by a common constant. By a classical correspondence, our result translates to the framework of on-line coloring of uniform hypergraphs. This way we obtain that for every on-line two coloring algorithm there exists a $k$-uniform hypergraph with $\Theta(2^k)$ edges on which the strategy fails. The results are derived through an analysis of a natural family of chip games.</p>Lech Duraj, Grzegorz Gutowski, Jakub Kozikhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p3Fri, 08 Jul 2016 00:00:00 +1000A Generalized Alon-Boppana Bound and Weak Ramanujan Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p4
<p>A basic eigenvalue bound due to Alon and Boppana holds only for regular graphs. In this paper we give a generalized Alon-Boppana bound for eigenvalues of graphs that are not required to be regular. We show that a graph $G$ with diameter $k$ and vertex set $V$, the smallest nontrivial eigenvalue $\lambda_1$ of the normalized Laplacian $\mathcal L$ satisfies<br />$$<br /> \lambda_1 \leq 1-\sigma \big(1- \frac c {k} \big)<br />$$ for some constant $c$ where $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $ and $d_v$ denotes the degree of the vertex $v$.</p><p>We consider weak Ramanujan graphs defined as graphs satisfying $ \lambda_1 \geq 1-\sigma$. We examine the vertex expansion and edge expansion of weak Ramanujan graphs and then use the expansion properties among other methods to derive the above Alon-Boppana bound.</p>Fan Chunghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p4Fri, 08 Jul 2016 00:00:00 +1000Generalizing the Divisibility Property of Rectangle Domino Tilings
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p5
<p><!--StartFragment-->We introduce a class of graphs called <em>compound graphs</em>, which are constructed out of copies of a planar bipartite <em>base graph</em>, and explore the number of perfect matchings of compound graphs. The main result is that the number of matchings of every compound graph is divisible by the number of matchings of its base graph. Our approach is to use Kasteleyn's theorem to prove a key lemma, from which the divisibility theorem follows combinatorially. This theorem is then applied to provide a proof of Problem 21 of Propp's <em>Enumeration of Matchings</em>, a divisibility property of rectangles. Finally, we present a new proof, in the same spirit, of Ciucu's factorization theorem.<!--EndFragment--></p>Forest Tonghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p5Fri, 08 Jul 2016 00:00:00 +1000Orphans in Forests of Linear Fractional Transformations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p6
<p>A positive linear fractional transformation (PLFT) is a function of the form $f(z)=\frac{az+b}{cz+d}$ where $a,b,c$ and $d$ are nonnegative integers with determinant $ad-bc\neq 0$. Nathanson generalized the notion of the Calkin-Wilf tree to PLFTs and used it to partition the set of PLFTs into an infinite forest of rooted trees. The roots of these PLFT Calkin-Wilf trees are called orphans. In this paper, we provide a combinatorial formula for the number of orphans with fixed determinant $D$. In addition, we derive a method for determining the orphan ancestor of a given PLFT. Lastly, taking $z$ to be a complex number, we show that every positive complex number has finitely many ancestors in the forest of complex $(u,v)$-Calkin-Wilf trees.</p>Sandie Han, Ariane M. Masuda, Satyanand Singh, Johann Thielhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p6Fri, 08 Jul 2016 00:00:00 +1000An $n$-in-a-row Type Game
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p7
<pre>We consider a Maker-Breaker type game on the square grid, in which each</pre><pre> player takes <span>$t$</span> points on their <span>$t^\textrm{th}$</span> turn. Maker wins</pre><pre> if he obtains <span>$n$</span> points on a line (in any direction) without any of</pre><pre> Breaker's points between them. We show that, despite Maker's</pre><pre> apparent advantage, Breaker can prevent Maker from winning until</pre><pre> about his <span>$n^\textrm{th}$</span> turn. We actually prove a stronger</pre><pre> result: Breaker only needs to claim <span>$\omega(\log t)$</span> points on</pre><pre> his <span>$t^\textrm{th}$</span> turn to prevent Maker from winning until this</pre><pre> time. We also consider the situation when the number of points claimed by</pre><pre> Maker grows at other speeds, in particular, when Maker claims</pre><pre> <span>$t^\alpha$</span> points on his <span>$t^\textrm{th}$</span> turn.</pre><pre><!--EndFragment--></pre>Joshua Erde, Mark Waltershttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p7Fri, 22 Jul 2016 00:00:00 +1000The Topology of the External Activity Complex of a Matroid
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p8
<p>We prove that the external activity complex $\textrm{Act}_<(M)$ of a matroid is shellable. In fact, we show that every linear extension of LasVergnas's external/internal order $<_{ext/int}$ on $M$ provides a shelling of $\textrm{Act}_<(M)$. We also show that every linear extension of LasVergnas's internal order $<_{int}$ on $M$ provides a shelling of the independence complex $IN(M)$. As a corollary, $\textrm{Act}_<(M)$ and $M$ have the same $h$-vector. We prove that, after removing its cone points, the external activity complex is contractible if $M$ contains $U_{1,3}$ as a minor, and a sphere otherwise.</p>Federico Ardila, Federico Castillo, José Alejandro Samperhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p8Fri, 22 Jul 2016 00:00:00 +1000Locating-Total Dominating Sets in Twin-Free Graphs: a Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p9
A total dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$. A locating-total dominating set of $G$ is a total dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-total domination number of $G$, denoted $\gamma_t^L(G)$, is the minimum cardinality of a locating-total dominating set in $G$. It is well-known that every connected graph of order $n \ge 3$ has a total dominating set of size at most $\frac{2}{3}n$. We conjecture that if $G$ is a twin-free graph of order $n$ with no isolated vertex, then $\gamma_t^L(G) \le \frac{2}{3}n$. We prove the conjecture for graphs without $4$-cycles as a subgraph. We also prove that if $G$ is a twin-free graph of order $n$, then $\gamma_t^L(G) \le \frac{3}{4}n$.Florent Foucaud, Michael A. Henninghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p9Fri, 22 Jul 2016 00:00:00 +1000Which Haar graphs are Cayley graphs?
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p10
<span style="color: #000000;">For a finite group </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> and subset </span><span style="color: #008000;">$S$</span><span style="color: #000000;"> of </span><span style="color: #008000;">$G,$</span><span style="color: #000000;"> the </span><span style="color: #000000;">Haar</span><span style="color: #000000;"> graph </span><span style="color: #008000;">$H(G,S)$</span><span style="color: #000000;"> is a bipartite regular graph, defined as a regular </span><span style="color: #008000;">$G$</span><span style="color: #000000;">-cover of a dipole with </span><span style="color: #008000;">$|S|$ </span><span style="color: #000000;">parallel arcs </span><span style="color: #000000;">labelled</span><span style="color: #000000;"> by elements of </span><span style="color: #008000;">$S$</span><span style="color: #000000;">.</span><span style="color: #000000;"> If </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> is an </span><span style="color: #000000;">abelian</span><span style="color: #000000;"> group, then </span><span style="color: #008000;">$H(G,S)$</span><span style="color: #000000;"> is well-known to be a </span><span style="color: #000000;">Cayley</span><span style="color: #000000;"> graph;</span><span style="color: #000000;"> however, there are examples of non-</span><span style="color: #000000;">abelian</span><span style="color: #000000;"> groups </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> and subsets </span><span style="color: #008000;">$S$</span><span style="color: #000000;"> when this is not the case. In this paper we address the problem of classifying finite non-</span><span style="color: #000000;">abelian</span><span style="color: #000000;"> groups </span><span style="color: #008000;">$G$ </span><span style="color: #000000;">with the property that every </span><span style="color: #000000;">Haar</span><span style="color: #000000;"> graph </span><span style="color: #008000;">$H(G,S)$</span><span style="color: #000000;"> is a </span><span style="color: #000000;">Cayley</span><span style="color: #000000;"> graph. An equivalent condition for </span><span style="color: #008000;">$H(G,S)$</span><span style="color: #000000;"> to be a </span><span style="color: #000000;">Cayley</span><span style="color: #000000;"> graph of a group containing </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> is derived</span><span style="color: #000000;"> in terms of </span><span style="color: #008000;">$G, S$</span><span style="color: #000000;"> and </span><span style="color: #008000;">$\mathrm{Aut } G$</span><span style="color: #000000;">. It is also shown that the </span><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">dihedral</span><span style="color: #000000;"> groups, which are solutions to the above problem, are </span><span style="color: #008000;">$\mathbb{Z}_2^2,D_3,D_4$</span><span style="color: #000000;"> and </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #008000;">$D_{5}$</span><span style="color: #000000;">.</span></pre><pre style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </pre>István Estélyi, Tomaž Pisanskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p10Fri, 22 Jul 2016 00:00:00 +1000Szemerédi's Regularity Lemma via Martingales
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p11
We prove a variant of the abstract probabilistic version of Szemerédi's regularity lemma, due to Tao, which applies to a number of structures (including graphs, hypergraphs, hypercubes, graphons, and many more) and works for random variables in $L_p$ for any $p>1$. Our approach is based on martingale difference sequences.Pandelis Dodos, Vassilis Kanellopoulos, Thodoris Karageorgoshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p11Fri, 22 Jul 2016 00:00:00 +1000The Černý Conjecture and 1-Contracting Automata
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p12
<p>A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. <span>Černý </span>conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. We introduce the notion of aperiodically 1-contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the <span>Černý</span> conjecture holds for aperiodically 1-contracting automata. As a special case, we prove some results for circular automata.</p>Henk Donhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p12Fri, 22 Jul 2016 00:00:00 +1000Higher Bruhat Orders in Type B
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p13
Motivated by the geometry of hyperplane arrangements, Manin and Schechtman defined for each integer $n \geq 1$ a hierarchy of finite partially ordered sets $B(n, k),$ indexed by positive integers $k$, called the higher Bruhat orders. The poset $B(n, 1)$ is naturally identified with the weak left Bruhat order on the symmetric group $S_n$, each $B(n, k)$ has a unique maximal and a unique minimal element, and the poset $B(n, k + 1)$ can be constructed from the set of maximal chains in $B(n, k)$. Ben Elias has demonstrated a striking connection between the posets $B(n, k)$ for $k = 2$ and the diagrammatics of Bott-Samelson bimodules in type A, providing significant motivation for the development of an analogous theory of higher Bruhat orders in other Cartan-Killing types, particularly for $k = 2$. In this paper we present a partial generalization to type B, complete up to $k = 2$, prove a direct analogue of the main theorem of Manin and Schechtman, and relate our construction to the weak Bruhat order and reduced expression graph for Weyl group $B_n$.Seth Shelley-Abrahamson, Suhas Vijaykumarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p13Fri, 22 Jul 2016 00:00:00 +1000Refined Dual Stable Grothendieck Polynomials and Generalized Bender-Knuth Involutions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p14
The dual stable Grothendieck polynomials are a deformation of the Schur functions, originating in the study of the $K$-theory of the Grassmannian. We generalize these polynomials by introducing a countable family of additional parameters, and we prove that this generalization still defines symmetric functions. For this fact, we give two self-contained proofs, one of which constructs a family of involutions on the set of reverse plane partitions generalizing the Bender-Knuth involutions on semistandard tableaux, whereas the other classifies the structure of reverse plane partitions with entries $1$ and $2$.Pavel Galashin, Darij Grinberg, Gaku Liuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p14Fri, 22 Jul 2016 00:00:00 +1000Proof of Gessel's $\gamma$-Positivity Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p15
We prove a conjecture of Gessel, which asserts that the joint distribution of descents and inverse descents on permutations has a fascinating refined $\gamma$-positivity.Zhicong Linhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p15Fri, 22 Jul 2016 00:00:00 +1000Even More Infinite Ball Packings from Lorentzian Root Systems
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p16
<p>Boyd (1974) proposed a class of infinite ball packings that are generated by inversions. Later, Maxwell (1983) interpreted Boyd's construction in terms of root systems in Lorentz spaces. In particular, he showed that the space-like weight vectors correspond to a ball packing if and only if the associated Coxeter graph is of "level 2"'. In Maxwell's work, the simple roots form a basis of the representations space of the Coxeter group. In several recent studies, the more general based root system is considered, where the simple roots are only required to be positively independent. In this paper, we propose a geometric version of "level'' for root systems to replace Maxwell's graph theoretical "level''. Then we show that Maxwell's results naturally extend to the more general root systems with positively independent simple roots. In particular, the space-like extreme rays of the Tits cone correspond to a ball packing if and only if the root system is of level $2$. We also present a partial classification of level-$2$ root systems, namely the Coxeter $d$-polytopes of level-$2$ with $d+2$ facets.</p>Hao Chenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p16Fri, 05 Aug 2016 00:00:00 +1000Asymptotic Enumeration of Sparse Uniform Linear Hypergraphs with Given Degrees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p17
A hypergraph is <em>simple</em> if it has no loops and no repeated edges, and a hypergraph is <em>linear</em> if it is simple and each pair of edges intersects in at most one vertex. For $n\geq 3$, let $r= r(n)\geq 3$ be an integer and let $\boldsymbol{k} = (k_1,\ldots, k_n)$ be a vector of nonnegative integers, where each $k_j = k_j(n)$ may depend on $n$. Let $M = M(n) = \sum_{j=1}^n k_j$ for all $n\geq 3$, and define the set $\mathcal{I} = \{ n\geq 3 \mid r(n) \text{ divides } M(n)\}$. We assume that $\mathcal{I}$ is infinite, and perform asymptotics as $n$ tends to infinity along $\mathcal{I}$. Our main result is an asymptotic enumeration formula for linear $r$-uniform hypergraphs with degree sequence $\boldsymbol{k}$. This formula holds whenever the maximum degree $k_{\max}$ satisfies $r^4 k_{\max}^4(k_{\max} + r) = o(M)$. Our approach is to work with the incidence matrix of a hypergraph, interpreted as the biadjacency matrix of a bipartite graph, enabling us to apply known enumeration results for bipartite graphs. This approach also leads to a new asymptotic enumeration formula for simple uniform hypergraphs with specified degrees, and a result regarding the girth of random bipartite graphs with specified degrees.Vladimir Blinovsky, Catherine Greenhillhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p17Fri, 05 Aug 2016 00:00:00 +1000Cliques in Graphs Excluding a Complete Graph Minor
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p18
This paper considers the following question: What is the maximum number of $k$-cliques in an $n$-vertex graph with no $K_t$-minor? This question generalises the extremal function for $K_t$-minors, which corresponds to the $k=2$ case. The exact answer is given for $t\leq 9$ and all values of $k$. We also determine the maximum total number of cliques in an $n$-vertex graph with no $K_t$-minor for $t\leq 9$. Several observations are made about the case of general $t$.David R. Woodhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p18Fri, 05 Aug 2016 00:00:00 +1000Mixed Volumes of Hypersimplices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p19
In this paper we consider mixed volumes of combinations of hypersimplices. These numbers, called "mixed Eulerian numbers", were first considered by A. Postnikov and were shown to satisfy many properties related to Eulerian numbers, Catalan numbers, binomial coefficients, etc. We give a general combinatorial interpretation for mixed Eulerian numbers and prove the above properties combinatorially. In particular, we show that each mixed Eulerian number enumerates a certain set of permutations in $S_n$. We also prove several new properties of mixed Eulerian numbers using our methods. Finally, we consider a type B analogue of mixed Eulerian numbers and give an analogous combinatorial interpretation for these numbers.Gaku Liuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p19Fri, 05 Aug 2016 00:00:00 +1000On the Cohen-Macaulay Property for Quadratic Tangent Cones
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p20
Let $H$ be an $n$-generated numerical semigroup such that its tangent cone $\operatorname{gr}_\mathfrak{m} K[H]$ is defined by quadratic relations. We show that if $n<5$ then $\operatorname{gr}_\mathfrak{m} K[H]$ is Cohen-Macaulay, and for $n=5$ we explicitly describe the semigroups $H$ such that $\operatorname{gr}_\mathfrak{m} K[H]$ is not Cohen-Macaulay. As an application we show that if the field $K$ is algebraically closed and of characteristic different from two, and $n\leq 5$ then $\operatorname{gr}_\mathfrak{m} K[H]$ is Koszul if and only if (possibly after a change of coordinates) its defining ideal has a quadratic Gröbner basis.Dumitru I. Stamatehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p20Fri, 05 Aug 2016 00:00:00 +1000Face-Degree Bounds for Planar Critical Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p21
<p>The only remaining case of a well known conjecture of Vizing states that there is no planar graph with maximum degree 6 and edge chromatic number 7. We introduce parameters for planar graphs, based on the degrees of the faces, and study the question whether there are upper bounds for these parameters for planar edge-chromatic critical graphs. Our results provide upper bounds on these parameters for smallest counterexamples to Vizing's conjecture, thus providing a partial characterization of such graphs, if they exist.</p><p>For $k \leq 5$ the results give insights into the structure of planar edge-chromatic critical graphs.</p>Ligang Jin, Yingli Kang, Eckhard Steffenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p21Fri, 05 Aug 2016 00:00:00 +1000Face Rings of Cycles, Associahedra, and Standard Young Tableaux
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p24
<p><!--StartFragment-->We show that $J_n$, the Stanley-Reisner ideal of the $n$-cycle, has a free resolution supported on the $(n-3)$-dimensional simplicial associahedron $A_n$. This resolution is not minimal for $n \geq 6$; in this case the Betti numbers of $J_n$ are strictly smaller than the $f$-vector of $A_n$. We show that in fact the Betti numbers $\beta_{d}$ of $J_n$ are in bijection with the number of standard Young tableaux of shape $(d+1, 2, 1^{n-d-3})$. This complements the fact that the number of $(d-1)$-dimensional faces of $A_n$ are given by the number of standard Young tableaux of (super)shape $(d+1, d+1, 1^{n-d-3})$; a bijective proof of this result was first provided by Stanley. An application of discrete Morse theory yields a cellular resolution of $J_n$ that we show is minimal at the first syzygy. We furthermore exhibit a simple involution on the set of associahedron tableaux with fixed points given by the Betti tableaux, suggesting a Morse matching and in particular a poset structure on these objects.<!--EndFragment--></p>Anton Dochtermannhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p24Fri, 05 Aug 2016 00:00:00 +1000New Conjectures for Union-Closed Families
http://www.combinatorics.org/ojs/index.php/eljc/article/view/oldv23i3p25
The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets. From an optimization point of view, one could instead prove that $2a$ is an upper bound to the number of sets in a union-closed family on a ground set of $n$ elements where each element is in at most $a$ sets for all $a,n\in \mathbb{N}^+$. Similarly, one could prove that the minimum number of sets containing the most frequent element in a (non-empty) union-closed family with $m$ sets and $n$ elements is at least $\frac{m}{2}$ for any $m,n\in \mathbb{N}^+$. Formulating these problems as integer programs, we observe that the optimal values we computed do not vary with $n$. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we prove special cases of the new conjectures and discuss possible approaches to solve them completely.Jonad Pulaj, Annie Raymond, Dirk Theishttp://www.combinatorics.org/ojs/index.php/eljc/article/view/oldv23i3p25Fri, 05 Aug 2016 00:00:00 +1000A Generalization of Sperner's Theorem on Compressed Ideals
http://www.combinatorics.org/ojs/index.php/eljc/article/view/oldv23i3p26
<p>Let $[n]=\{1,2,\ldots,n\}$ and $\mathscr{B}_n=\{A: A\subseteq [n]\}$. A family $\mathscr{A}\subseteq \mathscr{B}_n$ is a Sperner family if $A\nsubseteq B$ and $B\nsubseteq A$ for distinct $A,B\in\mathscr{A}$. Sperner's theorem states that the density of the largest Sperner family in $\mathscr{B}_n$ is $\binom{n}{\left\lceil{n/2}\right\rceil}/2^n$. The objective of this note is to show that the same holds if $\mathscr{B}_n$ is replaced by compressed ideals over $[n]$.</p>Lili Mu, Yi Wanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/oldv23i3p26Fri, 05 Aug 2016 00:00:00 +1000On Symmetries in Phylogenetic Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p25
<p>Billey et al. [arXiv:1507.04976] have recently discovered a surprisingly simple formula for the number $a_n(\sigma)$ of leaf-labelled rooted non-embedded binary trees (also known as phylogenetic trees) with $n\geq 1$ leaves, fixed (for the relabelling action) by a given permutation $\sigma\in\frak{S}_n$. Denoting by $\lambda\vdash n$ the integer partition giving the sizes of the cycles of $\sigma$ in non-increasing order, they show by a guessing/checking approach that if $\lambda$ is a binary partition (it is known that $a_n(\sigma)=0$ otherwise), then<br />$$<br />a_n(\sigma)=\prod_{i=2}^{\ell(\lambda)}(2(\lambda_i+\cdots+\lambda_{\ell(\lambda)})-1),<br />$$<br />and they derive from it a formula and random generation procedure for tanglegrams (and more generally for tangled chains). Our main result is a combinatorial proof of the formula for $a_n(\sigma)$, which yields a simplification of the random sampler for tangled chains.</p>Éric Fusyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p25Fri, 19 Aug 2016 00:00:00 +1000Fast Möbius Inversion in Semimodular Lattices and ER-labelable Posets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p26
We consider the problem of fast zeta and Möbius transforms in finite posets, particularly in lattices. It has previously been shown that for a certain family of lattices, zeta and Möbius transforms can be computed in $O(e)$ elementary arithmetic operations, where $e$ denotes the size of the covering relation. We show that this family is exactly that of geometric lattices. We also extend the algorithms so that they work in $e$ operations for all semimodular lattices, including chains and divisor lattices. Finally, for both transforms, we provide a more general algorithm that works in $e$ operations for all ER-labelable posets.Petteri Kaski, Jukka Kohonen, Thomas Westerbäckhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p26Fri, 19 Aug 2016 00:00:00 +1000Guaranteed Scoring Games
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p27
<p>The class of Guaranteed Scoring Games (GS) are two-player combinatorial games with the property that Normal-play games (Conway et. al.) are ordered embedded into GS. They include, as subclasses, the scoring games considered by Milnor (1953), Ettinger (1996) and Johnson (2014). We present the structure of GS and the techniques needed to analyze a sum of guaranteed games. Firstly, GS form a partially ordered monoid, via defined Right- and Left-stops over the reals, and with disjunctive sum as the operation. In fact, the structure is a quotient monoid with partially ordered congruence classes. We show that there are four reductions that when applied, in any order, give a unique representative for each congruence class. The monoid is not a group, but in this paper we prove that if a game has an inverse it is obtained by 'switching the players'. The order relation between two games is defined by comparing their stops in <em>any</em> disjunctive sum. Here, we demonstrate how to compare the games via a finite algorithm instead, extending ideas of Ettinger, and also Siegel (2013).</p>Urban Larsson, Richard J. Nowakowski, João P. Neto, Carlos P. Santoshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p27Fri, 19 Aug 2016 00:00:00 +1000A New Construction of Non-Extendable Intersecting Families of Sets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p28
In 1975, Lovász conjectured that any maximal intersecting family of $k$-sets has at most $\lfloor(e-1)k!\rfloor$ blocks, where $e$ is the base of the natural logarithm. This conjecture was disproved in 1996 by Frankl and his co-authors. In this short note, we reprove the result of Frankl et al. using a vastly simplified construction of maximal intersecting families with many blocks. This construction yields a maximal intersecting family $\mathbb{G}_{k}$ of $k-$sets whose number of blocks is asymptotic to $e^{2}(\frac{k}{2})^{k-1}$ as $k\rightarrow\infty$.Kaushik Majumderhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p28Fri, 19 Aug 2016 00:00:00 +1000All Ramsey Numbers for Brooms in Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p29
For $k,\ell\ge 1$, a broom $B_{k,\ell}$ is a tree on $n=k+\ell$ vertices obtained by connecting the central vertex of a star $K_{1,k}$ with an end-vertex of a path on $\ell-1$ vertices. As $B_{n-2,2}$ is a star and $B_{1,n-1}$ is a path, their Ramsey number have been determined among rarely known $R(T_n)$ of trees $T_n$ of order $n$. Erd<span>ő</span>s, Faudree, Rousseau and Schelp determined the value of $R(B_{k,\ell})$ for $\ell\ge 2k\geq2$. We shall determine all other $R(B_{k,\ell})$ in this paper, which says that, for fixed $n$, $R(B_{n-\ell,\ell})$ decreases first on $1\le\ell \le 2n/3$ from $2n-2$ or $2n-3$ to $\lceil\frac{4n}{3}\rceil-1$, and then it increases on $2n/3 < \ell\leq n$ from $\lceil\frac{4n}{3}\rceil-1$ to $\lfloor\frac{3n}{2}\rfloor -1$. Hence $R(B_{n-\ell,\ell})$ may attain the maximum and minimum values of $R(T_n)$ as $\ell$ varies.Pei Yu, Yusheng Lihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p29Fri, 19 Aug 2016 00:00:00 +1000Characteristic Flows on Signed Graphs and Short Circuit Covers
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p30
<p>We generalise to signed graphs a classical result of Tutte [Canad. J. Math. 8 (1956), 13<span class="_Tgc">—</span>28] stating that every integer flow can be expressed as a sum of characteristic flows of circuits. In our generalisation, the rôle of circuits is taken over by signed circuits of a signed graph which occur in two types <span class="_Tgc">—</span> either balanced circuits or pairs of disjoint unbalanced circuits connected with a path intersecting them only at its ends. As an application of this result we show that a signed graph $G$ admitting a nowhere-zero $k$-flow has a covering with signed circuits of total length at most $2(k-1)|E(G)|$.</p>Edita Máčajová, Martin Škovierahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p30Fri, 19 Aug 2016 00:00:00 +1000Generating Functions of Bipartite Maps on Orientable Surfaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p31
We compute, for each genus $g\geq 0$, the generating function $L_g\equiv L_g(t;p_1,p_2,\dots)$ of (labelled) bipartite maps on the orientable surface of genus $g$, with control on all face degrees. We exhibit an explicit change of variables such that for each $g$, $L_g$ is a rational function in the new variables, computable by an explicit recursion on the genus. The same holds for the generating function $F_g$ of <em>rooted</em> bipartite maps. The form of the result is strikingly similar to the Goulden/Jackson/Vakil and Goulden/Guay-Paquet /Novak formulas for the generating functions of classical and monotone Hurwitz numbers respectively, which suggests stronger links between these models. Our result complements recent results of Kazarian and Zograf, who studied the case where the number of faces is bounded, in the equivalent formalism of <em>dessins d'enfants</em>. Our proofs borrow some ideas from Eynard's "topological recursion" that he applied in particular to even-faced maps (unconventionally called "bipartite maps" in his work). However, the present paper requires no previous knowledge of this topic and comes with elementary (complex-analysis-free) proofs written in the perspective of formal power series.<br /><br />Guillaume Chapuy, Wenjie Fanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p31Fri, 19 Aug 2016 00:00:00 +1000A Decomposition of Parking Functions by Undesired Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p32
There is a well-known bijection between parking functions of a fixed length and maximal chains of the noncrossing partition lattice which we can use to associate to each set of parking functions a poset whose Hasse diagram is the union of the corresponding maximal chains. We introduce a decomposition of parking functions based on the largest number omitted and prove several theorems about the corresponding posets. In particular, they share properties with the noncrossing partition lattice such as local self-duality, a nice characterization of intervals, a readily computable M<span>ö</span>bius function, and a symmetric chain decomposition. We also explore connections with order complexes, labeled Dyck paths, and rooted forests.Melody Bruce, Michael Dougherty, Max Hlavacek, Ryo Kudo, Ian Nicolashttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p32Fri, 19 Aug 2016 00:00:00 +1000On the Additive Bases Problem in Finite Fields
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p33
We prove that if $G$ is an Abelian group and $A_1,\ldots,A_k \subseteq G$ satisfy $m A_i=G$ (the $m$-fold sumset), then $A_1+\cdots+A_k=G$ provided that $k \ge c_m \log \log |G|$. This generalizes a result of Alon, Linial, and Meshulam [Additive bases of vector spaces over prime fields. <em>J. Combin. Theory Ser. A</em>, 57(2):203<span class="_Tgc">—</span>210, 1991] regarding so-called additive bases.Victoria de Quehen, Hamed Hatamihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p33Fri, 19 Aug 2016 00:00:00 +1000Cubic Non-Cayley Vertex-Transitive Bi-Cayley Graphs over a Regular $p$-Group
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p34
A bi-Cayley graph is a graph which admits a semiregular group of automorphisms with two orbits of equal size. In this paper, we give a characterization of cubic non-Cayley vertex-transitive bi-Cayley graphs over a regular $p$-group, where $p>5$ is an odd prime. As an application, a classification of cubic non-Cayley vertex-transitive graphs of order $2p^3$ is given for each prime $p$.Jin-Xin Zhou, Yan-Quan Fenghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p34Fri, 19 Aug 2016 00:00:00 +1000The Number of Prefixes of Minimal Factorisations of a Cycle
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p35
We prove in two different ways that the number of distinct prefixes of length $k$ of minimal factorisations of the $n$-cycle $(1\ldots n)$ as a product of $n-1$ transpositions is $\binom{n}{k+1}n^{k-1}$. Our first proof is not bijective but makes use of a correspondence between minimal factorisations and Cayley trees. The second proof consists of establishing a bijection between the set which we want to enumerate and the set of parking functions of a certain kind, which can be counted by a standard conjugation argument.Thierry Lévyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p35Fri, 19 Aug 2016 00:00:00 +1000On Generalizations of Separating and Splitting Families
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p36
Starting from the well-established notion of a separating family (or separating system) and the refinement known as a splitting family, we define and study generalizations called $n$-separating and $n$-splitting families, obtaining lower and upper bounds on their minimum sizes. For $n$-separating families our bounds are asymptotically tight within a linear factor, while for $n$-splitting families we provide partial results and open questions.Daniel Condon, Samuel Coskey, Luke Serafin, Cody Stockdalehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p36Fri, 19 Aug 2016 00:00:00 +1000A Better Lower Bound on Average Degree of 4-List-Critical Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p37
This short note proves that every non-complete $k$-list-critical graph has average degree at least $k-1 + \frac{k-3}{k^2-2k+2}$. This improves the best known bound for $k = 4,5,6$. The same bound holds for online $k$-list-critical graphs.Landon Rabernhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p37Fri, 19 Aug 2016 00:00:00 +1000Infinite Orders and Non-D-finite Property of 3-Dimensional Lattice Walks
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p38
<p>Recently, Bostan and his coauthors investigated lattice walks restricted to the non-negative octant $\mathbb{N}^3$. For the $35548$ non-trivial models with at most six steps, they found that many models associated to a group of order at least $200$ and conjectured these groups were in fact infinite groups. In this paper, we first confirm these conjectures and then consider the non-$D$-finite property of the generating function for some of these models.</p>Daniel K. Du, Qing-Hu Hou, Rong-Hua Wanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p38Fri, 19 Aug 2016 00:00:00 +1000Counting Trees in Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p39
<p>Erd<span>ő</span>s and Simonovits proved that the number of paths of length $t$ in an $n$-vertex graph of average degree $d$ is at least $(1 - \delta) nd(d - 1) \cdots (d - t + 1)$, where $\delta = (\log d)^{-1/2 + o(1)}$ as $d \rightarrow \infty$. In this paper, we strengthen and generalize this result as follows. Let $T$ be a tree with $t$ edges. We prove that for any $n$-vertex graph $G$ of average degree $d$ and minimum degree greater than $t$, the number of labelled copies of $T$ in $G$ is at least \[(1 - \varepsilon) n d(d - 1) \cdots (d - t + 1)\] where $\varepsilon = O(d^{-2})$ as $d \rightarrow \infty$. This bound is tight except for the term $1 - \varepsilon$, as shown by a disjoint union of cliques. Our proof is obtained by first showing a lower bound that is a convex function of the degree sequence of $G$, and this answers a question of Dellamonica et. al.</p>Jacques Verstraete, Dhruv Mubayihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p39Fri, 19 Aug 2016 00:00:00 +1000