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)Mon, 31 Mar 2014 00:00:00 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60Counting Words with Laguerre Series
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p1
We develop a method for counting words subject to various restrictions by finding a combinatorial interpretation for a product of weighted sums of Laguerre polynomials with parameter $\alpha = -1$. We describe how such a series can be computed by finding an appropriate ordinary generating function and applying a certain transformation. We use this technique to find the generating function for the number of $k$-ary words avoiding any vincular pattern that has only ones, as well as words cyclically avoiding vincular patterns with only ones whose runs of ones between dashes are all of equal length.Jair Taylorhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p1Tue, 01 Apr 2014 00:00:00 +1100Revstack Sort, Zigzag Patterns, Descent Polynomials of $t$-revstack Sortable Permutations, and Steingrímsson's Sorting Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p2
In this paper we examine the sorting operator $\mathcal{T}(LnR)=\mathcal{T}(R)\mathcal{T}(L)n$. Applying this operator to a permutation is equivalent to passing the permutation reversed through a stack. We prove theorems that characterise $t$-revstack sortability in terms of patterns in a permutation that we call <em>zigzag</em> patterns. Using these theorems we characterise those permutations of length $n$ which are sorted by $t$ applications of $\mathcal{T}$ for $t=0,1,2,n-3,n-2,n-1$. We derive expressions for the descent polynomials of these six classes of permutations and use this information to prove Steingrímsson's sorting conjecture for those six values of $t$. Symmetry and unimodality of the descent polynomials for general $t$-revstack sortable permutations is also proven and three conjectures are given.Mark Dukeshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p2Tue, 01 Apr 2014 00:00:00 +1100Some New Characterizations of Graph Colorability and of Blocking Sets of Projective Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p3
Let $G=(V,E)$ be a graph and $q$ be an odd prime power. We prove that $G$ possess a proper vertex coloring with $q$ colors if and only if there exists an odd vertex labeling $x\in F_q^V$ of $G$. Here, $x$ is called odd if there is an odd number of partitions $\pi=\{V_1,V_2,\dotsc,V_t\}$ of $V$ whose blocks $V_i$ are \(G\)-bipartite and \(x\)-balanced, i.e., such that $G|_{V_i}$ is connected and bipartite, and $\sum_{v\in V_i}x_v=0$. Other new characterizations concern edge colorability of graphs and, on a more general level, blocking sets of projective spaces. Some of these characterizations are formulated in terms of a new switching game.Uwe Schauzhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p3Tue, 01 Apr 2014 00:00:00 +1100Counting Symmetric Nilpotent Matrices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p4
<pre>We determine the number of nilpotent matrices of order <span>$n$</span> over <span>$\mathbb{F}_q$ </span>that are self-adjoint for a given nondegenerate symmetric bilinear form, and in particular find the number of symmetric nilpotent matrices.</pre>Andries E. Brouwer, Rod Gow, John Sheekeyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p4Tue, 01 Apr 2014 00:00:00 +1100Degree Ramsey Numbers of Closed Blowups of Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/2526
<p>The degree Ramsey number of a graph $G$, denoted $R_\Delta(G;s)$, is $\min\{\Delta(H)\colon\, H\stackrel{s}{\to} G\}$, where $H\stackrel{s}{\to} G$ means that every $s$-edge-coloring of $H$ contains a monochromatic copy of $G$. The closed $k$-blowup of a graph is obtained by replacing every vertex with a clique of size $k$ and every edge with a complete bipartite graph where both partite sets have size $k$. We prove that there is a function $f$ such that $R_\Delta(G;s) \le f(\Delta(G), s)$ when $G$ is a closed blowup of a tree.</p>Paul Horn, Kevin G. Milans, Vojtěch Rödlhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/2526Wed, 16 Apr 2014 00:12:33 +1000Totally Symmetric Functions are Reconstructible from Identification Minors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p6
We formulate a reconstruction problem for functions of several arguments: Is a function of several arguments uniquely determined, up to equivalence, by its identification minors? We establish some positive and negative results on this reconstruction problem. In particular, we show that totally symmetric functions (of sufficiently large arity) are reconstructible.Erkko Lehtonenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p6Wed, 16 Apr 2014 00:00:00 +1000Application of Entropy Compression in Pattern Avoidance
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7
<p>In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$ such that $f= h(p)$ where $h: \Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words'", that is, every pattern with $k$ variables of length at least $2^k$ (resp. $3\times2^{k-1}$) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by Cassaigne in his thesis in 1994. This improves previous bounds due to Bell and Goh, and Rampersad.</p>Pascal Ochem, Alexandre Pinlouhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7Wed, 16 Apr 2014 00:00:00 +1000Packing Tree Factors in Random and Pseudo-random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p8
For a fixed graph $H$ with $t$ vertices, an $H$-factor of a graph $G$ with $n$ vertices, where $t$ divides $n$, is a collection of vertex disjoint (not necessarily induced) copies of $H$ in $G$ covering all vertices of $G$. We prove that for a fixed tree $T$ on $t$ vertices and $\epsilon>0$, the random graph $G_{n,p}$, with $n$ a multiple of $t$, with high probability contains a family of edge-disjoint $T$-factors covering all but an $\epsilon$-fraction of its edges, as long as $\epsilon^4 n p \gg \log^2 n$. Assuming stronger divisibility conditions, the edge probability can be taken down to $p>\frac{C\log n}{n}$. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.Deepak Bal, Alan Frieze, Michael Krivelevich, Po-Shen Lohhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p8Wed, 16 Apr 2014 00:00:00 +1000A Simple Formula for the Series of Constellations and Quasi-constellations with Boundaries
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p9
We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di Francesco and Guitter combined with a process (reminiscent of a construction of Pitman) of aggregating connected components of a forest into a single tree. The formula naturally extends to $p$-constellations and quasi-$p$-constellations with boundaries (the case $p=2$ corresponding to bipartite maps).Gwendal Collet, Éric Fusyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p9Wed, 16 Apr 2014 00:00:00 +1000Signed Excedance Enumeration in the Hyperoctahedral group
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p10
<span style="font-family: Arial,Helvetica;">Several signed excedance-like statistics have nice formulae or generating functions when summed over the symmetric group and over its subset of derangements. We give counterparts of some of these results when we sum over the hyperoctahedral group and its subset of derangements. Our results motivate us to define and derive attractive bivariate formulae which generalise some of these results for the symmetric group.<br /><br /><br /><br /></span>Sivaramakrishnan Sivasubramanianhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p10Wed, 16 Apr 2014 00:00:00 +1000On the Möbius Function of Permutations with One Descent
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p11
The set of all permutations, ordered by pattern containment, is a poset. We give a formula for the M<span>ö</span>bius function of intervals $[1,\pi]$ in this poset, for any permutation $\pi$ with at most one descent. We compute the M<span>ö</span>bius function as a function of the number and positions of pairs of consecutive letters in $\pi$ that are consecutive in value. As a result of this we show that the M<span>ö</span>bius function is unbounded on the poset of all permutations. We show that the M<span>ö</span>bius function is zero on any interval $[1,\pi]$ where $\pi$ has a triple of consecutive letters whose values are consecutive and monotone. We also conjecture values of the M<span>ö</span>bius function on some other intervals of permutations with at most one descent.Jason P. Smithhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p11Wed, 16 Apr 2014 00:00:00 +1000Progress on Dirac's Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p12
<p>In 1951, Gabriel Dirac conjectured that every non-collinear set $P$ of $n$ points in the plane contains a point incident to at least $\frac{n}{2}-c$ of the lines determined by $P$, for some constant $c$. The following weakened conjecture was proved by Beck and by Szemerédi and Trotter: every non-collinear set $P$ of $n$ points in the plane contains a point in at least $\frac{n}{c'}$ lines determined by $P$, for some constant $c'$. We prove this result with $c'= 37$. We also give the best known constant for Beck's Theorem, proving that every set of $n$ points with at most $\ell$ collinear determines at least $\frac{1}{98} n(n-\ell)$ lines.</p>Michael S. Payne, David R. Woodhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p12Wed, 16 Apr 2014 00:00:00 +1000