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><p>ISSN: <span lang="EN">1077-8926</span></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>mattbeck@sfsu.edu (Matt Beck)bdm@cs.anu.edu.au (Brendan McKay)Fri, 14 Jul 2017 00:00:00 +1000OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60On the Nonexistence of $k$-Reptile Simplices in $\mathbb R^3$ and $\mathbb R^4$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p1
A $d$-dimensional simplex $S$ is called a<em> $k$-reptile</em> (or a <em>$k$-reptile simplex</em>) if it can be tiled by $k$ simplices with disjoint interiors that are all mutually congruent and similar to $S$. For $d=2$, triangular $k$-reptiles exist for all $k$ of the form $a^2, 3a^2$ or $a^2 + b^2$ and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only $k$-reptile simplices that are known for $d \ge 3$, have $k = m^d$, where $m$ is a positive integer. We substantially simplify the proof by Matoušek and the second author that for $d=3$, $k$-reptile tetrahedra can exist only for $k=m^3$. We then prove a weaker analogue of this result for $d=4$ by showing that four-dimensional $k$-reptile simplices can exist only for $k=m^2$.Jan Kynčl, Zuzana Patákováhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p1Fri, 14 Jul 2017 00:00:00 +1000$T$-Joins in Infinite Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p2
<p>We characterize the class of infinite graphs $G$ for which there exists a $T$-join for any choice of an infinite $T \subseteq V(G)$. We also show that the following well-known fact remains true in the infinite case. If $G$ is connected and does not contain a $T$-join, then it will if we either remove an arbitrary vertex from $T$ or add any new vertex to $T$.</p>Attila Joóhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p2Fri, 14 Jul 2017 00:00:00 +1000Ideals and Quotients of Diagonally Quasi-Symmetric Functions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p3
In 2004, J.-C. Aval, F. Bergeron and N. Bergeron studied the algebra of diagonally quasi-symmetric functions $\operatorname{\mathsf{DQSym}}$ in the ring $\mathbb{Q}[\mathbf{x},\mathbf{y}]$ with two sets of variables. They made conjectures on the structure of the quotient $\mathbb{Q}[\mathbf{x},\mathbf{y}]/\langle\operatorname{\mathsf{DQSym}}^+\rangle$, which is a quasi-symmetric analogue of the diagonal harmonic polynomials. In this paper, we construct a Hilbert basis for this quotient when there are infinitely many variables i.e. $\mathbf{x}=x_1,x_2,\dots$ and $\mathbf{y}=y_1,y_2,\dots$. Then we apply this construction to the case where there are finitely many variables, and compute the second column of its Hilbert matrix.Shu Xiao Lihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p3Fri, 14 Jul 2017 00:00:00 +1000The Spectral Gap of Graphs Arising From Substring Reversals
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p4
<p>The substring reversal graph $R_n$ is the graph whose vertices are the permutations $S_n$, and where two permutations are adjacent if one is obtained from a substring reversal of the other. We determine the spectral gap of $R_n$, and show that its spectrum contains many integer values. Further we consider a family of graphs that generalize the prefix reversal (or pancake flipping) graph, and show that every graph in this family has adjacency spectral gap equal to one.</p>Fan Chung, Josh Tobinhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p4Fri, 14 Jul 2017 00:00:00 +1000Multicolor Ramsey Numbers and Restricted Turán Numbers for the Loose 3-Uniform Path of Length Three
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p5
Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges $\{a,b,c\}, \{c,d,e\},$ and $\{e,f,g\}$. It is known that the $r$-colored Ramsey number for $P$ is $R(P;r)=r+6$ for $r=2,3$, and that $R(P;r)\le 3r$ for all $r\ge3$. The latter result follows by a standard application of the Tur<span>á</span>n number $\mathrm{ex}_3(n;P)$, which was determined to be $\binom{n-1}2$ in our previous work. We have also shown that the full star is the only extremal 3-graph for $P$. In this paper, we perform a subtle analysis of the Tur<span>á</span>n numbers for $P$ under some additional restrictions. Most importantly, we determine the largest number of edges in an $n$-vertex $P$-free 3-graph which is not a star. These Tur<span>á</span>n-type results, in turn, allow us to confirm the formula $R(P;r)=r+6$ for $r\in\{4,5,6,7\}$.Andrzej Ruciński, Eliza Jackowska, Joanna Polcynhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p5Fri, 14 Jul 2017 00:00:00 +1000Bounds for Distinguishing Invariants of Infinite Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p6
<pre>We consider infinite graphs. The distinguishing number $D(G)$ of a graph $G$ is the minimum number of colours in a vertex colouring of $G$ that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by $D'(G)$. We prove that $D'(G)\leq D(G)+1$. For proper colourings, we study relevant invariants called the distinguishing chromatic number $\chi_D(G)$, and the distinguishing chromatic index $\chi'_D(G)$, for vertex and edge colourings, respectively. We show that $\chi_D(G)\leq 2\Delta(G)-1$ for graphs with a finite maximum degree $\Delta(G)$, and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that $\chi'_D(G)\leq \chi'(G)+1$, where $\chi'(G)$ is the chromatic index of $G$, and we prove a similar result $\chi''_D(G)\leq \chi''(G)+1$ for proper total colourings. A number of conjectures are formulated.</pre>Wilfried Imrich, Rafał Kalinowski, Monika Pilśniak, Mohammad Hadi Shekarrizhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p6Fri, 14 Jul 2017 00:00:00 +1000Bijection Between Oriented Maps and Weighted Non-Oriented Maps
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p7
<p><span>We consider bicolored maps, i.e. graphs which are drawn on surfaces, and construct a bijection between (i) oriented maps with arbitary face structure, and (ii) (weighted) non-oriented maps with exactly one face. Above, each non-oriented map is counted with a multiplicity which is based on the concept of the orientability generating series and the measure of orientability of a map. This bijection has the remarkable property of preserving the underlying bicolored graph. Our bijection shows equivalence between two explicit formulas for the top-degree of Jack characters, i.e. (suitably normalized) coefficients in the expansion of Jack symmetric functions in the basis of power-sum symmetric functions.</span></p>Agnieszka Czyżewska-Jankowska, Piotr Śniadyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p7Fri, 14 Jul 2017 00:00:00 +1000Coloring Graphs with no Even Hole of Length at Least 6: the Triangle-Free Case
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p8
<pre><!--StartFragment-->In this paper, we prove that the class of graphs with no triangle and no induced cycle of even length at least 6 has bounded chromatic number. It is well-known that even-hole-free graphs are <span>$\chi$</span>-bounded but we allow here the existence of <span>$C_4$</span>. The proof relies on the concept of Parity Changing Path, an adaptation of Trinity Changing Path which was recently introduced by <span>Bonamy</span>, <span>Charbit</span> and <span>Thomassé</span> to prove that graphs with no induced cycle of length divisible by three have bounded chromatic number.<!--EndFragment--></pre>Aurélie Lagouttehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p8Fri, 14 Jul 2017 00:00:00 +1000Analysis of the Gift Exchange Problem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p9
<p>In the <em>gift exchange</em> game there are $n$ players and $n$ wrapped gifts. When a player's number is called, that person can either choose one of the remaining wrapped gifts, or can "steal" a gift from someone who has already unwrapped it, subject to the restriction that no gift can be stolen more than a total of $\sigma$ times. The problem is to determine the number of ways that the game can be played out, for given values of $\sigma$ and $n$. Formulas and asymptotic expansions are given for these numbers. This work was inspired in part by a 2005 remark by Robert A. Proctor in the <em>On-Line Encyclopedia of Integer Sequences</em>.</p><p>This is a sequel to the earlier article [arXiv:0907.0513] by the second and third authors, differing from it in that there are two additional authors and several new theorems, including the resolution of most of the conjectures, and the extensive tables have been omitted.</p>Moa Apagodu, David Applegate, N. J. A. Sloane, Doron Zeilbergerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p9Fri, 14 Jul 2017 00:00:00 +1000A Hopf Algebraic Approach to Schur Function Identities
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p10
Using cocommutativity of the Hopf algebra of symmetric functions, certain skew Schur functions are proved to be equal. Some of these skew Schur function identities are new.<br /><br />Karen Yeatshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p10Fri, 28 Jul 2017 00:00:00 +1000On the Number of Solutions in Random Hypergraph 2-Colouring
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p11
We determine the limiting distribution of the logarithm of the number of satisfying assignments in the random $k$-uniform hypergraph 2-colouring problem in a certain density regime for all $k\ge 3$. As a direct consequence we obtain that in this regime the random colouring model is contiguous wrt. the planted model, a result that helps simplifying the transfer of statements between these two models. <br /><br />Felicia Rassmannhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p11Fri, 28 Jul 2017 00:00:00 +1000Kazhdan-Lusztig Polynomials of Thagomizer Matroids
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p12
We introduce thagomizer matroids and compute the Kazhdan-Lusztig polynomial of a rank $n+1$ thagomizer matroid by showing that the coefficient of $t^k$ is equal to the number of Dyck paths of semilength $n$ with $k$ long ascents. We also give a conjecture for the $S_n$-equivariant Kazhdan-Lusztig polynomial of a thagomizer matroid.Katie R. Gedeonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p12Fri, 28 Jul 2017 00:00:00 +1000Sorting via Chip-Firing
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p13
We investigate a variant of the chip-firing process on the infinite path graph $\mathbb{Z}$: rather than treating the chips as indistinguishable, we label them with positive integers. To fire an unstable vertex, i.e. a vertex with more than one chip, we choose any two chips at that vertex and move the lesser-labeled chip to the left and the greater-labeled chip to the right. This labeled version of the chip-firing process exhibits a remarkable confluence property, similar to but subtler than the confluence that prevails for unlabeled chip-firing: when all chips start at the origin and the number of chips is even, the chips always end up in sorted order. Our proof of sorting relies upon an independently interesting lemma concerning unlabeled chip-firing which says that stabilization preserves a natural partial order on configurations. We also discuss some extensions of this sorting phenomenon to other graphs (variants of the infinite path), to other initial configurations, and to other Cartan-Killing types.Sam Hopkins, Thomas McConville, James Propphttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p13Fri, 28 Jul 2017 00:00:00 +1000Expanders with Superquadratic Growth
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p14
<p>We prove several expanders with exponent strictly greater than $2$. For any finite set $A \subset \mathbb R$, we prove the following six-variable expander results:</p><p>$|(A-A)(A-A)(A-A)| \gg \frac{|A|^{2+\frac{1}{8}}}{\log^{\frac{17}{16}}|A|},$</p><p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">$\left|\frac{A+A}{A+A}+\frac{A}{A}\right| \gg \frac{|A|^{2+\frac{2}{17}}}{\log^{\frac{16}{17}}|A|},$</p><p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </p><p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">$\left|\frac{AA+AA}{A+A}\right| \gg \frac{|A|^{2+\frac{1}{8}}}{\log |A|},$</p><p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </p><p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">$\left|\frac{AA+A}{AA+A}\right| \gg \frac{|A|^{2+\frac{1}{8}}}{\log |A|}.$</p>Antal Balog, Oliver Roche-Newton, Dmitry Zhelezovhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p14Fri, 28 Jul 2017 00:00:00 +1000Orthogonal Trades in Complete Sets of MOLS
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p15
<p>Let $B_p$ be the Latin square given by the addition table for the integers modulo an odd prime $p$. Here we consider the properties of Latin trades in $B_p$ which preserve orthogonality with one of the $p-1$ MOLS given by the finite field construction. We show that for certain choices of the orthogonal mate, there is a lower bound logarithmic in $p$ for the number of times each symbol occurs in such a trade, with an overall lower bound of $(\log{p})^2/\log\log{p}$ for the size of such a trade. Such trades imply the existence of orthomorphisms of the cyclic group which differ from a linear orthomorphism by a small amount. We also show that any transversal in $B_p$ hits the main diagonal either $p$ or at most $p-\log_2{p}-1$ times. Finally, if $p\equiv 1\pmod{6}$ we show the existence of a Latin square which is orthogonal to $B_p$ and which contains a $2\times 2$ subsquare.</p>Nicholas Cavenagh, Diane Donovan, Fatih Demirkalehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p15Fri, 28 Jul 2017 00:00:00 +1000On the Structure of the Power Graph and the Enhanced Power Graph of a Group
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p16
<p>Let $G$ be a group. The <em>power graph</em> of $G$ is a graph with the vertex set $G$, having an edge between two elements whenever one is a power of the other. We characterize nilpotent groups whose power graphs have finite independence number. For a bounded exponent group, we prove its power graph is a perfect graph and we determine its clique/chromatic number. Furthermore, it is proved that for every group $G$, the clique number of the power graph of $G$ is at most countably infinite. We also measure how close the power graph is to the <em>commuting graph</em> by introducing a new graph which lies in between. We call this new graph as the <em>enhanced power graph</em>. For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal.</p>Ghodratollah Aalipour, Saieed Akbari, Peter J. Cameron, Reza Nikandish, Farzad Shaveisihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p16Fri, 28 Jul 2017 00:00:00 +1000Coincidences between Characters to Hook Partitions and 2-Part Partitions on Families arising from 2-Regular Classes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p17
Strongly refining results by Regev, Regev and Zeilberger, we prove surprising coincidences between characters to 2-part partitions of size $n$ and characters to hook partitions of size $n+2$ on two related families obtained by extending 2-regular conjugacy classes.Christine Bessenrodthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p17Fri, 28 Jul 2017 00:00:00 +1000Unified Hanani–Tutte Theorem
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p18
<p>We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph $G$ has a drawing $D$ in the plane where every pair of independent edges crosses an even number of times, then $G$ has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in $D$. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.</p>Radoslav Fulek, Jan Kynčl, Dömötör Pálvölgyihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p18Fri, 28 Jul 2017 00:00:00 +1000New Constructions of Self-Complementary Cayley Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p19
Self-complementary Cayley graphs are useful in the study of Ramsey numbers, but they are relatively very rare and hard to construct. In this paper, we construct several families of new self-complementary Cayley graphs of order $p^4$ where $p$ is a prime and congruent to $1$ modulo $8$.Lei Wang, Cai Heng Li, Yin Liu, Ci Xuan Wuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p19Fri, 28 Jul 2017 00:00:00 +1000Uniform Mixing on Cayley Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p20
<p>We provide new examples of Cayley graphs on which the quantum walks reach uniform mixing. Our first result is a complete characterization of all $2(d+2)$-regular Cayley graphs over $\mathbb{Z}_3^d$ that admit uniform mixing at time $2\pi/9$. Our second result shows that for every integer $k\ge 3$, we can construct Cayley graphs over $\mathbb{Z}_q^d$ that admit uniform mixing at time $2\pi/q^k$, where $q=3, 4$.</p><p>We also find the first family of irregular graphs, the Cartesian powers of the star $K_{1,3}$, that admit uniform mixing.</p>Chris Godsil, Hanmeng Zhanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p20Fri, 28 Jul 2017 00:00:00 +1000Tail Positive Words and Generalized Coinvariant Algebras
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p21
<p>Let $n,k,$ and $r$ be nonnegative integers and let $S_n$ be the symmetric group. We introduce a quotient $R_{n,k,r}$ of the polynomial ring $\mathbb{Q}[x_1, \dots, x_n]$ in $n$ variables which carries the structure of a graded $S_n$-module. When $r \ge n$ or $k = 0$ the quotient $R_{n,k,r}$ reduces to the classical coinvariant algebra $R_n$ attached to the symmetric group. Just as algebraic properties of $R_n$ are controlled by combinatorial properties of permutations in $S_n$, the algebra of $R_{n,k,r}$ is controlled by the combinatorics of objects called <em>tail positive words</em>. We calculate the standard monomial basis of $R_{n,k,r}$ and its graded $S_n$-isomorphism type. We also view $R_{n,k,r}$ as a module over the 0-Hecke algebra $H_n(0)$, prove that $R_{n,k,r}$ is a projective 0-Hecke module, and calculate its quasisymmetric and nonsymmetric 0-Hecke characteristics. We conjecture a relationship between our quotient $R_{n,k,r}$ and the delta operators of the theory of Macdonald polynomials.</p>Brendon Rhoades, Andrew Timothy Wilsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p21Fri, 28 Jul 2017 00:00:00 +1000Uniform Mixing and Association Schemes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p22
<p>We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.</p><p>First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph $X$ with $n$ vertices, then $n$ is divisible by four. We also prove that if $X$ is bipartite and regular, then $n$ is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on $C_{2m}$ for $m \geq 3$. Using a result of Haagerup, we show that uniform mixing does not occur on $C_p$ for any prime $p$ such that $p \geq 5$. In contrast to this result, we see that $\epsilon$-uniform mixing occurs on $C_p$ for all primes $p$.</p>Chris Godsil, Natalie Mullin, Aidan Royhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p22Fri, 11 Aug 2017 00:00:00 +1000Disjoint Difference Families from Galois Rings
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p23
In this paper, we give new constructions of disjoint difference families from Galois rings. The constructions are based on choosing cosets of the unit group of a subring in the Galois ring $\mathrm{GR}(p^2,p^{2s})$. Two infinite families of disjoint difference families are obtained from the Galois rings $\mathrm{GR}(p^{2},p^{4n})$ and $\mathrm{GR}(2^2,2^{2s})$.Koji Momiharahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p23Fri, 11 Aug 2017 00:00:00 +1000Top Degree Part in $b$-Conjecture for Unicellular Bipartite Maps
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p24
<p>Goulden and Jackson (1996) introduced, using Jack symmetric functions, some multivariate generating series $\psi(\boldsymbol{x}, \boldsymbol{y},\boldsymbol{z}; 1, 1+\beta)$ with an additional parameter $\beta$ that might be interpreted as a continuous deformation of the rooted bipartite maps generating series. Indeed, it has a property that for $\beta \in \{0,1\}$, it specializes to the rooted, orientable (general, i.e. orientable or not, respectively) bipartite maps generating series. They made the following conjecture: coefficients of $\psi$ are polynomials in $\beta$ with positive integer coefficients that can be written as a multivariate generating series of rooted, general bipartite maps, where the exponent of $\beta$ is an integer-valued statistics that in some sense "measures the non-orientability" of the corresponding bipartite map.</p><p>We show that except two special values of $\beta = 0,1$ for which the combinatorial interpretation of the coefficients of $\psi$ is known, there exists a third special value $\beta = -1$ for which the coefficients of $\psi$ indexed by two partitions $\mu,\nu$, and one partition with only one part are given by rooted, orientable bipartite maps with arbitrary face degrees and black/white vertex degrees given by $\mu$/$\nu$, respectively. We show that this evaluation corresponds, up to a sign, to a top-degree part of the coefficients of $\psi$. As a consequence, we introduce a collection of integer-valued statistics of maps $(\eta)$ such that the top-degree of the multivariate generating series of rooted, bipartite maps with only one face (called <em>unicellular</em>) with respect to $\eta$ gives the top degree of the appropriate coefficients of $\psi$. Finally, we show that $b$ conjecture holds true for all rooted, unicellular bipartite maps of genus at most $2$.</p>Maciej Dołęgahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p24Fri, 11 Aug 2017 00:00:00 +1000Frankl's Conjecture for Subgroup Lattices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p25
<p>We show that the subgroup lattice of any finite group satisfies Frankl’s Union-Closed Conjecture. We show the same for all lattices with a modular coatom, a family which includes all supersolvable and dually semimodular lattices. A common technical result used to prove both may be of some independent interest.</p>Alireza Abdollahi, Russ Woodroofe, Gjergji Zaimihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p25Fri, 11 Aug 2017 00:00:00 +1000A Note on Intersecting Hypergraphs with Large Cover Number
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p26
<p>We give a construction of $r$-partite $r$-uniform intersecting hypergraphs with cover number at least $r-4$ for all but finitely many $r$. This answers a question of Abu-Khazneh, Bar<span>á</span>t, Pokrovskiy and Szab<span>ó</span>, and shows that a long-standing unsolved conjecture due to Ryser is close to being best possible for every value of $r$.</p>P. E. Haxell, A. D. Scotthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p26Fri, 11 Aug 2017 00:00:00 +1000On some Euler-Mahonian Distributions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p27
<p><!--StartFragment--> We prove that the pair of statistics (des,maj) on multiset permutations is equidistributed with the pair (stc,inv) on certain quotients of the symmetric group. We define an analogue of the statistic stc on multiset permutations whose joint distribution with the inversions equals that of (des,maj). We extend the definition of the statistic stc to hyperoctahedral and even hyperoctahedral groups. These functions, together with the Coxeter length, are equidistributed with (ndes,nmaj) and (ddes,dmaj), respectively.<!--EndFragment--></p>Angela Carnevalehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p27Fri, 11 Aug 2017 00:00:00 +1000Counting Lyndon Factors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p28
<p>In this paper, we determine the maximum number of distinct Lyndon factors that a word of length $n$ can contain. We also derive formulas for the expected total number of Lyndon factors in a word of length $n$ on an alphabet of size $\sigma$, as well as the expected number of distinct Lyndon factors in such a word. The minimum number of distinct Lyndon factors in a word of length $n$ is $1$ and the minimum total number is $n$, with both bounds being achieved by $x^n$ where $x$ is a letter. A more interesting question to ask is <em>what is the minimum number of distinct Lyndon factors in a Lyndon word of length $n$?</em> In this direction, it is known (Saari, 2014) that a lower bound for the number of distinct Lyndon factors in a Lyndon word of length $n$ is $\lceil\log_{\phi}(n) + 1\rceil$, where $\phi$ denotes the <em>golden ratio</em> $(1 + \sqrt{5})/2$. Moreover, this lower bound is sharp when $n$ is a <em>Fibonacci number</em> and is attained by the so-called finite <em>Fibonacci Lyndon words</em>, which are precisely the Lyndon factors of the well-known <em>infinite Fibonacci word</em> $\boldsymbol{f}$ (a special example of an <em>infinite Sturmian word</em>). Saari (2014) conjectured that if $w$ is Lyndon word of length $n$, $n\ne 6$, containing the least number of distinct Lyndon factors over all Lyndon words of the same length, then $w$ is a <em>Christoffel word</em> (i.e., a Lyndon factor of an infinite Sturmian word). We give a counterexample to this conjecture. Furthermore, we generalise Saari's result on the number of distinct Lyndon factors of a Fibonacci Lyndon word by determining the number of distinct Lyndon factors of a given Christoffel word. We end with two open problems.</p>Amy Glen, Jamie Simpson, W. F. Smythhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p28Fri, 11 Aug 2017 00:00:00 +1000Beyond Degree Choosability
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p29
<p>Let $G$ be a connected graph with maximum degree $\Delta$. Brooks' theorem states that $G$ has a $\Delta$-coloring unless $G$ is a complete graph or an odd cycle. A graph $G$ is <em>degree-choosable</em> if $G$ can be properly colored from its lists whenever each vertex $v$ gets a list of $d(v)$ colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph $G$ is degree-choosable unless each block of $G$ is a complete graph or an odd cycle; such a graph $G$ is a <em>Gallai tree</em>.<br /> <br /> This degree-choosability result was further strengthened to Alon—Tarsi orientations; these are orientations of $G$ in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph $G$ is <em>degree-AT</em> if $G$ has an Alon—Tarsi orientation in which each vertex has indegree at least 1. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladký, Král', and Schauz showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs $(G,x)$ where $G$ is a connected graph and $x$ is some specified vertex in $V(G)$. We characterize pairs such that $G$ has no Alon—Tarsi orientation in which each vertex has indegree at least 1 and $x$ has indegree at least 2. When $G$ is 2-connected, the characterization is simple to state.</p>Daniel W. Cranston, Landon Rabernhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p29Fri, 11 Aug 2017 00:00:00 +1000Quasi-Eulerian Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p30
<p>We generalize the notion of an Euler tour in a graph in the following way. An <em>Euler family</em> in a hypergraph is a family of closed walks that jointly traverse each edge of the hypergraph exactly once. An <em>Euler tour</em>thus corresponds to an Euler family with a single component. We provide necessary and sufficient conditions for the existence of an Euler family in an arbitrary hypergraph, and in particular, we show that every 3-uniform hypergraph without cut edges admits an Euler family. Finally, we show that the problem of existence of an Euler family is polynomial on the class of all hypergraphs.</p><p>This work complements existing results on rank-1 universal cycles and 1-overlap cycles in triple systems, as well as recent results by <span>Lonc</span> and <span>Naroski</span>, who showed that the problem of existence of an Euler tour in a <span>hypergraph</span> is NP-complete.</p>Amin Bahmanian, Mateja Šajnahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p30Fri, 11 Aug 2017 00:00:00 +1000The Total Acquisition Number of Random Geometric Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p31
Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight on $v$ is at least as large as the weight on $u$. The total acquisition number of $G$, denoted by $a_t(G)$, is the minimum cardinality of the set of vertices with positive weight at the end of the process. In this paper, we investigate random geometric graphs $\mathcal{G}(n,r)$ with $n$ vertices distributed uniformally at random in $[0,\sqrt{n}]^2$ and two vertices being adjacent if and only if their distance is at most $r$. We show that asymptotically almost surely $a_t(\mathcal{G}(n,r)) = \Theta( n / (r \lg r)^2)$ for the whole range of $r=r_n \ge 1$ such that $r \lg r \le \sqrt{n}$. By monotonicity, asymptotically almost surely $a_t(\mathcal{G}(n,r)) = \Theta(n)$ if $r < 1$, and $a_t(\mathcal{G}(n,r)) = \Theta(1)$ if $r \lg r > \sqrt{n}$.Ewa Infeld, Dieter Mitsche, Paweł Prałathttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p31Fri, 11 Aug 2017 00:00:00 +1000On $t$-Common List-Colorings
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p32
<p>In this paper, we introduce a new variation of list-colorings. For a graph $G$ and for a given nonnegative integer $t$, a <em>$t$-common list assignment </em>of $G$ is a mapping $L$ which assigns each vertex $v$ a set $L(v)$ of colors such that given set of $t$ colors belong to $L(v)$ for every $v\in V(G)$. The <em>$t$-common list chromatic number</em> of $G$ denoted by $ch_t(G)$ is defined as the minimum positive integer $k$ such that there exists an $L$-coloring of $G$ for every $t$-common list assignment $L$ of $G$, satisfying $|L(v)| \ge k$ for every vertex $v\in V(G)$. We show that for all positive integers $k, \ell$ with $2 \le k \le \ell$ and for any positive integers $i_1 , i_2, \ldots, i_{k-2}$ with $k \le i_{k-2} \le \cdots \le i_1 \le \ell$, there exists a graph $G$ such that $\chi(G)= k$, $ch(G) = \ell$ and $ch_t(G) = i_t$ for every $t=1, \ldots, k-2$. Moreover, we consider the $t$-common list chromatic number of planar graphs. From the four color theorem and the result of Thomassen (1994), for any $t=1$ or $2$, the sharp upper bound of $t$-common list chromatic number of planar graphs is $4$ or $5$. Our first step on $t$-common list chromatic number of planar graphs is to find such a sharp upper bound. By constructing a planar graph $G$ such that $ch_1(G) =5$, we show that the sharp upper bound for $1$-common list chromatic number of planar graphs is $5$. The sharp upper bound of $2$-common list chromatic number of planar graphs is still open. We also suggest several questions related to $t$-common list chromatic number of planar graphs.</p>Hojin Choi, Young Soo Kwonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p32Fri, 11 Aug 2017 00:00:00 +1000Gröbner Bases Techniques for an $S$-Packing $k$-Coloring of a Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p33
In this paper, polynomial ideal theory is used to deal with the problem of the $S$-packing coloring of a finite undirected and unweighted graph by introducing a family of polynomials encoding the problem. A method to find the $S$-packing colorings of the graph is presented and illustrated by examples.Hamid Maaroufhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p33Fri, 25 Aug 2017 00:00:00 +1000Multidimensional Lower Density Versions of Plünnecke’s Inequality
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p34
We investigate the lower asymptotic density of sumsets in $\mathbb{N}^2$ by proving certain Plünnecke type inequalities for various notions of lower density in $\mathbb{N}^2$. More specifically, we introduce a notion of lower <em>tableaux</em> density in $\mathbb{N}^2$ which involves averaging over convex tableaux-shaped regions in $\mathbb{N}^2$ which contain the origin. This generalizes the well known Plünnecke type inequality for the lower asymptotic density of sumsets in $\mathbb{N}$. We also provide a conjectural Plünnecke inequality for the more basic notion of lower <em>rectangular</em> asymtpotic density in $\mathbb{N}^2$ and prove certain partial results.Kamil Bulinskihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p34Fri, 25 Aug 2017 00:00:00 +1000Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p35
The words separation problem, originally formulated by Goralcik and Koubek (1986), is stated as follows. Let $Sep(n)$ be the minimum number such that for any two words of length $\le n$ there is a deterministic finite automaton with $Sep(n)$ states, accepting exactly one of them. The problem is to find the asymptotics of the function $Sep$. This problem is inverse to finding the asymptotics of the length of the shortest identity in full transformation semigroups $T_k$. The known lower bound on $Sep$ stems from the unary identity in $T_k$. We find the first series of identities in $T_k$ which are shorter than the corresponding unary identity for infinitely many values of $k$, and thus slightly improve the lower bound on $Sep(n)$. Then we present some short positive identities in symmetric groups, improving the lower bound on separating words by permutational automata by a multiplicative constant. Finally, we present the results of computer search for short identities for small $k$.Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsevhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p35Fri, 25 Aug 2017 00:00:00 +1000Counting Gluings of Octahedra
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p36
<pre><span>Three-dimensional colored triangulations are gluings of tetrahedra whose faces carry the colors 0, 1, 2, 3 and in which the attaching maps between tetrahedra are defined using the colors. This framework makes it possible to generalize the notion of two-dimensional </span><span>$2p$</span><span>-angulations to three dimensions in a way which is suitable for combinatorics and enumeration. In particular, universality classes of three-dimensional triangulations can be investigated within this framework. Here we study colored triangulations obtained by gluing octahedra. Those which maximize the number of edges at fixed number of octahedra are fully characterized and are shown to have the topology of the 3-sphere. They are further shown to be in bijection with a family of plane trees. The enumeration is performed both directly and using this bijection.</span></pre>Valentin Bonzom, Luca Lionnihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p36Fri, 25 Aug 2017 00:00:00 +1000New Upper Bound for Sums of Dilates
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p37
<p>For $\lambda \in \mathbb{Z}$, let $\lambda \cdot A = \{ \lambda a : a \in A\}$. Suppose $r, h\in \mathbb{Z}$ are sufficiently large and comparable to each other. We prove that if $|A+A| \le K |A|$ and $\lambda_1, \ldots, \lambda_h \le 2^r$, then <br />\[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{ 7 rh /\ln (r+h) } |A|. \]<br />This improves upon a result of Bukh who shows that<br />\[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{O(rh)} |A|. \]<br />Our main technique is to combine Bukh's idea of considering the binary expansion of $\lambda_i$ with a result on biclique decompositions of bipartite graphs.</p>Albert Bush, Yi Zhaohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p37Fri, 25 Aug 2017 00:00:00 +1000A Note on Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p38
We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Rúzsa as well as Rué et al.Christoph Spiegelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p38Fri, 25 Aug 2017 00:00:00 +1000A Dual Ramsey Theorem for Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p39
<p>In 2012 M. Sokić proved that the that the class of all finite permutations has the Ramsey property. Using different strategies the same result was then reproved in 2013 by J. Böttcher and J. Foniok, in 2014 by M. Bodirsky and in 2015 yet another proof was provided by M. Sokić.</p><p>Using the categorical reinterpretation of the Ramsey property in this paper we prove that the class of all finite permutations has the dual Ramsey property as well. It was Leeb who pointed out in 1970 that the use of category theory can be quite helpful both in the formulation and in the proofs of results pertaining to structural Ramsey theory. In this paper we argue that this is even more the case when dealing with the dual Ramsey property.</p>Dragan Mašulovićhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p39Fri, 25 Aug 2017 00:00:00 +1000Tomaszewski's Problem on Randomly Signed Sums: Breaking the 3/8 Barrier
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p40
Let $v_1$, $v_2$, ..., $v_n$ be real numbers whose squares add up to 1. Consider the $2^n$ signed sums of the form $S = \sum \pm v_i$. Holzman and Kleitman (1992) proved that at least 3/8 of these sums satisfy $|S| \le 1$. This 3/8 bound seems to be the best their method can achieve. Using a different method, we improve the bound to 13/32, thus breaking the 3/8 barrier.Ravi B. Boppana, Ron Holzmanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p40Fri, 25 Aug 2017 00:00:00 +1000Fair Splitting of Colored Paths
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p41
<p>This paper deals with two problems about splitting fairly a path with colored vertices, where "fairly" means that each part contains almost the same amount of vertices in each color.</p><p>Our first result states that it is possible to remove one vertex per color from a path with colored vertices so that the remaining vertices can be fairly split into two independent sets of the path. It implies in particular a conjecture of Ron Aharoni and coauthors. The proof uses the octahedral Tucker lemma.</p><p>Our second result is the proof of a particular case of a conjecture of Dömötör Pálvölgyi about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by Noga Alon and coauthors to prove the discrete splitting necklace theorem from the continuous one.</p>Meysam Alishahi, Frédéric Meunierhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p41Fri, 25 Aug 2017 00:00:00 +1000Connected Even Factors in the Square of Essentially 2-Edge-connected Graph
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p42
An essentially $k$-edge connected graph $G$ is a connected graph such that deleting less than $k$ edges from $G$ cannot result in two nontrivial components. In this paper we prove that if an essentially 2-edge-connected graph $G$ satisfies that for any pair of leaves at distance 4 in $G$ there exists another leaf of $G$ that has distance 2 to one of them, then the square $G^2$ has a connected even factor with maximum degree at most 4. Moreover we show that, in general, the square of essentially 2-edge-connected graph does not contain a connected even factor with bounded maximum degree.Jan Ekstein, Baoyindureng Wu, Liming Xionghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p42Fri, 08 Sep 2017 00:00:00 +1000Enumeration of Chord Diagrams without Loops and Parallel Chords
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p43
We enumerate chord diagrams without loops and without both loops and parallel chords. For labelled diagrams we obtain generating functions, for unlabelled ones we derive recurrence relations.Evgeniy Krasko, Alexander Omelchenkohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p43Fri, 08 Sep 2017 00:00:00 +1000Nice Restrictions of Reflection Arrangements
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p44
In a recent paper, Hoge and the second author classified all nice and all inductively factored reflection arrangements. In this note we extend this classification by determining all nice and all inductively factored restrictions of reflection arrangements.Tilman Möller, Gerhard Röhrlehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p44Fri, 08 Sep 2017 00:00:00 +1000Vertex-Addition Strategy for Domination-Like Invariants
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p45
<p>In [J. Graph Theory <strong>13</strong> (1989) 749—762], McCuaig and Shepherd gave an upper bound of the domination number for connected graphs with minimum degree at least two. In this paper, we propose a simple strategy which, together with the McCuaig-Shepherd theorem, gives a sharp upper bound of the domination number via the number of leaves. We also apply the same strategy to other domination-like invariants, and find a relationship between such invariants and the number of leaves.</p>Michitaka Furuya, Naoki Matsumotohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p45Fri, 08 Sep 2017 00:00:00 +1000On a Special Class of Hyper-Permutahedra
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p46
<p class="p1"><span class="s1">Minkowski sums of simplices in<span class="Apple-converted-space"> </span></span>${\mathbb{R}}^n$ form an interesting class of polytopes that seem to emerge in various situations. In this paper we discuss the Minkowski sum of the<span class="Apple-converted-space"> </span>simplices $\Delta_{k-1}$ in ${\mathbb{R}}^n$ where $k$ and $n$ are fixed, their flags and some of their face lattice structure. In particular, we derive a closed formula for<span class="Apple-converted-space"> </span>their <em>exponential generating flag function</em>. These polytopes are simple, include both the simplex $\Delta_{n-1}$ and the permutahedron $\Pi_{n-1}$, and form a Minkowski basis for more general permutahedra.</p><p class="p1"> </p>Geir Agnarssonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p46Fri, 08 Sep 2017 00:00:00 +1000Do Triangle-Free Planar Graphs have Exponentially Many $3$-Colorings?
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p47
Thomassen conjectured that triangle-free planar graphs have an exponential number of $3$-colorings. We show this conjecture to be equivalent to the following statement: there exists a positive real $\alpha$ such that whenever $G$ is a planar graph and $A$ is a subset of its edges whose deletion makes $G$ triangle-free, there exists a subset $A'$ of $A$ of size at least $\alpha|A|$ such that $G-(A\setminus A')$ is $3$-colorable. This equivalence allows us to study restricted situations, where we can prove the statement to be true.Zdeněk Dvořák, Jean-Sébastien Serenihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p47Fri, 08 Sep 2017 00:00:00 +1000Combinatorial Reductions for the Stanley Depth of $I$ and $S/I$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p48
We develop combinatorial tools to study the relationship between the Stanley depth of a monomial ideal $I$ and the Stanley depth of its compliment, $S/I$. Using these results we are able to prove that if $S$ is a polynomial ring with at most 5 indeterminates and $I$ is a square-free monomial ideal, then the Stanley depth of $S/I$ is strictly larger than the Stanley depth of $I$. Using a computer search, we are able to extend this strict inequality up to polynomial rings with at most 7 indeterminates. This partially answers questions asked by Propescu and Qureshi as well as Herzog.Mitchel T. Keller, Stephen J. Younghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p48Fri, 08 Sep 2017 00:00:00 +1000A Note on the Rainbow Connection of Random Regular Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p49
<p>We prove that a random 3-regular graph has rainbow connection number $O(\log n)$. This completes the remaining open case from <em>Rainbow connection of random regular graphs</em>, by Dudek, Frieze and Tsourakakis.</p><p><!--EndFragment--></p>Michael Molloyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p49Fri, 08 Sep 2017 00:00:00 +1000Promotion of Increasing Tableaux: Frames and Homomesies
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p50
<pre><!--StartFragment-->A key fact about M.-P. Schützenberger's (1972) promotion operator on rectangular standard Young tableaux is that iterating promotion once per entry recovers the original tableau. For tableaux with strictly increasing rows and columns, H. Thomas and A. Yong (2009) introduced a theory of <span>$K$</span>-jeu de taquin with applications to <span>$K$</span>-theoretic Schubert calculus. The author (2014) studied a <span>$K$</span>-promotion operator <span>$\mathcal{P}$</span> derived from this theory, but observed that this key fact does not generally extend to <span>$K$</span>-promotion of such increasing tableaux.</pre><pre> </pre><pre>Here, we show that the key fact holds for labels on the boundary of the rectangle. That is, for <span>$T$</span> a rectangular increasing tableau with entries bounded by <span>$q$</span>, we have <span>$\mathsf{Frame}(\mathcal{P}^q(T)) = \mathsf{Frame}(T)$</span>, where <span>$\mathsf{Frame}(U)$</span> denotes the restriction of <span>$U$</span> to its first and last row and column. Using this fact, we obtain a family of homomesy results on the average value of certain statistics over <span>$K$</span>-promotion orbits, extending a <span>$2$</span>-row theorem of J. Bloom, D. Saracino, and the author (2016) to arbitrary rectangular shapes.<!--EndFragment--></pre><pre><!--EndFragment--></pre>Oliver Pechenikhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p50Fri, 08 Sep 2017 00:00:00 +1000Crystal Analysis of type C Stanley Symmetric Functions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p51
Combining results of T.K. Lam and J. Stembridge, the type $C$ Stanley symmetric function $F_w^C(\mathbf{x})$, indexed by an element $w$ in the type $C$ Coxeter group, has a nonnegative integer expansion in terms of Schur functions. We provide a crystal theoretic explanation of this fact and give an explicit combinatorial description of the coefficients in the Schur expansion in terms of highest weight crystal elements.Graham Hawkes, Kirill Paramonov, Anne Schillinghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p51Fri, 08 Sep 2017 00:00:00 +1000Internally Fair Factorizations and Internally Fair Holey Factorizations with Prescribed Regularity
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p52
<p>Let $G$ be a multipartite multigraph without loops. Then $G$ is said to be <em>internally fair</em> if its edges are shared as evenly as possible among all pairs of its partite sets. An <em>internally fair factorization</em> of $G$ is an edge-decomposition of $G$ into internally fair regular spanning subgraphs. A <em>holey factor</em> of $G$ is a regular subgraph spanning all vertices but one partite set. An <em>internally fair holey factorization</em> is an edge-decomposition of $G$ into internally fair holey factors. In this paper, we settle the existence of internally fair (respectively, internally fair holey) factorizations of the complete equipartite multigraph into factors (respectively, holey factors) with prescribed regularity.</p>Aras Erzurumluoğlu, Chris A. Rodgerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p52Fri, 08 Sep 2017 00:00:00 +1000Note on the Union-Closed Sets Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p53
The union-closed sets conjecture states that if a finite family of sets $\mathcal{A} \neq \{\varnothing\}$ is union-closed, then there is an element which belongs to at least half the sets in $\mathcal{A}$. In 2001, D. Reimer showed that the average set size of a union-closed family, $\mathcal{A}$, is at least $\frac{1}{2} \log_2 |\mathcal{A}|$. In order to do so, he showed that all union-closed families satisfy a particular condition, which in turn implies the preceding bound. Here, answering a question raised in the context of T. Gowers' polymath project on the union-closed sets conjecture, we show that Reimer's condition alone is not enough to imply that there is an element in at least half the sets.Abigail Razhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p53Fri, 08 Sep 2017 00:00:00 +1000Large Monochromatic Components in Edge Colored Graphs with a Minimum Degree Condition
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p54
<p>It is well-known that in every $k$-coloring of the edges of the complete graph $K_n$ there is a monochromatic connected component of order at least ${n\over k-1}$. In this paper we study an extension of this problem by replacing complete graphs by graphs of large minimum degree. For $k=2$ the authors proved that $\delta(G)\ge{3n\over 4}$ ensures a monochromatic connected component with at least $\delta(G)+1$ vertices in every $2$-coloring of the edges of a graph $G$ with $n$ vertices. This result is sharp, thus for $k=2$ we really need a complete graph to guarantee that one of the colors has a monochromatic connected spanning subgraph. Our main result here is that for larger values of $k$ the situation is different, graphs of minimum degree $(1-\epsilon_k)n$ can replace complete graphs and still there is a monochromatic connected component of order at least ${n\over k-1}$, in fact $$\delta(G)\ge \left(1 - \frac{1}{1000(k-1)^9}\right)n$$ suffices.</p><p>Our second result is an improvement of this bound for $k=3$. If the edges of $G$ with $\delta(G)\geq {9n\over 10}$ are $3$-colored, then there is a monochromatic component of order at least ${n\over 2}$. We conjecture that this can be improved to ${7n\over 9}$ and for general $k$ we conjecture the following: if $k\geq 3$ and $G$ is a graph of order $n$ such that $\delta(G)\geq \left( 1 - \frac{k-1}{k^2}\right)n$, then in any $k$-coloring of the edges of $G$ there is a monochromatic connected component of order at least ${n\over k-1}$.</p>András Gyárfás, Gábor Sárközyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p54Fri, 08 Sep 2017 00:00:00 +1000Application of Smirnov Words to Waiting Time Distributions of Runs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p55
<p>Consider infinite random words over a finite alphabet where the letters occur as an i.i.d. sequence according to some arbitrary distribution on the alphabet. The expectation and the variance of the waiting time for the first completed $h$-run of any letter (i.e., first occurrence of $h$ subsequential equal letters) is computed. The expected waiting time for the completion of $h$-runs of $j$ arbitrary distinct letters is also given.</p>Uta Freiberg, Clemens Heuberger, Helmut Prodingerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p55Fri, 08 Sep 2017 00:00:00 +1000Stability for Vertex Cycle Covers
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p56
<p>In 1996 Kouider and Lonc proved the following natural generalization of Dirac's Theorem: for any integer $k\geq 2$, if $G$ is an $n$-vertex graph with minimum degree at least $n/k$, then there are $k-1$ cycles in $G$ that together cover all the vertices.</p><p>This is tight in the sense that there are $n$-vertex graphs that have minimum degree $n/k-1$ and that do not contain $k-1$ cycles with this property. A concrete example is given by $I_{n,k} = K_n\setminus K_{(k-1)n/k+1}$ (an edge-maximal graph on $n$ vertices with an independent set of size $(k-1)n/k+1$). This graph has minimum degree $n/k-1$ and cannot be covered with fewer than $k$ cycles. More generally, given positive integers $k_1,\dotsc,k_r$ summing to $k$, the disjoint union $I_{k_1n/k,k_1}+ \dotsb + I_{k_rn/k,k_r}$ is an $n$-vertex graph with the same properties.</p><p>In this paper, we show that there are no extremal examples that differ substantially from the ones given by this construction. More precisely, we obtain the following stability result: if a graph $G$ has $n$ vertices and minimum degree nearly $n/k$, then it either contains $k-1$ cycles covering all vertices, or else it must be close (in ‘edit distance') to a subgraph of $I_{k_1n/k,k_1}+ \dotsb + I_{k_rn/k,k_r}$, for some sequence $k_1,\dotsc,k_r$ of positive integers that sum to $k$.</p><p>Our proof uses Szemerédi's Regularity Lemma and the related machinery.</p>József Balogh, Frank Mousset, Jozef Skokanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p56Fri, 08 Sep 2017 00:00:00 +1000Majority Choosability of Digraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p57
<p>A <em>majority coloring</em> of a digraph is a coloring of its vertices such that for each vertex $v$, at most half of the out-neighbors of $v$ have the same color as $v$. A digraph $D$ is <em>majority $k$-choosable</em> if for any assignment of lists of colors of size $k$ to the vertices there is a majority coloring of $D$ from these lists. We prove that every digraph is majority $4$-choosable. This gives a positive answer to a question posed recently by Kreutzer, Oum, Seymour, van der Zypen, and Wood (2017). We obtain this result as a consequence of a more general theorem, in which majority condition is profitably extended. For instance, the theorem implies also that every digraph has a coloring from arbitrary lists of size three, in which at most $2/3$ of the out-neighbors of any vertex share its color. This solves another problem posed by the same authors, and supports an intriguing conjecture stating that every digraph is majority $3$-colorable.</p>Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczukhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p57Fri, 22 Sep 2017 00:00:00 +1000Group Actions on Partitions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p58
<p>We introduce group actions on the integer partitions and their variances. Using generating functions and Burnside's lemma, we study arithmetic properties of the counting functions arising from group actions. In particular, we find a modulo 4 congruence involving the number of ordinary partitions and the number of partitions into distinct parts.</p>Byungchan Kimhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p58Fri, 22 Sep 2017 00:00:00 +1000Non-Flat Regular Polytopes and Restrictions on Chiral Polytopes
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p59
<p>An abstract polytope is <em>flat</em> if every facet is incident on every vertex. In this paper, we prove that no chiral polytope has flat finite regular facets and finite regular vertex-figures. We then determine the three smallest non-flat regular polytopes in each rank, and use this to show that for $n \geq 8$, a chiral $n$-polytope has at least $48(n-2)(n-2)!$ flags.</p>Gabe Cunninghamhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p59Fri, 22 Sep 2017 00:00:00 +1000Perfect Fractional Matchings in $k$-Out Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p60
Extending the notion of (random) $k$-out graphs, we consider when the $k$-out hypergraph is likely to have a perfect fractional matching. In particular, we show that for each $r$ there is a $k=k(r)$ such that the $k$-out $r$-uniform hypergraph on $n$ vertices has a perfect fractional matching with high probability (i.e., with probability tending to $1$ as $n\to\infty$) and prove an analogous result for $r$-uniform $r$-partite hypergraphs. This is based on a new notion of hypergraph expansion and the observation that sufficiently expansive hypergraphs admit perfect fractional matchings. As a further application, we give a short proof of a stopping-time result originally due to Krivelevich.Pat Devlin, Jeff Kahnhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p60Fri, 22 Sep 2017 00:00:00 +1000Rational Dyck Paths in the Non Relatively Prime Case
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p61
We study the relationship between rational slope Dyck paths and invariant subsets of $\mathbb{Z},$ extending the work of the first two authors in the relatively prime case. We also find a bijection between $(dn,dm)$–Dyck paths and $d$-tuples of $(n,m)$-Dyck paths endowed with certain gluing data. These are the first steps towards understanding the relationship between rational slope Catalan combinatorics and the geometry of affine Springer fibers and knot invariants in the non relatively prime case.Eugene Gorsky, Mikhail Mazin, Monica Vaziranihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p61Fri, 22 Sep 2017 00:00:00 +1000Asymptotic Behavior of Odd-Even Partitions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p62
<p>Andrews studied a function which appears in Ramanujan's identities. In Ramanujan's "Lost" Notebook, there are several formulas involving this function, but they are not as simple as the identities with other similar shape of functions. Nonetheless, Andrews found out that this function possesses combinatorial information, odd-even partition. In this paper, we provide the asymptotic formula for this combinatorial object. We also study its companion odd-even overpartitions.</p>Min-Joo Janghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p62Fri, 22 Sep 2017 00:00:00 +1000Unimodal Permutations and Almost-Increasing Cycles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p63
In this paper, we establish a natural bijection between the almost-increasing cyclic permutations of length $n$ and unimodal permutations of length $n-1$. This map is used to give a new characterization, in terms of pattern avoidance, of almost-increasing cycles. Additionally, we use this bijection to enumerate several statistics on almost-increasing cycles. Such statistics include descents, inversions, peaks and excedances, as well as the newly defined statistic called low non-inversions. Furthermore, we refine the enumeration of unimodal permutations by descents, inversions and inverse valleys. We conclude this paper with a theorem that characterizes the standard cycle notation of almost-increasing permutations.Kassie Archer, L.-K. Lauderdalehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p63Fri, 22 Sep 2017 00:00:00 +1000Relative Difference Sets Partitioned by Cosets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p64
We explore classical (relative) difference sets intersected with the cosets of a subgroup of small index. The intersection sizes are governed by quadratic Diophantine equations. Developing the intersections in the subgroup yields an interesting class of group divisible designs. From this and the Bose-Shrikhande-Parker construction, we obtain some new sets of mutually orthogonal latin squares. We also briefly consider optical orthogonal codes and difference triangle systems.Peter J. Dukes, Alan C.H. Linghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p64Fri, 22 Sep 2017 00:00:00 +1000A Conjecture of Norine and Thomas for Abelian Cayley Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p65
A graph $\Gamma_1$ is a matching minor of $\Gamma$ if some even subdivision of $\Gamma_1$ is isomorphic to a subgraph $\Gamma_2$ of $\Gamma$, and by deleting the vertices of $\Gamma_2$ from $\Gamma$ the left subgraph has a perfect matching. Motivated by the study of Pfaffian graphs (the numbers of perfect matchings of these graphs can be computed in polynomial time), we characterized Abelian Cayley graphs which do not contain a $K_{3,3}$ matching minor. Furthermore, the Pfaffian property of Cayley graphs on Abelian groups is completely characterized. This result confirms that the conjecture posed by Norine and Thomas in 2008 for Abelian Cayley graphs is true.Fuliang Lu, Lianzhu Zhanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p65Fri, 22 Sep 2017 00:00:00 +1000Pruned Double Hurwitz Numbers
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p66
Hurwitz numbers count ramified genus $g$, degree $d$ coverings of the projective line with fixed branch locus and fixed ramification data. Double Hurwitz numbers count such covers, where we fix two special profiles over $0$ and $\infty$ and only simple ramification else. These objects feature interesting structural behaviour and connections to geometry. In this paper, we introduce the notion of pruned double Hurwitz numbers, generalizing the notion of pruned simple Hurwitz numbers in Do and Norbury. We show that pruned double Hurwitz numbers, similar to usual double Hurwitz numbers, satisfy a cut-and-join recursion and are piecewise polynomial with respect to the entries of the two special ramification profiles. Furthermore, double Hurwitz numbers can be computed from pruned double Hurwitz numbers. To sum up, it can be said that pruned double Hurwitz numbers count a relevant subset of covers, leading to considerably smaller numbers and computations, but still featuring the important properties we can observe for double Hurwitz numbers.Marvin Anas Hahnhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p66Fri, 22 Sep 2017 00:00:00 +1000