The Electronic Journal of Combinatorics
http://www.combinatorics.org/ojs/index.php/eljc
<p>The Electronic Journal of Combinatorics (E-JC) is a fully-refereed electronic journal with <em>very high standards,</em> publishing papers of substantial content and interest in all branches of discrete mathematics, including combinatorics, graph theory, and algorithms for combinatorial problems. The journal is <em>completely free</em> for both authors and readers. Authors retain the copyright of their articles. Articles published in E-JC are reviewed on MathSciNet and ZBMath, and are indexed by Web of Science. The latest papers are always available by clicking on the tab marked "Current" near the top of the page. You can also locate papers using the search facility on the right hand side of this page.</p><p>E-JC was founded in 1994 by Herbert S. Wilf and Neil Calkin, making it one of the oldest electronic journals.</p>en-US<p>The copyright of published papers remains with the authors. We only require your agreement that we publish it, as described in the following publication release agreement:</p><ol><li>This is an agreement between the Electronic Journal of Combinatorics (the "Journal"), and the copyright owner (the "Owner") of a work (the "Work") to be published in the Journal.</li><li>The Owner warrants that s/he has the full power and authority to enter into this Agreement and to grant the rights granted in this Agreement.</li><li>The Owner hereby grants to the Journal a worldwide, irrevocable, royalty free license to publish or distribute the Work, to enter into arrangements with others to publish or distribute the Work, and to archive the Work.</li><li>The Owner agrees that further publication of the Work, with the same or substantially the same content as appears in the Journal, will include an acknowledgement of prior publication in the Journal.</li></ol>beck@math.sfsu.edu (Matthias Beck)bdm@cs.anu.edu.au (Brendan McKay)Mon, 11 Jan 2016 13:05:28 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60Bi-Cohen-Macaulay graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p1
In this paper we consider bi-Cohen-Macaulay graphs, and give a complete classification of such graphs in the case they are bipartite or chordal. General bi-Cohen-Macaulay graphs are classified up to separation. The inseparable bi-Cohen-Macaulay graphs are determined. We establish a bijection between the set of all trees and the set of inseparable bi-Cohen-Macaulay graphs.<br /><br />Jürgen Herzog, Ahad Rahimihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p1Mon, 11 Jan 2016 00:00:00 +1100On Periodicity of Generalized Pseudostandard Words
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p2
<p>Generalized pseudostandard words were introduced by de Luca and De Luca in 2006. In comparison to the palindromic and pseudopalindromic closure, only little is known about the generalized pseudopalindromic closure and the associated generalized pseudostandard words. In this paper we provide a necessary and sufficient condition for their periodicity over a binary and a ternary alphabet. More precisely, we describe how the directive bi-sequence of a generalized pseudostandard word has to look like in order to correspond to a periodic word. We state moreover a conjecture concerning a necessary and sufficient condition for periodicity over any alphabet.</p>Josef Florian, L'ubomíra Dvořákováhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p2Mon, 11 Jan 2016 00:00:00 +1100Posets of Finite Functions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p3
The symmetric group $ S(n) $ is partially ordered by Bruhat order. This order is extended by L. Renner to the set of partial injective functions of $ \{ 1, 2, \ldots, n \} $ (see, <em>Linear Algebraic Monoids</em>, Springer, 2005). This poset is investigated by M. Fortin in his paper <em>The MacNeille Completion of the Poset of Partial Injective Functions</em> [Electron. J. Combin., 15, R62, 2008]. In this paper we show that Renner order can be also defined for sets of all functions, partial functions, injective and partial injective functions from $ \{ 1, 2, \ldots, n \} $ to $ \{ 1, 2, \ldots, m \} $. Next, we generalize Fortin's results on these posets, and also, using simple facts and methods of linear algebra, we give simpler and shorter proofs of some fundamental Fortin's results. We first show that these four posets can be order embedded in the set of $ n \times m $-matrices with non-negative integer entries and with the natural componentwise order. Second, matrix representations of the Dedekind-MacNeille completions of our posets are given. Third, we find join- and meet-irreducible elements for every finite sublattice of the lattice of all $ n \times m $-matrices with integer entries. In particular, we obtain join- and meet-irreducible elements of these Dedekind-MacNeille completions. Hence and by general results concerning Dedekind-MacNeille completions, join- and meet-irreducible elements of our four posets of functions are also found. Moreover, subposets induced by these irreducible elements are precisely described.Konrad Piórohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p3Mon, 11 Jan 2016 00:00:00 +1100Simultaneous Core Partitions: Parameterizations and Sums
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p4
<p>Fix coprime $s,t\ge1$. We re-prove, without Ehrhart reciprocity, a conjecture of Armstrong (recently verified by Johnson) that the finitely many simultaneous $(s,t)$-cores have average size $\frac{1}{24}(s-1)(t-1)(s+t+1)$, and that the subset of self-conjugate cores has the same average (first shown by Chen-Huang-Wang). We similarly prove a recent conjecture of Fayers that the average weighted by an inverse stabilizer - giving the "expected size of the $t$-core of a random $s$-core" - is $\frac{1}{24}(s-1)(t^2-1)$. We also prove Fayers' conjecture that the analogous self-conjugate average is the same if $t$ is odd, but instead $\frac{1}{24}(s-1)(t^2+2)$ if $t$ is even. In principle, our explicit methods - or implicit variants thereof - extend to averages of arbitrary powers.</p><p>The main new observation is that the stabilizers appearing in Fayers' conjectures have simple formulas in Johnson's $z$-coordinates parameterization of $(s,t)$-cores.</p><p>We also observe that the $z$-coordinates extend to parameterize general $t$-cores. As an example application with $t := s+d$, we count the number of $(s,s+d,s+2d)$-cores for coprime $s,d\ge1$, verifying a recent conjecture of Amdeberhan and Leven.</p><div id="spoon-plugin-kncgbdglledmjmpnikebkagnchfdehbm-2" style="display: none;"> </div>Victor Y. Wanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p4Mon, 11 Jan 2016 00:00:00 +1100An Extension of MacMahon's Equidistribution Theorem to Ordered Multiset Partitions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p5
A classical result of MacMahon states that inversion number and major index have the same distribution over permutations of a given multiset. In this work, we prove a strengthening of MacMahon's theorem originally conjectured by Haglund. Our result can be seen as an equidistribution theorem over the ordered partitions of a multiset into sets, which we call ordered multiset partitions. Our proof is bijective and involves a new generalization of Carlitz's insertion method. This generalization leads to a new extension of Macdonald polynomials for hook shapes. We use our main theorem to show that these polynomials are symmetric and we give their Schur expansion.Andrew Timothy Wilsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p5Mon, 11 Jan 2016 00:00:00 +1100Low Degree Nullstellensatz Certificates for 3-Colorability
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p6
In a seminal paper, De Loera et. al introduce the algorithm NulLA (Nullstellensatz Linear Algebra) and use it to measure the difficulty of determining if a graph is not 3-colorable. The crux of this relies on a correspondence between 3-colorings of a graph and solutions to a certain system of polynomial equations over a field $\mathbb{k}$. In this article, we give a new direct combinatorial characterization of graphs that can be determined to be non-3-colorable in the first iteration of this algorithm when $\mathbb{k}=GF(2)$. This greatly simplifies the work of De Loera et. al, as we express the combinatorial characterization directly in terms of the graphs themselves without introducing superfluous directed graphs. Furthermore, for all graphs on at most $12$ vertices, we determine at which iteration NulLA detects a graph is not 3-colorable when $\mathbb{k}=GF(2)$.Bo Li, Benjamin Lowenstein, Mohamed Omarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p6Mon, 11 Jan 2016 00:00:00 +1100Expansions of a Chord Diagram and Alternating Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p7
A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ with $n$ chords is called an $n$-crossing if all chords of $E$ are mutually crossing. A chord diagram $E$ is called nonintersecting if $E$ contains no $2$-crossing. For a chord diagram $E$ having a $2$-crossing $S = \{ x_1 x_3, x_2 x_4 \}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1 = (E \setminus S) \cup \{ x_2 x_3, x_4 x_1 \}$ or $E_2 = (E \setminus S) \cup \{ x_1 x_2, x_3 x_4 \}$. It is shown that there is a one-to-one correspondence between the multiset of all nonintersecting chord diagrams generated from an $n$-crossing with a finite sequence of expansions and the set of alternating permutations of order $n+1$.Tomoki Nakamigawahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p7Mon, 11 Jan 2016 00:00:00 +1100Combinatorial Proofs of Addition Formulas
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p8
<p><!--StartFragment-->In this paper we give a combinatorial proof of an addition formula for weighted partial Motzkin paths. The addition formula allows us to determine the $LDU$ decomposition of a Hankel matrix of the polynomial sequence defined by weighted partial Motzkin paths. As a direct consequence, we get the determinant of the Hankel matrix of certain combinatorial sequences. In addition, we obtain an addition formula for weighted large Schröder paths.<!--EndFragment--></p>Xiang-Ke Chang, Xing-Biao Hu, Hongchuan Lei, Yeong-Nan Yehhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p8Mon, 11 Jan 2016 00:00:00 +1100Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p9
We prove that a $k$-tree can be viewed as a subgraph of a special type of $(k+1)$-tree that corresponds to a stacked polytope and that these "stacked'' $(k+1)$-trees admit representations by orthogonal spheres in $\mathbb{R}^{k+1}$. As a result, we derive lower bounds for Colin de Verdière's $\mu$ of complements of partial $k$-trees and prove that $\mu(G) + \mu(\overline{G}) \geq |G| - 2$ for all chordal $G$.Lon Mitchell, Lynne Yengulalphttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p9Fri, 22 Jan 2016 00:00:00 +1100Finite Edge-Transitive Oriented Graphs of Valency Four: a Global Approach
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p10
We develop a new framework for analysing finite connected, oriented graphs of valency four, which admit a vertex-transitive and edge-transitive group of automorphisms preserving the edge orientation. We identify a sub-family of `basic' graphs such that each graph of this type is a normal cover of at least one basic graph. The basic graphs either admit an edge-transitive group of automorphisms that is quasiprimitive or biquasiprimitive on vertices, or admit an (oriented or unoriented) cycle as a normal quotient. We anticipate that each of these additional properties will facilitate effective further analysis, and we demonstrate that this is so for the quasiprimitive basic graphs. Here we obtain strong restrictions on the group involved, and construct several infinite families of such graphs which, to our knowledge, are different from any recorded in the literature so far. Several open problems are posed in the paper.Jehan A. Al-bar, Ahmad N. Al-kenani, Najat M. Muthana, Cheryl E. Praeger, Pablo Spigahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p10Fri, 22 Jan 2016 00:00:00 +1100A Quantitative Study of Pure Parallel Processes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p11
In this paper, we study the interleaving <em></em><em>–</em> or pure merge <em></em><em></em><em>–</em> operator that most often characterizes parallelism in concurrency theory. This operator is a principal cause of the so-called combinatorial explosion that makes the analysis of process behaviours e.g. by model-checking, very hard <em></em><em>–</em><em></em> at least from the point of view of computational complexity. The originality of our approach is to study this combinatorial explosion phenomenon on average, relying on advanced analytic combinatorics techniques. We study various measures that contribute to a better understanding of the process behaviours represented as plane rooted trees: the number of runs (corresponding to the width of the trees), the expected total size of the trees as well as their overall shape. Two practical outcomes of our quantitative study are also presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random sampling of concurrent runs. These provide interesting responses to the combinatorial explosion problem.O. Bodini, A. Genitrini, F. Peschanskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p11Fri, 22 Jan 2016 00:00:00 +1100The Phase Transition in Site Percolation on Pseudo-Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p12
We establish the existence of the phase transition in site percolation on pseudo-random $d$-regular graphs. Let $G=(V,E)$ be an $(n,d,\lambda)$-graph, that is, a $d$-regular graph on $n$ vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most $\lambda$ in their absolute values. Form a random subset $R$ of $V$ by putting every vertex $v\in V$ into $R$ independently with probability $p$. Then for any small enough constant $\epsilon>0$, if $p=\frac{1-\epsilon}{d}$, then with high probability all connected components of the subgraph of $G$ induced by $R$ are of size at most logarithmic in $n$, while for $p=\frac{1+\epsilon}{d}$, if the eigenvalue ratio $\lambda/d$ is small enough as a function of $\epsilon$, then typically $R$ contains a connected component of size at least $\frac{\epsilon n}{d}$ and a path of length proportional to $\frac{\epsilon^2n}{d}$.Michael Krivelevichhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p12Fri, 22 Jan 2016 00:00:00 +1100A Combinatorial Proof of a Relationship Between Maximal $(2k-1,2k+1)$-Cores and $(2k-1,2k,2k+1)$-Cores
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p13
Integer partitions which are simultaneously $t$-cores for distinct values of $t$ have attracted significant interest in recent years. When $s$ and $t$ are relatively prime, Olsson and Stanton have determined the size of the maximal $(s,t)$-core $\kappa_{s,t}$. When $k\geq 2$, a conjecture of Amdeberhan on the maximal $(2k-1,2k,2k+1)$-core $\kappa_{2k-1,2k,2k+1}$ has also recently been verified by numerous authors.<br /><br />In this work, we analyze the relationship between maximal $(2k-1,2k+1)$-cores and maximal $(2k-1,2k,2k+1)$-cores. In previous work, the first author noted that, for all $k\geq 1,$<br />$$<br />\vert \, \kappa_{2k-1,2k+1}\, \vert = 4\vert \, \kappa_{2k-1,2k,2k+1}\, \vert<br />$$<br />and requested a combinatorial interpretation of this unexpected identity. Here, using the theory of abaci, partition dissection, and elementary results relating triangular numbers and squares, we provide such a combinatorial proof.Rishi Nath, James A. Sellershttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p13Fri, 22 Jan 2016 00:00:00 +1100The Chromatic Number of a Signed Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p14
<p>In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $\phi\colon V(G)\to \mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $\phi(u)$ is different from the colour $\sigma(uv)\phi(v)$, where is $\sigma(uv)$ is the sign of the edge $uv$. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks' theorem to signed graphs.</p>Edita Máčajová, André Raspaud, Martin Škovierahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p14Fri, 22 Jan 2016 00:00:00 +1100Chromatic Bases for Symmetric Functions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p15
In this note we obtain numerous new bases for the algebra of symmetric functions whose generators are chromatic symmetric functions. More precisely, if $\{ G_ k \} _{k\geq 1}$ is a set of connected graphs such that $G_k$ has $k$ vertices for each $k$, then the set of all chromatic symmetric functions $\{ X_{G_ k} \} _{k\geq 1}$ generates the algebra of symmetric functions. We also obtain explicit expressions for the generators arising from complete graphs, star graphs, path graphs and cycle graphs.Soojin Cho, Stephanie van Willigenburghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p15Fri, 22 Jan 2016 00:00:00 +1100A Note on Perfect Matchings in Uniform Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p16
We determine the <em>exact</em> minimum $\ell$-degree threshold for perfect matchings in $k$-uniform hypergraphs when the corresponding threshold for perfect fractional matchings is significantly less than $\frac{1}{2}\left( \begin{array}{c} n \\ k- \ell\end{array}\right)$. This extends our previous results that determine the minimum $\ell$-degree thresholds for perfect matchings in $k$-uniform hypergraphs for all $\ell\ge k/2$ and provides two new (exact) thresholds: $(k,\ell)=(5,2)$ and $(7,3)$.<br /><br /><br />Andrew Treglown, Yi Zhaohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p16Fri, 22 Jan 2016 00:00:00 +1100A Note on Maxima in Random Walks
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p17
<p>We give a combinatorial proof that a random walk attains a unique maximum with probability at least $1/2$. For closed random walks with uniform step size, we recover Dwass's count of the number of length $\ell$ walks attaining the maximum exactly $k$ times. We also show that the probability that there is both a unique maximum and a unique minimum is asymptotically equal to $\frac14$ and that the probability that a Dyck word has a unique minimum is asymptotically $\frac12$.</p>Joseph Helfer, Daniel T. Wisehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p17Fri, 22 Jan 2016 00:00:00 +1100Avoiding Letter Patterns in Ternary Square-Free Words
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p18
We consider special patterns of lengths 5 and 6 in a ternary alphabet. We show that some of them are unavoidable in square-free words and prove avoidability of the other ones. Proving the main results, we use Fibonacci words as codes of ternary words in some natural coding system and show that they can be decoded to square-free words avoiding the required patterns. Furthermore, we estimate the minimal local (critical) exponents of square-free words with such avoidance properties.Elena A. Petrovahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p18Fri, 05 Feb 2016 00:00:00 +1100Doubled Patterns are 3-Avoidable
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p19
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$. A pattern is said to be doubled if no variable occurs only once. Doubled patterns with at most 3 variables and doubled patterns with at least 6 variables are $3$-avoidable. We show that doubled patterns with 4 and 5 variables are also $3$-avoidable.<br /><br />Pascal Ochemhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p19Fri, 05 Feb 2016 00:00:00 +1100A Note on the $\gamma$-Coefficients of the Tree Eulerian Polynomial
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p20
<p>We consider the generating polynomial of the number of rooted trees on the set $\{1,2,\dots,n\}$ counted by the number of descending edges (a parent with a greater label than a child). This polynomial is an extension of the descent generating polynomial of the set of permutations of a totally ordered $n$-set, known as the Eulerian polynomial. We show how this extension shares some of the properties of the classical one. A classical product formula shows that this polynomial factors completely over the integers. From this product formula it can be concluded that this polynomial has positive coefficients in the $\gamma$-basis and we show that a formula for these coefficients can also be derived. We discuss various combinatorial interpretations of these coefficients in terms of leaf-labeled binary trees and in terms of the Stirling permutations introduced by Gessel and Stanley. These interpretations are derived from previous results of Liu, Dotsenko-Khoroshkin, Bershtein-Dotsenko-Khoroshkin, González D'León-Wachs and Gonzláez D'León related to the free multibracketed Lie algebra and the poset of weighted partitions.</p>Rafael S. González D'Leónhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p20Fri, 05 Feb 2016 00:00:00 +1100Another Proof of the Harer-Zagier Formula
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p21
For a regular $2n$-gon there are $(2n-1)!!$ ways to match and glue the $2n$ sides. The Harer-Zagier bivariate generating function enumerates the gluings by $n$ and the genus $g$ of the attendant surface and leads to a recurrence equation for the counts of gluings with parameters $n$ and $g$. This formula was originally obtained using multidimensional Gaussian integrals. Soon after, Jackson and later Zagier found alternative proofs using symmetric group characters. In this note we give a different, characters-based, proof. Its core is computing and marginally inverting the Fourier transform of the underlying probability measure on $S_{2n}$. A key ingredient is the Murnaghan-Nakayama rule for the characters associated with one-hook Young diagrams.Boris Pittelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p21Fri, 05 Feb 2016 00:00:00 +1100A New Lower Bound for the Towers of Hanoi Problem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p22
<p>More than a century after its proposal, the Towers of Hanoi puzzle with 4 pegs was solved by Thierry Bousch in a breakthrough paper in 2014. The general problem with $p$ pegs is still open, with the best lower bound on the minimum number of moves due to Chen and Shen. We use some of Bousch's new ideas to obtain an asymptotic improvement on this bound for all $p \geq 5$.</p>Codruƫ Grosuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p22Fri, 05 Feb 2016 00:00:00 +1100An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p23
<p>We present a simple, explicit orthogonal basis of eigenvectors for the Johnson and Kneser graphs, based on Young's orthogonal representation of the symmetric group. Our basis can also be viewed as an orthogonal basis for the vector space of all functions over a slice of the Boolean hypercube (a set of the form $\{(x_1,\ldots,x_n) \in \{0,1\}^n : \sum_i x_i = k\}$), which refines the eigenspaces of the Johnson association scheme; our basis is orthogonal with respect to <em>any</em> exchangeable measure. More concretely, our basis is an orthogonal basis for all multilinear polynomials $\mathbb{R}^n \to \mathbb{R}$ which are annihilated by the differential operator $\sum_i \partial/\partial x_i$. As an application of the last point of view, we show how to lift low-degree functions from a slice to the entire Boolean hypercube while maintaining properties such as expectation, variance and $L^2$-norm.</p><p><br />As an application of our basis, we streamline Wimmer's proof of Friedgut's theorem for the slice. Friedgut's theorem, a fundamental result in the analysis of Boolean functions, states that a Boolean function on the Boolean hypercube with low total influence can be approximated by a Boolean junta (a function depending on a small number of coordinates). Wimmer generalized this result to slices of the Boolean hypercube, working mostly over the symmetric group, and utilizing properties of Young's orthogonal representation. Using our basis, we show how the entire argument can be carried out directly on the slice.</p>Yuval Filmushttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p23Fri, 05 Feb 2016 00:00:00 +1100Generalizing the Classic Greedy and Necklace Constructions of de Bruijn Sequences and Universal Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p24
<p>We present a class of languages that have an interesting property: For each language $\mathbf{L}$ in the class, both the classic greedy algorithm and the classic Lyndon word (or necklace) concatenation algorithm provide the lexicographically smallest universal cycle for $\mathbf{L}$. The languages consist of length $n$ strings over $\{1,2,\ldots ,k\}$ that are closed under rotation with their subset of necklaces also being closed under replacing any suffix of length $i$ by $i$ copies of $k$. Examples include all strings (in which case universal cycles are commonly known as de Bruijn sequences), strings that sum to at least $s$, strings with at most $d$ cyclic descents for a fixed $d>0$, strings with at most $d$ cyclic decrements for a fixed $d>0$, and strings avoiding a given period. Our class is also closed under both union and intersection, and our results generalize results of several previous papers.</p>Joe Sawada, Aaron Williams, Dennis Wonghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p24Fri, 05 Feb 2016 00:00:00 +1100Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p25
<p>We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those $n$ for which an automatic sequence $\bf x$ has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length $n$ is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length $n$ of a $k$-automatic sequence is not $k$-synchronized.<br /><br /></p>Luke Schaeffer, Jeffrey Shallithttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p25Fri, 05 Feb 2016 00:00:00 +1100Determining a Binary Matroid from its Small Circuits
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p26
It is well known that a rank-$r$ matroid $M$ is uniquely determined by its circuits of size at most $r$. This paper proves that if $M$ is binary and $r\ge 3$, then $M$ is uniquely determined by its circuits of size at most $r-1$ unless $M$ is a binary spike or a special restriction thereof. In the exceptional cases, $M$ is determined up to isomorphism.James Oxley, Charles Semple, Geoff Whittlehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p26Fri, 05 Feb 2016 00:00:00 +1100A Curved Brunn Minkowski Inequality for the Symmetric Group
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p27
<p>In this paper, we construct an injection $A \times B \rightarrow M \times M$ from the product of any two nonempty subsets of the symmetric group into the square of their midpoint set, where the metric is that corresponding to the conjugacy class of transpositions. If $A$ and $B$ are disjoint, our construction allows to inject two copies of $A \times B$ into $M \times M$. These injections imply a positively curved Brunn-Minkowski inequality for the symmetric group analogous to that obtained by Ollivier and Villani for the hypercube. However, while Ollivier and Villani's inequality is optimal, we believe that the curvature term in our inequality can be improved. We identify a hypothetical concentration inequality in the symmetric group and prove that it yields an optimally curved Brunn-Minkowski inequality.<br /><br /></p>Weerachai Neeranartvong, Jonathan Novak, Nat Sothanaphanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p27Fri, 05 Feb 2016 00:00:00 +1100