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 +1000