The Electronic Journal of Combinatorics
http://www.combinatorics.org/ojs/index.php/eljc
<p>The Electronic Journal of Combinatorics (E-JC) is a fully-refereed electronic journal with <em>very high standards,</em> publishing papers of substantial content and interest in all branches of discrete mathematics, including combinatorics, graph theory, and algorithms for combinatorial problems. The journal is <em>completely free</em> for both authors and readers. Authors retain the copyright of their articles. Articles published in E-JC are reviewed on MathSciNet and ZBMath, and are indexed by Web of Science. The latest papers are always available by clicking on the tab marked "Current" near the top of the page. You can also locate papers using the search facility on the right hand side of this page.</p><p>E-JC was founded in 1994 by Herbert S. Wilf and Neil Calkin, making it one of the oldest electronic journals.</p>en-US<p>The copyright of published papers remains with the authors. We only require your agreement that we publish it, as described in the following publication release agreement:</p><ol><li>This is an agreement between the Electronic Journal of Combinatorics (the "Journal"), and the copyright owner (the "Owner") of a work (the "Work") to be published in the Journal.</li><li>The Owner warrants that s/he has the full power and authority to enter into this Agreement and to grant the rights granted in this Agreement.</li><li>The Owner hereby grants to the Journal a worldwide, irrevocable, royalty free license to publish or distribute the Work, to enter into arrangements with others to publish or distribute the Work, and to archive the Work.</li><li>The Owner agrees that further publication of the Work, with the same or substantially the same content as appears in the Journal, will include an acknowledgement of prior publication in the Journal.</li></ol>akundgen@csusm.edu (André Kündgen)bdm@cs.anu.edu.au (Brendan McKay)Thu, 02 Oct 2014 06:05:01 +1000OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60The Optimal Drawings of $K_{5,n}$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p1
<p>Zarankiewicz's Conjecture (ZC) states that the crossing number cr$(K_{m,n})$ equals $Z(m,n):=\lfloor{\frac{m}{2}}\rfloor \lfloor{\frac{m-1}{2}}\rfloor \lfloor{\frac{n}{2}}\rfloor \lfloor{\frac{n-1}{2}}\rfloor$. Since Kleitman's verification of ZC for $K_{5,n}$ (from which ZC for $K_{6,n}$ easily follows), very little progress has been made around ZC; the most notable exceptions involve computer-aided results. With the aim of gaining a more profound understanding of this notoriously difficult conjecture, we investigate the <em>optimal</em> (that is, crossing-minimal) drawings of $K_{5,n}$. The widely known natural drawings of $K_{m,n}$ (the so-called <em>Zarankiewicz drawings</em>) with $Z(m,n)$ crossings contain <em>antipodal</em> vertices, that is, pairs of degree-$m$ vertices such that their induced drawing of $K_{m,2}$ has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr$(K_{5,n}) = Z(5,n)$. We explore in depth the role of antipodal vertices in optimal drawings of $K_{5,n}$, for $n$ even. We prove that if {$n \equiv 2$ (mod $4$)}, then every optimal drawing of $K_{5,n}$ has antipodal vertices. We also exhibit a two-parameter family of optimal drawings $D_{r,s}$ of $K_{5,4(r+s)}$ (for $r,s\ge 0$), with no antipodal vertices, and show that if $n\equiv 0$ (mod $4$), then every optimal drawing of $K_{5,n}$ without antipodal vertices is (vertex rotation) isomorphic to $D_{r,s}$ for some integers $r,s$. As a corollary, we show that if $n$ is even, then every optimal drawing of $K_{5,n}$ is the superimposition of Zarankiewicz drawings with a drawing isomorphic to $D_{r,s}$ for some nonnegative integers $r,s$.</p>César Hernández-Vélez, Carolina Medina, Gelasio Salazarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p1Thu, 02 Oct 2014 00:00:00 +1000Limits of Boolean Functions on $\mathbb{F}_p^n$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p2
<p>We study sequences of functions of the form $\mathbb{F}_p^n \to \{0,1\}$ for varying $n$, and define a notion of convergence based on the induced distributions from restricting the functions to a random affine subspace. Using a decomposition theorem and a recently proven equi-distribution theorem from higher order Fourier analysis, we prove that the limits of such convergent sequences can be represented by certain measurable functions. We also show that every such limit object arises as the limit of some sequence of functions. These results are in the spirit of similar results which have been developed for limits of graph sequences. A more general, albeit substantially more sophisticated, limit object was recently constructed by Balázs Szegedy [Gowers norms, regularization and limits of functions on abelian groups. 2010. arXiv:1010.6211].</p>Hamed Hatami, Pooya Hatami, James Hirsthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p2Thu, 02 Oct 2014 00:00:00 +1000Permutation Reconstruction from Differences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3
We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is $\sf{NP}$-complete. As an intermediate step we first prove the $\sf{NP}$-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.Marzio De Biasihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3Thu, 02 Oct 2014 00:00:00 +1000Isometric Embeddings of Half-Cube Graphs in Half-Spin Grassmannians
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p4
Let $\Pi$ be a polar space of type $\textsf{D}_{n}$. Denote by ${\mathcal G}_{\delta}(\Pi)$, $\delta\in \{+,-\}$ the associated half-spin Grassmannians and write $\Gamma_{\delta}(\Pi)$ for the corresponding half-spin Grassmann graphs. In the case when $n\ge 4$ is even, the apartments of ${\mathcal G}_{\delta}(\Pi)$ will be characterized as the images of isometric embeddings of the half-cube graph $\frac{1}{2}H_n$ in $\Gamma_{\delta}(\Pi)$. As an application, we describe all isometric embeddings of $\Gamma_{\delta}(\Pi)$ in the half-spin Grassmann graphs associated to a polar space of type $\textsf{D}_{n'}$ under the assumption that $n\ge 6$ is even.Mark Pankovhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p4Thu, 02 Oct 2014 00:00:00 +1000An Extension of Turán's Theorem, Uniqueness and Stability
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p5
We determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $M\subset V(G)$. For $(r-1)|M|\ge n$, the $(r-1)$-partite Turán graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguethttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p5Thu, 02 Oct 2014 00:00:00 +1000Coxeter-Knuth Graphs and a Signed Little Map for Type B Reduced Words
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p6
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span>We define an analog of David Little’s algorithm for reduced words in type B, and investigate its main properties. In particular, we show that our algorithm preserves the recording tableau of Kra<span>ś</span>kiewicz insertion, and that it provides a bijective realization of the Type B transition equations in Schubert calculus. Many other aspects of type A theory carry over to this new setting. Our primary tool is a shifted version of the dual equivalence graphs defined by Assaf and further developed by Roberts. We provide an axiomatic characterization of shifted dual equivalence graphs, and use them to prove a structure theorem for the graph of Type B Coxeter-Knuth relations. </span></p></div></div></div>Sara Billey, Zachary Hamaker, Austin Roberts, Benjamin Younghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p6Thu, 02 Oct 2014 00:00:00 +1000Enumerating Hamiltonian Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7
<p style="-qt-block-indent: 0; text-indent: 0px; -qt-user-state: 0; margin: 0px;">A dynamic programming method for enumerating hamiltonian cycles in arbitrary graphs is presented. The method is applied to grid graphs, king's graphs, triangular grids, and three-dimensional grid graphs, and results are obtained for larger cases than previously published. The approach can easily be modified to enumerate hamiltonian paths and other similar structures.</p>Ville H. Petterssonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7Thu, 09 Oct 2014 00:00:00 +1100New Infinite Families of Congruences Modulo 8 for Partitions with Even Parts Distinct
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p8
Let $ped(n)$ denote the number of partitions of an integer $n$ wherein even parts are distinct. Recently, Andrews, Hirschhorn and Sellers, Chen, and Cui and Gu have derived a number of interesting congruences modulo 2, 3 and 4 for $ped(n)$. In this paper we prove several new infinite families of congruences modulo 8 for $ped(n)$. For example, we prove that for $ \alpha \geq 0$ and $n\geq 0$,<br />\[<br /> ped\left(3^{4\alpha+4}n+\frac{11\times 3^{4\alpha+3}-1}{8}\right)\equiv 0 \ ({\rm mod \ 8}).<br />\]Ernest X. W. Xiahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p8Thu, 09 Oct 2014 00:00:00 +1100Graph Homomorphisms between Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p9
<p>In this paper we study several problems concerning the number of homomorphisms of trees. We begin with an algorithm for the number of homomorphisms from a tree to any graph. By using this algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization and a dual of <span>Bollobás</span> and Tyomkyn's result concerning the number of walks in trees.</p><p>Some other main results of the paper are the following. Denote by $\hom(H,G)$ the number of homomorphisms from a graph $H$ to a graph $G$. For any tree $T_m$ on $m$ vertices we give a general lower bound for $\hom(T_m,G)$ by certain entropies of Markov chains defined on the graph $G$. As a particular case, we show that for any graph $G$, <br />$$\exp(H_{\lambda}(G))\lambda^{m-1}\leq\hom(T_m,G),$$ <br />where $\lambda$ is the largest eigenvalue of the adjacency matrix of $G$ and $H_{\lambda}(G)$ is a certain constant depending only on $G$ which we call the spectral entropy of $G$. We also show that if $T_m$ is any fixed tree and<br />$$\hom(T_m,P_n)>\hom(T_m,T_n),$$for some tree $T_n$ on $n$ vertices, then $T_n$ must be the tree obtained from a path $P_{n-1}$ by attaching a pendant vertex to the second vertex of $P_{n-1}$.</p><p>All the results together enable us to show that among all trees with fixed number of vertices, the path graph has the fewest number of endomorphisms while the star graph has the most.</p>Péter Csikvári, Zhicong Linhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p9Thu, 09 Oct 2014 00:00:00 +1100The Range of a Simple Random Walk on $\mathbb{Z}$: An Elementary Combinatorial Approach
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p10
<p>Two different elementary approaches for deriving an explicit formula for the distribution of the range of a simple random walk on $\mathbb{Z}$ of length $n$ are presented. Both of them rely on Hermann Weyl's discrepancy norm, which equals the maximal partial sum of the elements of a sequence. By this the original combinatorial problem on $\mathbb{Z}$ can be turned into a known path-enumeration problem on a bounded lattice. The solution is provided by means of the adjacency matrix $\mathbf Q_d$ of the walk on a bounded lattice $(0,1,\ldots,d)$. The second approach is algebraic in nature, and starts with the adjacency matrix $\mathbf{Q_d}$. The powers of the adjacency matrix are expanded in terms of products of non-commutative left and right shift matrices. The representation of such products by means of the discrepancy norm reveals the solution directly.</p>Bernhard A. Moserhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p10Thu, 09 Oct 2014 00:00:00 +1100Operators of Equivalent Sorting Power and Related Wilf-equivalences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p11
We study sorting operators $\mathbf{A}$ on permutations that are obtained composing Knuth's stack sorting operator $\mathbf{S}$ and the reversal operator $\mathbf{R}$, as many times as desired. For any such operator $\mathbf{A}$, we provide a size-preserving bijection between the set of permutations sorted by $\mathbf{S} \circ \mathbf{A}$ and the set of those sorted by $\mathbf{S} \circ \mathbf{R} \circ \mathbf{A}$, proving that these sets are enumerated by the same sequence, but also that many classical permutation statistics are equidistributed across these two sets. The description of this family of bijections is based on a bijection between the set of permutations avoiding the pattern $231$ and the set of those avoiding $132$ which preserves many permutation statistics. We also present other properties of this bijection, in particular for finding pairs of Wilf-equivalent permutation classes.<br /><br />Michael Albert, Mathilde Bouvelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p11Thu, 09 Oct 2014 00:00:00 +1100$k$-Fold Sidon Sets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p12
Let $k \geq 1$ be an integer. A set $A \subset \mathbb{Z}$ is a $k$<em>-fold Sidon set </em>if $A$ has only trivial solutions to each equation of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 = 0$ where $0 \leq |c_i | \leq k$, and $c_1 + c_2 + c_3 + c_4 = 0$. We prove that for any integer $k \geq 1$, a $k$-fold Sidon set $A \subset [N]$ has at most $(N/k)^{1/2} + O((Nk)^{1/4})$ elements. Indeed we prove that given any $k$ positive integers $c_1<\cdots <c_k$, any set $A\subset [N]$ that contains only trivial solutions to $c_i(x_1-x_2)=c_j(x_3-x_4)$ for each $1 \le i \le j \le k$, has at most $(N/k)^{1/2}+O((c_k^2N/k)^{1/4})$ elements. On the other hand, for any $k \geq 2$ we can exhibit $k$ positive integers $c_1,\dots, c_k$ and a set $A\subset [N]$ with $|A|\ge (\frac 1k+o(1))N^{1/2}$, such that $A$ has only trivial solutions to $c_i(x_1 - x_2) = c_j (x_3 - x_4)$ for each $1 \le i \le j\le k$.Javier Cilleruelo, Craig Timmonshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p12Thu, 09 Oct 2014 00:00:00 +1100On Sets with Few Intersection Numbers in Finite Projective and Affine Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p13
<p>In this paper we study sets $X$ of points of both affine and projective spaces over the Galois field $\mathop{\rm{GF}}(q)$ such that every line of the geometry that is neither contained in $X$ nor disjoint from $X$ meets the set $X$ in a constant number of points and we determine all such sets. This study has its main motivation in connection with a recent study of neighbour transitive codes in Johnson graphs by Liebler and Praeger [<em>Designs, Codes and Crypt.</em>, 2014]. We prove that, up to complements, in $\mathop{\rm{PG}}(n,q)$ such a set $X$ is either a subspace or $n=2,q$ is even and $X$ is a maximal arc of degree $m$. In $\mathop{\rm{AG}}(n,q)$ we show that $X$ is either the union of parallel hyperplanes or a cylinder with base a maximal arc of degree $m$ (or the complement of a maximal arc) or a cylinder with base the projection of a quadric. Finally we show that in the affine case there are examples (different from subspaces or their complements) in $\mathop{\rm{AG}}(n,4)$ and in $\mathop{\rm{AG}}(n,16)$ giving new neighbour transitive codes in Johnson graphs.</p>Nicola Durantehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p13Thu, 16 Oct 2014 00:00:00 +1100Mutations of Fake Weighted Projective Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p14
We characterise mutations between fake weighted projective spaces, and give explicit formulas for how the weights and multiplicity change under mutation. In particular, we prove that multiplicity-preserving mutations between fake weighted projective spaces are mutations over edges of the corresponding simplices. As an application, we analyse the canonical and terminal fake weighted projective spaces of maximal degree.Tom Coates, Samuel Gonshaw, Alexander Kasprzyk, Navid Nabijouhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p14Thu, 16 Oct 2014 00:00:00 +1100The Combinatorial Nullstellensätze Revisited
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p15
We revisit and further explore the celebrated Combinatorial Nullstellensätze of N. Alon in several different directions.Pete L. Clarkhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p15Thu, 16 Oct 2014 00:00:00 +1100Decomposing Labeled Interval Orders as Pairs of Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p16
We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.Anders Claesson, Stuart A. Hannahhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p16Thu, 16 Oct 2014 00:00:00 +1100Chromatic Bounds on Orbital Chromatic Roots
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p17
<p><!--StartFragment-->Given a group $G$ of automorphisms of a graph $\Gamma$, the orbital chromatic polynomial $OP_{\Gamma,G}(x)$ is the polynomial whose value at a positive integer $k$ is the number of orbits of $G$ on proper $k$-colorings of $\Gamma.$ Cameron and Kayibi introduced this polynomial as a means of understanding roots of chromatic polynomials. In this light, they posed a problem asking whether the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root of its chromatic polynomial. We resolve this problem in a resounding negative by not only constructing a counterexample, but by providing a process for generating families of counterexamples. We additionally begin the program of finding classes of graphs whose orbital chromatic polynomials have real roots bounded above by the largest real root of their chromatic polynomials; in particular establishing this for many outerplanar graphs.<!--EndFragment--></p>Dae Hyun Kim, Alexander H. Mun, Mohamed Omarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p17Thu, 23 Oct 2014 00:00:00 +1100Enumerating Permutations by their Run Structure
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p18
<p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">Motivated by a problem in quantum field theory, we study the up and down structure of circular and linear permutations. In particular, we count the length of the (alternating) runs of permutations by representing them as monomials and find that they can always be decomposed into so-called 'atomic' permutations introduced in this work. This decomposition allows us to enumerate the (circular) permutations of a subset of $\mathbb{N}$ by the length of their runs. Furthermore, we rederive, in an elementary way and using the methods developed here, a result due to Kitaev on the enumeration of valleys.</p>Christopher J. Fewster, Daniel Siemssenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p18Thu, 23 Oct 2014 00:00:00 +1100Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19
<p>Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width.</p><p>This extends known results on rapid mixing for the Tutte polynomial, adjacency-rank ($R_2$-)polynomial and interlace polynomial. In particular Glauber dynamics for the $R_2$-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.</p>Magnus Bordewich, Ross J. Kanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19Thu, 23 Oct 2014 00:00:00 +1100Schreier Graphs of an Extended Version of the Binary Adding Machine
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p20
<p>In this paper we give a complete classification of the infinite Schreier graphs of an automaton group generated by an extended version of the binary adding machine.</p>Daniele D'Angelihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p20Thu, 30 Oct 2014 00:00:00 +1100On the Subpartitions of the Ordinary Partitions, II
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p21
<p>In this note, we provide a new proof for the number of partitions of $n$ having subpartitions of length $\ell$ with gap $d$. Moreover, by generalizing the definition of a subpartition, we show what is counted by $q$-expansion</p><p>\[\prod_{n=1}^{\infty} \frac{1}{1-q^n} \sum_{n=0}^{\infty} (-1)^n q^{(an^2 + bn)/2}\]</p><p>and how fast it grows. Moreover, we prove there is a special sign pattern for the coefficients of $q$-expansion</p><p>\[\prod_{n=1}^{\infty} \frac{1}{1-q^n} \left( 1 - 2 \sum_{n=0}^{\infty} (-1)^n q^{(an^2 + bn)/2} \right).\]</p>Byungchan Kim, Eunmi Kimhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p21Thu, 30 Oct 2014 00:00:00 +1100Turán Problems on Non-Uniform Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p22
A non-uniform hypergraph $H=(V,E)$ consists of a vertex set $V$ and an edge set $E\subseteq 2^V$; the edges in $E$ are not required to all have the same cardinality. The set of all cardinalities of edges in $H$ is denoted by $R(H)$, the set of edge types. For a fixed hypergraph $H$, the Turán density $\pi(H)$ is defined to be $\lim_{n\to\infty}\max_{G_n}h_n(G_n)$, where the maximum is taken over all $H$-free hypergraphs $G_n$ on $n$ vertices satisfying $R(G_n)\subseteq R(H)$, and $h_n(G_n)$, the so called Lubell function, is the expected number of edges in $G_n$ hit by a random full chain. This concept, which generalizes the Turán density of $k$-uniform hypergraphs, is motivated by recent work on extremal poset problems. The details connecting these two areas will be revealed in the end of this paper.<br /><br />Several properties of Turán density, such as supersaturation, blow-up, and suspension, are generalized from uniform hypergraphs to non-uniform hypergraphs. Other questions such as "Which hypergraphs are degenerate?" are more complicated and don't appear to generalize well. In addition, we completely determine the Turán densities of $\{1,2\}$-hypergraphs.J. Travis Johnston, Linyuan Luhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p22Thu, 30 Oct 2014 00:00:00 +1100Counting Permutations by Alternating Descents
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p23
<p>We find the exponential generating function for permutations with all valleys even and all peaks odd, and use it to determine the asymptotics for its coefficients, answering a question posed by Liviu Nicolaescu. The generating function can be expressed as the reciprocal of a sum involving Euler numbers: <br />\[<br />\left(1-E_1x+E_{3}\frac{x^{3}}{3!}-E_{4}\frac{x^{4}}{4!}+E_{6}\frac{x^{6}}{6!}-E_{7}\frac{x^{7}}{7!}+\cdots\right)^{-1},<br />\tag{$*$}<br />\]<br />where $\sum_{n=0}^\infty E_n x^n\!/n! = \sec x + \tan x$. We give two proofs of this formula. The first uses a system of differential equations whose solution gives the generating function<br />\begin{equation*}<br />\frac{3\sin\left(\frac{1}{2}x\right)+3\cosh\left(\frac{1}{2}\sqrt{3}x\right)}{3\cos\left(\frac{1}{2}x\right)-\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}x\right)},<br />\end{equation*} <br />which we then show is equal to $(*)$. The second proof derives $(*)$ directly from general permutation enumeration techniques, using noncommutative symmetric functions. The generating function $(*)$ is an "alternating" analogue of David and Barton's generating function <br />\[<br />\left(1-x+\frac{x^{3}}{3!}-\frac{x^{4}}{4!}+\frac{x^{6}}{6!}-\frac{x^{7}}{7!}+\cdots\right)^{-1},<br />\]<br />for permutations with no increasing runs of length 3 or more. Our general results give further alternating analogues of permutation enumeration formulas, including results of Chebikin and Remmel.</p>Ira M. Gessel, Yan Zhuanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p23Thu, 30 Oct 2014 00:00:00 +1100Some Spectral Properties of Uniform Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p24
For a $k$-uniform hypergraph $H$, we obtain some trace formulas for the Laplacian tensor of $H$, which imply that $\sum_{i=1}^nd_i^s$ ($s=1,\ldots,k$) is determined by the Laplacian spectrum of $H$, where $d_1,\ldots,d_n$ is the degree sequence of $H$. Using trace formulas for the Laplacian tensor, we obtain expressions for some coefficients of the Laplacian polynomial of a regular hypergraph. We give some spectral characterizations of odd-bipartite hypergraphs, and give a partial answer to a question posed by Shao et al (2014). We also give some spectral properties of power hypergraphs, and show that a conjecture posed by Hu et al (2013) holds under certain conditons.Jiang Zhou, Lizhu Sun, Wenzhe Wang, Changjiang Buhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p24Thu, 30 Oct 2014 00:00:00 +1100Avoiding 7-Circuits in 2-Factors of Cubic Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p25
Let $G$ be a cyclically $4$-edge-connected cubic graph with girth at least $7$ on $n$ vertices. We show that $G$ has a $2$-factor $F$ such that at least a linear amount of vertices is not in $7$-circuits of $F$. More precisely, there are at least $n/657$ vertices of $G$ that are not in $7$-circuits of $F$. If $G$ is cyclically $6$-edge-connected then the bound can be improved to $n/189$. As a corollary we obtain bounds on the oddness and on the length of the shortest travelling salesman tour in a cyclically $4$-edge-connected ($6$-edge-connected) cubic graph of girth at least $7$.<p style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </p>Robert Lukoťkahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p25Thu, 06 Nov 2014 00:00:00 +1100On $m$-Closed Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p26
A graph is closed when its vertices have a labeling by $[n]$ such that the binomial edge ideal $J_G$ has a quadratic <span>Gröbner </span>basis with respect to the lexicographic order induced by $x_1 > \ldots > x_n > y_1> \ldots > y_n$. In this paper, we generalize this notion and study the so called $m$-closed graphs. We find equivalent condition to $3$-closed property of an arbitrary tree $T$. Using it, we classify a class of $3$-closed trees. The primary decomposition of this class of graphs is also studied.Leila Sharifan, Masoumeh Javanbakhthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p26Thu, 06 Nov 2014 00:00:00 +1100Schubert Polynomials and $k$-Schur Functions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p27
The main purpose of this paper is to show that the multiplication of a Schubert polynomial of finite type $A$ by a Schur function, which we refer to as Schubert vs. Schur problem, can be understood combinatorially from the multiplication in the space of dual $k$-Schur functions. Using earlier work by the second author, we encode both problems by means of quasisymmetric functions. On the Schubert vs. Schur side, we study the poset given by the Bergeron-Sottile's $r$-Bruhat order, along with certain operators associated to this order. Then, we connect this poset with a graph on dual $k$-Schur functions given by studying the affine grassmannian order of Lam-Lapointe-Morse-Shimozono. Also, we define operators associated to the graph on dual $k$-Schur functions which are analogous to the ones given for the Schubert vs. Schur problem. This is the first step of our more general program of showing combinatorially the positivity of the multiplication of a dual $k$-Schur function by a Schur function.Carolina Benedetti, Nantel Bergeronhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p27Thu, 06 Nov 2014 00:00:00 +1100Integer Decomposition Property of Dilated Polytopes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p28
<p>An integral convex polytope $\mathcal{P} \subset \mathbb{R}^N$ possesses the integer decomposition property if, for any integer $k > 0$ and for any $\alpha \in k \mathcal{P} \cap \mathbb{Z}^{N}$, there exist $\alpha_{1}, \ldots, \alpha_k \in \mathcal{P} \cap \mathbb{Z}^{N}$ such that $\alpha = \alpha_{1} + \cdots + \alpha_k$. A fundamental question is to determine the integers $k > 0$ for which the dilated polytope $k\mathcal{P}$ possesses the integer decomposition property. In the present paper, combinatorial invariants related to the integer decomposition property of dilated polytopes will be proposed and studied.</p>David A. Cox, Christian Haase, Takayuki Hibi, Akihiro Higashitanihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p28Thu, 06 Nov 2014 00:00:00 +1100A 64-Dimensional Counterexample to Borsuk's Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p29
Bondarenko's 65-dimensional counterexample to Borsuk's conjecture contains a 64-dimensional counterexample. It is a two-distance set of 352 points.Thomas Jenrich, Andries E. Brouwerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p29Thu, 06 Nov 2014 00:00:00 +1100Shattering-Extremal Set Systems of VC Dimension at most 2
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p30
<p>We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a given set $S\subseteq [n]$ if $2^S=\{F~\cap~S ~:~F~\in~\mathcal{F}\}$. The Sauer inequality states that in general, a set system $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly $|\mathcal{F}|$ sets. In this paper we characterize shattering-extremal set systems of Vapnik-Chervonenkis dimension $2$ in terms of their inclusion graphs, and as a corollary we answer an open question about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension $2$.</p>Tamás Mészáros, Lajos Rónyaihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p30Thu, 06 Nov 2014 00:00:00 +1100Kauffman's Clock Lattice as a Graph of Perfect Matchings: a Formula for its Height
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p31
<p>We give an algorithmic computation for the height of Kauffman's clock lattice obtained from a knot diagram with two adjacent regions starred and without crossing information specified. We show that this lattice is more familiarly the graph of perfect matchings of a bipartite graph obtained from the knot diagram by overlaying the two dual Tait graphs of the knot diagram. Furthermore we prove structural properties of the bipartite graph in general. This setting also makes evident applications to Chebyshev or harmonic knots, whose related bipartite graph is the popular grid graph, and to discrete Morse functions.</p>Moshe Cohen, Mina Teicherhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p31Thu, 13 Nov 2014 00:00:00 +1100An Abstraction of Whitney's Broken Circuit Theorem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p32
We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type $\sum_{A\subseteq S} f(A)$ where $S$ is a finite set and $f$ is a mapping from the power set of $S$ into an abelian group. We give applications to the domination polynomial and the subgraph component polynomial of a graph, the chromatic polynomial of a hypergraph, the characteristic polynomial and Crapo's beta invariant of a matroid, and the principle of inclusion-exclusion. Thus, we discover several known and new results in a concise and unified way. As further applications of our main result, we derive a new generalization of the maximums-minimums identity and of a theorem due to Blass and Sagan on the Möbius function of a finite lattice, which generalizes Rota's crosscut theorem. For the classical Möbius function, both Euler's totient function and its Dirichlet inverse, and the reciprocal of the Riemann zeta function we obtain new expansions involving the greatest common divisor resp. least common multiple. We finally establish an even broader generalization of Whitney's broken circuit theorem in the context of convex geometries (antimatroids).Klaus Dohmen, Martin Trinkshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p32Thu, 13 Nov 2014 00:00:00 +1100A Combinatorial Approach to Ebert's Hat Game with Many Colors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p33
<p>This paper proves an optimal strategy for Ebert's hat game with three players and more than two hat colors. In general, for $n$ players and $k$ hat colours, we construct a strategy that is asymptotically optimal as $k\rightarrow \infty$. Computer calculation for particular values of $n$ and $k$ suggests that, as long as $n$ is linear with $k$, the strategy is asymptotically optimal. We conclude by comparing our strategy with the strategy of Lenstra and Seroussi and with the bound of Alon, and suggest our strategy is better when $2k \geq n \geq 7$.</p>Uthaipon Tantipongpipathttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p33Thu, 13 Nov 2014 00:00:00 +1100Bruhat Order on Partial Fixed Point Free Involutions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p34
The order complex of inclusion poset $PF_n$ of Borel orbit closures in skew-symmetric matrices is investigated. It is shown that $PF_n$ is an EL-shellable poset, and furthermore, its order complex triangulates a ball. The rank-generating function of $PF_n$ is computed and the resulting polynomial is contrasted with the Hasse-Weil zeta function of the variety of skew-symmetric matrices over finite fields.Mahir Bilen Can, Yonah Cherniavsky, Tim Twelbeckhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p34Thu, 13 Nov 2014 00:00:00 +1100Structure Coefficients of the Hecke Algebra of $(\mathcal{S}_{2n},\mathcal{B}_n)$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p35
<span style="color: #000000;"><span style="color: #000000;">The </span><span style="color: #000000;">Hecke</span><span style="color: #000000;"> algebra of the pair </span><span style="color: #008000;">$(\mathcal{S}_{2n},\mathcal{B}_n)$</span><span style="color: #000000;">, where </span><span style="color: #008000;">$\mathcal{B}_n$</span><span style="color: #000000;"> is the </span><span style="color: #000000;">hyperoctahedral</span><span style="color: #000000;"> subgroup of </span><span style="color: #008000;">$\mathcal{S}_{2n}$</span><span style="color: #000000;">, was introduced by James in 1961. It is a natural analogue of the center of the symmetric group algebra. In this paper, we give a </span><span style="color: #000000;">polynomiality</span><span style="color: #000000;"> property of its structure coefficients. Our main tool is a combinatorial algebra which projects onto the </span><span style="color: #000000;">Hecke</span><span style="color: #000000;"> algebra of </span><span style="color: #008000;">$(\mathcal{S}_{2n},\mathcal{B}_n)$</span><span style="color: #000000;"> for every </span><span style="color: #008000;">$n$</span><span style="color: #000000;">. To build it, by using partial bijections we introduce and study a new class of finite dimensional algebras.</span></span>Omar Touthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p35Thu, 13 Nov 2014 00:00:00 +1100On Floors and Ceilings of the $k$-Catalan Arrangement
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p36
<p>The set of dominant regions of the $k$-Catalan arrangement of a crystallographic root system $\Phi$ is a well-studied object enumerated by the Fuß-Catalan number $Cat^{(k)}(\Phi)$. It is natural to refine this enumeration by considering floors and ceilings of dominant regions. A conjecture of Armstrong states that counting dominant regions by their number of floors of a certain height gives the same distribution as counting dominant regions by their number of ceilings of the same height. We prove this conjecture using a bijection that provides even more refined enumerative information.</p>Marko Thielhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p36Thu, 13 Nov 2014 00:00:00 +1100Face-Width of Pfaffian Braces and Polyhex Graphs on Surfaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p37
<p><!--StartFragment-->A graph $G$ with a perfect matching is Pfaffian if it admits an orientation $D$ such that every central cycle $C$ (i.e. $C$ is of even size and $G-V(C)$ has a perfect matching) has an odd number of edges oriented in either direction of the cycle. It is known that the number of perfect matchings of a Pfaffian graph can be computed in polynomial time. In this paper, we show that every embedding of a Pfaffian brace (i.e. 2-extendable bipartite graph) on a surface with a positive genus has face-width at most 3. Further, we study Pfaffian cubic braces and obtain a characterization of Pfaffian polyhex graphs: a polyhex graph is Pfaffian if and only if it is either non-bipartite or isomorphic to the cube, or the Heawood graph, or the Cartesian product $C_k\times K_2$ for even integers $k\ge 6$.<br /><br /><br /></p>Dong Ye, Heping Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p37Thu, 20 Nov 2014 00:00:00 +1100The Number of Moves of the Largest Disc in Shortest Paths on Hanoi Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p38
<p>In contrast to the widespread interest in the <em>Frame-Stewart conjecture</em> (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in <em>Hanoi graphs</em> $H_p^n$ in a more general setting. Here $p$ stands for the number of pegs and $n$ for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of <em>largest disc moves</em> (LDMs). The patterns of these LDMs will be coded as binary strings of length $p-1$ assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all $n\geqslant p(p-2)$, of optimal paths where $p-1$ LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC.</p>Simon Aumann, Katharina A.M. Götz, Andreas M. Hinz, Ciril Petrhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p38Thu, 20 Nov 2014 00:00:00 +1100A Slight Improvement to the Colored Bárány's Theorem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p39
Suppose $d+1$ absolute continuous probability measures $m_0, \ldots, m_d$ on $\mathbb{R}^d$ are given. In this paper, we prove that there exists a point of $\mathbb{R}^d$ that belongs to the convex hull of $d+1$ points $v_0, \ldots, v_d$ with probability at least $\frac{2d}{(d+1)!(d+1)}$, where each point $v_i$ is sampled independently according to probability measure $m_i$.Zilin Jianghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p39Thu, 20 Nov 2014 00:00:00 +1100A Combinatorial Proof for Cayley's Identity
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p40
<p>In a recent paper, Caracciolo, Sokal and Sportiello presented, <em>inter alia</em>, an algebraic/combinatorial proof for Cayley's identity. The purpose of the present paper is to give a "purely combinatorial" proof for this identity; i.e., a proof involving only combinatorial arguments. Since these arguments eventually employ a generalization of Laplace’s Theorem, we present a "purely combinatorial" proof for this theorem, too. </p>Markus Fulmekhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p40Thu, 27 Nov 2014 00:00:00 +1100The Ramsey Numbers of Paths Versus Wheels: a Complete Solution
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p41
Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. We denote by $P_n$ the path on $n$ vertices and $W_m$ the wheel on $m+1$ vertices. Chen et al. and Zhang determined the values of $R(P_n,W_m)$ when $m\leq n+1$ and when $n+2\leq m\leq 2n$, respectively. In this paper we determine all the values of $R(P_n,W_m)$ for the left case $m\geq 2n+1$. Together with Chen et al.'s and Zhang's results, we give a complete solution to the problem of determining the Ramsey numbers of paths versus wheels.Binlong Li, Bo Ninghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p41Thu, 27 Nov 2014 00:00:00 +1100Ramsey Precompact Expansions of Homogeneous Directed Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p42
<pre>In 2005, Kechris, Pestov and Todor<span>č</span>evi<span>ć</span> provided a powerful tool to compute an invariant of topological groups known as the universal minimal flow, immediately leading to an explicit representation of this invariant in many concrete cases. More recently, the framework was generalized allowing for further applications, and the purpose of this paper is to apply these new methods in the context of homogeneous directed graphs.</pre><pre> In this paper, we show that the age of any homogeneous directed graph allows a <em>Ramsey precompact expansion</em>. Moreover, we verify the relative expansion properties and consequently describe the respective universal minimal flows.</pre>Jakub Jasiński, Claude Laflamme, Lionel Nguyen Van Thé, Robert Woodrowhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p42Thu, 27 Nov 2014 00:00:00 +1100Equidistributed Statistics on Matchings and Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p43
<p>We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization.</p><p>As a special case we obtain proofs of two conjectures of Claesson and Linusson.</p><p>Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.</p>Niklas Eriksen, Jonas Sjöstrandhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p43Thu, 27 Nov 2014 00:00:00 +1100Combinatorial Nullstellensatz Modulo Prime Powers and the Parity Argument
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p44
<pre>We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of their combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degree-constrained subgraphs modulo $2^d$ such as $2^d$-divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over $\mathbb{F}_2$ belong to the complexity class Polynomial Parity Argument (PPA).</pre>László Vargahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p44Thu, 27 Nov 2014 00:00:00 +1100On Groups all of whose Undirected Cayley Graphs of Bounded Valency are Integral
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p45
A finite group $G$ is called Cayley integral if all undirected Cayley graphs over $G$ are integral, i.e., all eigenvalues of the graphs are integers. The Cayley integral groups have been determined by Kloster and Sander in the abelian case, and by Abdollahi and Jazaeri, and independently by Ahmady, Bell and Mohar in the non-abelian case. In this paper we generalize this class of groups by introducing the class $\mathcal{G}_k$ of finite groups $G$ for which all graphs $\mathrm{Cay}(G,S)$ are integral if $|S| \le k$. It will be proved that $\mathcal{G}_k$ consists of the Cayley integral groups if $k \ge 6;$ and the classes $\mathcal{G}_4$ and $\mathcal{G}_5$ are equal, and consist of: (1) the Cayley integral groups, (2) the generalized dicyclic groups $Dic(E_{3^n} \times \mathbb{Z}_6),$ where $n \ge 1$.<p style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </p>István Estélyi, István Kovácshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p45Thu, 27 Nov 2014 00:00:00 +1100Enumeration of Tilings of Quartered Aztec Rectangles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p46
We generalize a theorem of W. Jockusch and J. Propp on quartered Aztec diamonds by enumerating the tilings of quartered Aztec rectangles. We use subgraph replacement method to transform the dual graph of a quartered Aztec rectangle to the dual graph of a quartered lozenge hexagon, and then use Lindstr<span><span>ö</span></span>m-Gessel-Viennot methodology to find the number of tilings of a quartered lozenge hexagon.Tri Laihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p46Thu, 27 Nov 2014 00:00:00 +1100The Game Chromatic Number of Dense Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p47
<p>Suppose that two players take turns coloring the vertices of a given graph G with k colors. In each move the current player colors a vertex such that neighboring vertices get different colors. The first player wins this game if and only if at the end, all vertices are colored. The <em>game chromatic number</em> χ<sub>g</sub>(G) is defined as the smallest k for which the first player has a winning strategy.</p><p>Recently, Bohman, Frieze and Sudakov [Random Structures and Algorithms 2008] analysed the game chromatic number of random graphs and obtained lower and upper bounds of the same order of magnitude. In this paper we improve existing results and show that with high probability, the game chromatic number χ<sub>g</sub>(G<sub>n,p</sub>) of dense random graphs with p ≥ e<sup>-o(log n)</sup> is asymptotically twice as large as the ordinary chromatic number χ(G<sub>n,p</sub>).</p>Ralph Keusch, Angelika Stegerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p47Wed, 26 Nov 2014 00:00:00 +1100A Superlocal Version of Reed's Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p48
<p><br />Reed's well-known $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisfies $\chi \leq \lceil \frac 12(\Delta+1+\omega)\rceil$. The second author formulated a local strengthening of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further.</p>Katherine Edwards, Andrew D. Kinghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p48Thu, 04 Dec 2014 00:00:00 +1100Bell Numbers Modulo a Prime Number, Traces and Trinomials
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p49
<p>Given a prime number $p$, we deduce from a formula of Barsky and Benzaghou and from a result of Coulter and Henderson on trinomials over finite fields, a simple necessary and sufficient condition $\beta(n) =k\beta(0)$ in $\mathbb{F}_{p^p}$ in order to resolve the congruence $B(n) \equiv k \pmod{p}$, where $B(n)$ is the $n$-th Bell number, and $k$ is any fixed integer. Several applications of the formula and of the condition are included, in particular we give equivalent forms of the conjecture of Kurepa that $B(p-1)$ is $\neq 1$ modulo $p$.</p>Luis H. Gallardo, Olivier Rahavandrainyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p49Thu, 04 Dec 2014 00:00:00 +1100The Degree-Diameter Problem for Circulant Graphs of Degree 8 and 9
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p50
This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establish the results for degree 6 and 7 has been extended successfully to degree 8 and 9. Candidate graphs are defined as functions of the diameter for both degree 8 and degree 9. They are proven to be extremal for small diameters. They establish new lower bounds for all greater diameters, and are conjectured to be extremal. The existence of the degree 8 solution is proved for all diameters. Finally some conjectures are made about solutions for circulant graphs of higher degree.Robert R. Lewishttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p50Thu, 04 Dec 2014 00:00:00 +1100Growth Rates of Geometric Grid Classes of Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p51
<p align="LEFT">Geometric grid classes of permutations have proven to be key in investigations of classical permutation pattern classes. By considering the representation of gridded permutations as words in a trace monoid, we prove that every geometric grid class has a growth rate which is given by the square of the largest root of the matching polynomial of a related graph. As a consequence, we characterise the set of growth rates of geometric grid classes in terms of the spectral radii of trees, explore the influence of “cycle parity” on the growth rate, compare the growth rates of geometric grid classes against those of the corresponding monotone grid classes, and present new results concerning the effect of edge subdivision on the largest root of the matching polynomial.</p>David Bevanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p51Thu, 04 Dec 2014 00:00:00 +1100Infinite Graphs with Finite 2-Distinguishing Cost
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p52
<p>A graph $G$ is said to be 2-distinguishable if there is a labeling of the vertices with two labels such that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of $G$ the cost of 2-distinguishing $G$.</p><p>We show that the connected, locally finite, infinite graphs with finite 2-distinguishing cost are exactly the graphs with countable automorphism group. Further we show that in such graphs the cost is less than three times the size of a smallest determining set. We also another, sharper bound on the 2-distinguishing cost, in particular for graphs of linear growth.</p>Debra Boutin, Wilfried Imrichhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p52Thu, 11 Dec 2014 00:00:00 +1100On Bipartite $Q$-Polynomial Distance-Regular Graphs with $c_2 \le 2$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p53
<p>Let $\Gamma$ denote a bipartite $Q$-polynomial distance-regular graph with diameter $D \ge 4$, valency $k \ge 3$ and intersection number $c_2 \le 2$. We show that $\Gamma$ is either the $D$-dimensional hypercube, or the antipodal quotient of the $2D$-dimensional hypercube, or $D=5$.</p>Stefko Miklavic, Safet Penjichttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p53Thu, 11 Dec 2014 00:00:00 +1100