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>akundgen@csusm.edu (Andre Kundgen)bdm@cs.anu.edu.au (Brendan McKay)Fri, 20 Jan 2017 13:45:46 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60Majority Bootstrap Percolation on $G(n,p)$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p1
Majority bootstrap percolation on a graph $G$ is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have at least half of its neighbours infected become infected. We say that percolation occurs if eventually all vertices in $G$ become infected.<br /><br />In this paper we provide sharp bounds for the critical size of the initially infected set in majority bootstrap percolation on the Erdős-Rényi random graph $G(n,p)$. This answers an open question by Janson, Luczak, Turova and Vallier (2012). Our results obtained for $p=c\log(n)/n$ are close to the results obtained by Balogh, Bollobás and Morris (2009) for majority bootstrap percolation on the hypercube. We conjecture that similar results will be true for all regular-like graphs with the same density and sufficiently strong expansion properties.Cecilia Holmgren, Tomas Juškevičius, Nathan Kettlehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p1Fri, 20 Jan 2017 00:00:00 +1100Sidorenko's Conjecture, Colorings and Independent Sets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p2
<p>Let $\hom(H,G)$ denote the number of homomorphisms from a graph $H$ to a graph $G$. Sidorenko's conjecture asserts that for any bipartite graph $H$, and a graph $G$ we have<br />$$\hom(H,G)\geq v(G)^{v(H)}\left(\frac{\hom(K_2,G)}{v(G)^2}\right)^{e(H)},$$<br />where $v(H),v(G)$ and $e(H),e(G)$ denote the number of vertices and edges of the graph $H$ and $G$, respectively. In this paper we prove Sidorenko's conjecture for certain special graphs $G$: for the complete graph $K_q$ on $q$ vertices, for a $K_2$ with a loop added at one of the end vertices, and for a path on $3$ vertices with a loop added at each vertex. These cases correspond to counting colorings, independent sets and Widom-Rowlinson colorings of a graph $H$. For instance, for a bipartite graph $H$ the number of $q$-colorings $\mathrm{ch}(H,q)$ satisfies<br />$$\mathrm{ch}(H,q)\geq q^{v(H)}\left(\frac{q-1}{q}\right)^{e(H)}.$$<br />In fact, we will prove that in the last two cases (independent sets and Widom-Rowlinson colorings) the graph $H$ does not need to be bipartite. In all cases, we first prove a certain correlation inequality which implies Sidorenko's conjecture in a stronger form.</p>Péter Csikvári, Zhicong Linhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p2Fri, 20 Jan 2017 00:00:00 +1100Flag Bicolorings, Pseudo-Orientations, and Double Covers of Maps
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p3
This paper discusses consistent flag bicolorings of maps, in their own right and as generalizations of orientations and pseudo-orientations. Furthermore, a related doubling concept is introduced, and relationships between these ideas are explored.Hiroki Koike, Daniel Pellicer, Miguel Raggi, Steve Wilsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p3Fri, 20 Jan 2017 00:00:00 +1100The Polytope of $k$-Star Densities
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p4
This paper describes the polytope $\mathbf{P}_{k;N}$ of $i$-star counts, for all $i\le k$, for graphs on $N$ nodes. The vertices correspond to graphs that are regular or as regular as possible. For even $N$ the polytope is a cyclic polytope, and for odd $N$ the polytope is well-approximated by a cyclic polytope. As $N$ goes to infinity, $\mathbf{P}_{k;N}$ approaches the convex hull of the moment curve. The affine symmetry group of $\mathbf{P}_{k;N}$ contains just a single non-trivial element, which corresponds to forming the complement of a graph.<br /><br />The results generalize to the polytope $\mathbf{P}_{I;N}$ of $i$-star counts, for $i$ in some set $I$ of non-consecutive integers. In this case, $\mathbf{P}_{I;N}$ can still be approximated by a cyclic polytope, but it is usually not a cyclic polytope itself.<br /><br />Polytopes of subgraph statistics characterize corresponding exponential random graph models. The elongated shape of the $k$-star polytope gives a qualitative explanation of some of the degeneracies found in such random graph models.Johannes Rauhhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p4Fri, 20 Jan 2017 00:00:00 +1100Abaci Structures of $(s, ms\pm1)$-Core Partitions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p5
We develop a geometric approach to the study of $(s,ms-1)$-core and $(s,ms+1)$-core partitions through the associated $ms$-abaci. This perspective yields new proofs for results of H. Xiong and A. Straub on the enumeration of $(s, s+1)$ and $(s,ms-1)$-core partitions with distinct parts. It also enumerates $(s, ms+1)$-cores with distinct parts. Furthermore, we calculate the weight of the $(s, ms-1,ms+1)$-core partition with the largest number of parts. Finally we use 2-core partitions to enumerate self-conjugate core partitions with distinct parts. The central idea is that the $ms$-abaci of maximal $(s,ms\pm1)$-cores can be built up from $s$-abaci of $(s,s\pm 1)$-cores in an elegant way.Rishi Nath, James A. Sellershttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p5Fri, 20 Jan 2017 00:00:00 +1100Pattern Avoidance and Young Tableaux
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p6
<p>This paper extends Lewis's bijection (J. Combin. Theorey Ser. A 118, 2011) to a bijection between a more general class $\mathcal{L}(n,k,I)$ of permutations and the set of standard Young tableaux of shape $\langle (k+1)^n\rangle$, so the cardinality<span style="font-size: 10px;">\[</span><span style="font-size: 10px;">|\mathcal{L}(n,k,I)|=f^{\langle (k+1)^n\rangle},</span><span style="font-size: 10px;">\]</span><span style="font-size: 10px;">is independent of the choice of $I\subseteq [n]$. As a consequence, we obtain some new combinatorial realizations and identities on Catalan numbers. In the end, we raise a problem on finding a bijection between $\mathcal{L}(n,k,I)$ and $\mathcal{L}(n,k,I')$ for distinct $I$ and $I'$.</span></p>Zhousheng Mei, Suijie Wanghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p6Fri, 20 Jan 2017 00:00:00 +1100The Extremal Function for Cycles of Length $\ell$ mod $k$
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p7
<p>Burr and Erdős conjectured that for each $k,\ell \in \mathbb Z^+$ such that $k \mathbb Z + \ell$ contains even integers, there exists $c_k(\ell)$ such that any graph of average degree at least $c_k(\ell)$ contains a cycle of length $\ell$ mod $k$. This conjecture was proved by Bollobás, and many successive improvements of upper bounds on $c_k(\ell)$ appear in the literature. In this short note, for $1 \leq \ell \leq k$, we show that $c_k(\ell)$ is proportional to the largest average degree of a $C_{\ell}$-free graph on $k$ vertices, which determines $c_k(\ell)$ up to an absolute constant. In particular, using known results on Turán numbers for even cycles, we obtain $c_k(\ell) = O(\ell k^{2/\ell})$ for all even $\ell$, which is tight for $\ell \in \{4,6,10\}$. Since the complete bipartite graph $K_{\ell - 1,n - \ell + 1}$ has no cycle of length $2\ell$ mod $k$, it also shows $c_k(\ell) = \Theta(\ell)$ for $\ell = \Omega(\log k)$.</p>Benny Sudakov, Jacques Verstraetehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p7Fri, 20 Jan 2017 00:00:00 +1100Enumerating Matroids of Fixed Rank
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p8
<p>It has been conjectured that asymptotically almost all matroids are sparse paving, i.e. that~$s(n) \sim m(n)$, where $m(n)$ denotes the number of matroids on a fixed groundset of size $n$, and $s(n)$ the number of sparse paving matroids. In an earlier paper, we showed that $\log s(n) \sim \log m(n)$. The bounds that we used for that result were dominated by matroids of rank $r\approx n/2$. In this paper we consider the relation between the number of sparse paving matroids $s(n,r)$ and the number of matroids $m(n,r)$ on a fixed groundset of size $n$ of fixed rank $r$. In particular, we show that $\log s(n,r) \sim \log m(n,r)$ whenever $r\ge 3$, by giving asymptotically matching upper and lower bounds.</p><p>Our upper bound on $m(n,r)$ relies heavily on the theory of matroid erections as developed by Crapo and Knuth, which we use to encode any matroid as a stack of paving matroids. Our best result is obtained by relating to this stack of paving matroids an antichain that completely determines the matroid. We also obtain that the collection of essential flats and their ranks gives a concise description of matroids.</p>Rudi Pendavingh, Jorn van der Polhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p8Fri, 20 Jan 2017 00:00:00 +1100Signed Lozenge Tilings
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p9
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p><span style="font-size: 10.000000pt; font-family: 'CMR10';">It is well-known that plane partitions, lozenge tilings of a hexagon, perfect matchings on a honeycomb graph, and families of non-intersecting lattice paths in a hexagon are all in bijection. In this work we consider regions that are more general than hexagons. They are obtained by further removing upward-pointing triangles. We call the resulting shapes triangular regions. We establish signed versions of the latter three bijections for triangular regions. We first investigate the tileability of triangular regions by lozenges. Then we use perfect matchings and families of non-intersecting lattice paths to define two signs of a lozenge tiling. Using a new method that we call resolution of a puncture, we show that the two signs are in fact equivalent. As a consequence, we obtain the equality of determinants, up to sign, that enumerate signed perfect matchings and signed families of lattice paths of a triangular region, respectively. We also describe triangular regions, for which the signed enumerations agree with the unsigned enumerations. </span></p></div></div></div>D. Cook II, Uwe Nagelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p9Fri, 20 Jan 2017 00:00:00 +1100Mixed Ehrhart polynomials
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p10
<p>For lattice polytopes $P_1,\ldots, P_k \subseteq \mathbb{R}^d$, Bihan (2016) introduced the discrete mixed volume $DMV(P_1,\dots,P_k)$ in analogy to the classical mixed volume. In this note we study the associated mixed Ehrhart polynomial $ME_{P_1, \dots,P_k}(n) = DMV(nP_1, \dots, nP_k)$. We provide a characterization of all mixed Ehrhart coefficients in terms of the classical multivariate Ehrhart polynomial. Bihan (2016) showed that the discrete mixed volume is always non-negative. Our investigations yield simpler proofs for certain special cases.<br /><br />We also introduce and study the associated mixed $h^*$-vector. We show that for large enough dilates $r P_1, \ldots, rP_k$ the corresponding mixed $h^*$-polynomial has only real roots and as a consequence the mixed $h^*$-vector becomes non-negative.</p><p> </p>Christian Haase, Martina Juhnke-Kubitzke, Raman Sanyal, Thorsten Theobaldhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p10Fri, 20 Jan 2017 00:00:00 +1100Flow Polynomials as Feynman Amplitudes and their $\alpha$-Representation
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p11
Let $G$ be a connected graph; denote by $\tau(G)$ the set of its spanning trees. Let $\mathbb F_q$ be a finite field, $s(\alpha,G)=\sum_{T\in\tau(G)} \prod_{e \in E(T)} \alpha_e$, where $\alpha_e\in \mathbb F_q$. Kontsevich conjectured in 1997 that the number of nonzero values of $s(\alpha, G)$ is a polynomial in $q$ for all graphs. This conjecture was disproved by Brosnan and Belkale. In this paper, using the standard technique of the Fourier transformation of Feynman amplitudes, we express the flow polynomial $F_G(q)$ in terms of the "correct" Kontsevich formula. Our formula represents $F_G(q)$ as a linear combination of Legendre symbols of $s(\alpha, H)$ with coefficients $\pm 1/q^{(|V(H)|-1)/2}$, where $H$ is a contracted graph of $G$ depending on $\alpha\in \left(\mathbb F^*_q \right)^{E(G)}$, and $|V(H)|$ is odd.Andrey Kuptsov, Eduard Lerner, Sofya Mukhamedjanovahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p11Fri, 20 Jan 2017 00:00:00 +1100An Application of Hoffman Graphs for Spectral Characterizations of Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p12
In this paper, we present the first application of Hoffman graphs for spectral characterizations of graphs. In particular, we show that the 2-clique extension of the $(t+1)\times (t+1)$-grid is determined by its spectrum when $t$ is large enough. This result will help to show that the Grassmann graph $J_2(2D,D)$ is determined by its intersection numbers as a distance regular graph, if $D$ is large enough.Qianqian Yang, Aida Abiad, Jack H. Koolenhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p12Fri, 20 Jan 2017 00:00:00 +1100Rainbow Matchings and Rainbow Connectedness
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p13
<p>Aharoni and Berger conjectured that every collection of $n$ matchings of size $n+1$ in a bipartite graph contains a rainbow matching of size $n$. This conjecture is related to several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares. There have been many recent partial results about the Aharoni-Berger Conjecture. The conjecture is known to hold when the matchings are much larger than $n+1$. The best bound is currently due to Aharoni, Kotlar, and Ziv who proved the conjecture when the matchings are of size at least $3n/2+1$. When the matchings are all edge-disjoint and perfect, the best result follows from a theorem of Häggkvist and Johansson which implies the conjecture when the matchings have size at least $n+o(n)$.<br /> <br />In this paper we show that the conjecture is true when the matchings have size $n+o(n)$ and are all edge-disjoint (but not necessarily perfect). We also give an alternative argument to prove the conjecture when the matchings have size at least $\phi n+o(n)$ where $\phi\approx 1.618$ is the Golden Ratio.</p><p>Our proofs involve studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is new, and perhaps of independent interest.</p>Alexey Pokrovskiyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p13Fri, 03 Feb 2017 00:00:00 +1100On Star Forest Ascending Subgraph Decomposition
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p14
<p>The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph $G$ with ${n+1\choose 2}$ edges admits an edge decomposition $G=H_1\oplus\cdots \oplus H_n$ such that $H_i$ has $i$ edges and it is isomorphic to a subgraph of $H_{i+1}$, $i=1,\ldots ,n-1$. We show that every bipartite graph $G$ with ${n+1\choose 2}$ edges such that the degree sequence $d_1,\ldots ,d_k$ of one of the stable sets satisfies $ d_{k-i}\ge n-i\; \text{for each}\; 0\le i\le k-1$, admits an ascending subgraph decomposition with star forests. We also give a necessary condition on the degree sequence which is not far from the above sufficient one.</p>Josep M. Aroca, Anna Lladóhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p14Fri, 03 Feb 2017 00:00:00 +1100The Maximal Order of Hyper-($b$-ary)-expansions
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p15
<p>Using methods developed by Coons and Tyler, we give a new proof of a recent result of Defant, by determining the maximal order of the number of hyper-($b$-ary)-expansions of a nonnegative integer $n$ for general integral bases $b\geqslant 2$.</p>Michael Coons, Lukas Spiegelhoferhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p15Fri, 03 Feb 2017 00:00:00 +1100New Feasibility Conditions for Directed Strongly Regular Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p16
We prove two results for directed strongly regular graphs that have an eigenvalue of multiplicity less than $k$, the common out-degree of each vertex. The first bounds the size of an independent set, and the second determines an eigenvalue of the subgraph on the out-neighborhood of a vertex. Both lead to new nonexistence results for parameter sets.Sylvia A. Hobart, Jason Willifordhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p16Fri, 03 Feb 2017 00:00:00 +1100On a Permutation Problem for Finite Abelian Groups
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p17
<p>Let $G$ be a finite additive abelian group with exponent $n>1$, and let $a_1,\ldots,a_{n-1}$ be elements of $G$. We show that there is a permutation $\sigma\in S_{n-1}$ such that all the elements $sa_{\sigma(s)}\ (s=1,\ldots,n-1)$ are nonzero if and only if<br />$$\left|\left\{1\leqslant s<n:\ \frac{n}da_s\not=0\right\}\right|\geqslant d-1\ \ \mbox{for any positive divisor}\ d\ \mbox{of}\ n.$$<br />When $G$ is the cyclic group $\mathbb Z/n\mathbb Z$, this confirms a conjecture of Z.-W. Sun.</p><p> </p>Fan Ge, Zhi-Wei Sunhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p17Fri, 03 Feb 2017 00:00:00 +1100Partitioning Random Graphs into Monochromatic Components
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p18
<pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">Erdős</span><span style="color: #000000;">, </span><span style="color: #000000;">Gyárfás</span><span style="color: #800000;">,</span><span style="color: #000000;"> and </span><span style="color: #000000;">Pyber (1991) conjectured that every </span><span style="color: #008000;">$r$</span><span style="color: #000000;">-colored complete graph can be partitioned into at most </span><span style="color: #008000;">$r-1$</span><span style="color: #000000;"> monochromatic components; this is a strengthening of a conjecture of </span><span style="color: #000000;">Lov</span><span><span style="color: #800000;">ász</span></span><span style="color: #000000;"> (1975) </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">and </span><span style="color: #000000;">Ryser (1970) in which the components are only required to form a cover. An important partial result of </span><span style="color: #000000;">Haxell</span><span style="color: #000000;"> and </span><span style="color: #000000;">Kohayakawa</span><span style="color: #000000;"> (1995) </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">shows that a partition into </span><span style="color: #008000;">$r$</span><span style="color: #000000;"> monochromatic components is possible for sufficiently large </span><span style="color: #008000;">$r$</span><span style="color: #000000;">-colored complete graphs.</span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;"><br /><br />We start by extending </span><span style="color: #000000;">Haxell</span><span style="color: #000000;"> and </span><span style="color: #000000;">Kohayakawa's</span><span style="color: #000000;"> result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if </span><span style="color: #008000;">$p\ge \left(\frac{27\log n}{n}\right)^{1/3}$</span><span style="color: #000000;">, then a.a.s. in every </span><span style="color: #008000;">$2$</span><span style="color: #000000;">-coloring of </span><span style="color: #008000;">$G(n,p)$</span><span style="color: #000000;"> there exists a partition into two monochromatic components, and for </span><span style="color: #008000;">$r\geq 2$</span><span style="color: #000000;"> if </span><span style="color: #008000;">$p\ll \left(\frac{r\log n}{n}\right)^{1/r}$</span><span style="color: #000000;">, then a.a.s. there exists an </span><span style="color: #008000;">$r$</span><span style="color: #000000;">-coloring of </span><span style="color: #008000;">$G(n,p)$</span><span style="color: #000000;"> such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of </span><span>Gyárfá<span style="color: #800000;">s </span></span><span style="color: #000000;">(1977) about large monochromatic components in </span><span style="color: #008000;">$r$</span><span style="color: #000000;">-colored complete graphs. We show that if </span><span style="color: #008000;">$p=\frac{\omega(1)}{n}$</span><span style="color: #000000;">, then a.a.s. in every </span><span style="color: #008000;">$r$</span><span style="color: #000000;">-coloring of </span><span style="color: #008000;">$G(n,p)$</span><span style="color: #000000;"> there exists a monochromatic component of order at least </span><span style="color: #008000;">$(1-o(1))\frac{n}{r-1}$</span><span style="color: #000000;">.</span></pre>Deepak Bal, Louis DeBiasiohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p18Fri, 03 Feb 2017 00:00:00 +1100(Total) Domination in Prisms
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p19
Using hypergraph transversals it is proved that $\gamma_t(Q_{n+1}) = 2\gamma(Q_n)$, where $\gamma_t(G)$ and $\gamma(G)$ denote the total domination number and the domination number of $G$, respectively, and $Q_n$ is the $n$-dimensional hypercube. More generally, it is shown that if $G$ is a bipartite graph, then $\gamma_t(G \square K_2) = 2\gamma(G)$. Further, we show that the bipartiteness condition is essential by constructing, for any $k \ge 1$, a (non-bipartite) graph $G$ such that $\gamma_t(G\square K_2) = 2\gamma(G) - k$. Along the way several domination-type identities for hypercubes are also obtained.Jernej Azarija, Michael Henning, Sandi Klavžarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p19Fri, 03 Feb 2017 00:00:00 +1100Permutations that Destroy Arithmetic Progressions in Elementary $p$-Groups
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p20
<p>Given an abelian group $G$, it is natural to ask whether there exists a permutation $\pi$ of $G$ that "destroys" all nontrivial 3-term arithmetic progressions (APs), in the sense that $\pi(b) - \pi(a) \neq \pi(c) - \pi(b)$ for every ordered triple $(a,b,c) \in G^3$ satisfying $b-a = c-b \neq 0$. This question was resolved for infinite groups $G$ by Hegarty, who showed that there exists an AP-destroying permutation of $G$ if and only if $G/\Omega_2(G)$ has the same cardinality as $G$, where $\Omega_2(G)$ denotes the subgroup of all elements in $G$ whose order divides $2$. In the case when $G$ is finite, however, only partial results have been obtained thus far. Hegarty has conjectured that an AP-destroying permutation of $G$ exists if $G = \mathbb{Z}/n\mathbb{Z}$ for all $n \neq 2,3,5,7$, and together with Martinsson, he has proven the conjecture for all $n > 1.4 \times 10^{14}$. In this paper, we show that if $p$ is a prime and $k$ is a positive integer, then there is an AP-destroying permutation of the elementary $p$-group $(\mathbb{Z}/p\mathbb{Z})^k$ if and only if $p$ is odd and $(p,k) \not\in \{(3,1),(5,1), (7,1)\}$.</p>Noam D. Elkies, Ashvin A. Swaminathanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p20Fri, 03 Feb 2017 00:00:00 +1100Algebraic Properties of Chromatic Roots
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p21
<p>A chromatic root is a root of the chromatic polynomial of a graph. Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008. The purpose of this paper is to report on the seminar and subsequent developments.</p><p>We conjecture that, for every algebraic integer $\alpha$, there is a natural number n such that $\alpha+n$ is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one "interesting" factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.</p>Peter J. Cameron, Kerri Morganhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p21Fri, 03 Feb 2017 00:00:00 +1100Paths vs. Stars in the Local Profile of Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p22
The aim of this paper is to provide an affirmative answer to a recent question by Bubeck and Linial on the local profile of trees. For a tree $T$, let $p^{(k)}_1(T)$ be the proportion of paths among all $k$-vertex subtrees (induced connected subgraphs) of $T$, and let $p^{(k)}_2(T)$ be the proportion of stars. Our main theorem states: if $p^{(k)}_1(T_n) \to 0$ for a sequence of trees $T_1,T_2,\ldots$ whose size tends to infinity, then $p^{(k)}_2(T_n) \to 1$. Both are also shown to be equivalent to the statement that the number of $k$-vertex subtrees grows superlinearly and the statement that the $(k-1)$th degree moment grows superlinearly.Éva Czabarka, László Székely, Stephan Wagnerhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p22Fri, 03 Feb 2017 00:00:00 +1100Colorful Subhypergraphs in Uniform Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p23
<p><br />There are several topological results ensuring in any properly colored graph the existence of a colorful complete bipartite subgraph, whose order is bounded from below by some topological invariants of some topological spaces associated to the graph. Meunier [<em>Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal </em><em>of Combinatorics,</em> 2014] presented the first colorful type result for uniform hypergraphs. In this paper, we give some new generalizations of the $\mathbb{Z}_p$-Tucker lemma and by use of them, we improve Meunier's result and some other colorful results by Simonyi, Tardif, and Zsbán [<em>Colourful theorems and indices of homomorphism complexes, </em><em>The Electronic Journal of Combinatorics,</em> 2014] and by Simonyi and Tardos [<em>Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics,</em> 2007] to uniform hypergraphs. Also, we introduce some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs. A hierarchy between these lower bounds is presented as well.</p>Meysam Alishahihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p23Fri, 03 Feb 2017 00:00:00 +1100On the Number of $r$-Matchings in a Tree
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p24
<p><!--StartFragment-->An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. This generalizes both matchings and induced matchings as matchings are $1$-matchings and induced matchings are $2$-matchings. In this paper, we study the minimum and maximum number of $r$-matchings in a tree with fixed order.<!--EndFragment--></p>Dong Yeap Kang, Jaehoon Kim, Younjin Kim, Hiu-Fai Lawhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p24Fri, 03 Feb 2017 00:00:00 +1100Permanent Index of Matrices Associated with Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p25
<p>A total weighting of a graph $G$ is a mapping $f$ which assigns to each element $z \in V(G) \cup E(G)$ a real number $f(z)$ as its weight. The vertex sum of $v$ with respect to $f$ is $\phi_f(v)=\sum_{e \in E(v)}f(e)+f(v)$. A total weighting is proper if $\phi_f(u) \ne \phi_f(v)$ for any edge $uv$ of $G$. A $(k,k')$-list assignment is a mapping $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ permissible weights, and assigns to each edge $e$ a set $L(e)$ of $k'$ permissible weights. We say $G$ is $(k,k')$-choosable if for any $(k,k')$-list assignment $L$, there is a proper total weighting $f$ of $G$ with $f(z) \in L(z)$ for each $z \in V(G) \cup E(G)$. It was conjectured in [T. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] that every graph is $(2,2)$-choosable and every graph with no isolated edge is $(1,3)$-choosable. A promising tool in the study of these conjectures is Combinatorial Nullstellensatz. This approach leads to conjectures on the permanent indices of matrices $A_G$ and $B_G$ associated to a graph $G$. In this paper, we establish a method that reduces the study of permanent of matrices associated to a graph $G$ to the study of permanent of matrices associated to induced subgraphs of $G$. Using this reduction method, we show that if $G$ is a subcubic graph, or a $2$-tree, or a Halin graph, or a grid, then $A_G$ has permanent index $1$. As a consequence, these graphs are $(2,2)$-choosable.</p>Tsai-Lien Wong, Xuding Zhuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p25Fri, 17 Feb 2017 00:00:00 +1100A General Method to Determine Limiting Optimal Shapes for Edge-Isoperimetric Inequalities
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p26
For a general family of graphs on $\mathbb{Z}^n$, we translate the edge-isoperimetric problem into a continuous isoperimetric problem in $\mathbb{R}^n$. We then solve the continuous isoperimetric problem using the Brunn-Minkowski inequality and Minkowski's theorem on mixed volumes. This translation allows us to conclude, under a reasonable assumption about the discrete problem, that the shapes of the optimal sets in the discrete problem approach the shape of the optimal set in the continuous problem as the size of the set grows. The solution is the zonotope defined as the Minkowski sum of the edges of the original graph. <br /><br />We demonstrate the efficacy of this method by revisiting some previously solved classical edge-isoperimetric problems. We then apply our method to some discrete isoperimetric problems which had not previously been solved. The complexity of those solutions suggest that it would be quite difficult to find them using discrete methods only.Ellen Veomett, Emmanuel Tsukermanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p26Fri, 17 Feb 2017 00:00:00 +1100On the Multicolor Ramsey Number for 3-Paths of Length Three
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p27
<p>We show that if we color the hyperedges of the complete $3$-uniform hypergraph on $2n+\sqrt{18n+1}+2$ vertices with $n$ colors, then one of the color classes contains a loose path of length three.</p>Tomasz Łuczak, Joanna Polcynhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p27Fri, 17 Feb 2017 00:00:00 +1100Small Subgraphs in the Trace of a Random Walk
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p28
We consider the combinatorial properties of the trace of a random walk on the complete graph and on the random graph $G(n,p)$. In particular, we study the appearance of a fixed subgraph in the trace. We prove that for a subgraph containing a cycle, the threshold for its appearance in the trace of a random walk of length $m$ is essentially equal to the threshold for its appearance in the random graph drawn from $G(n,m)$. In the case where the base graph is the complete graph, we show that a fixed forest appears in the trace typically much earlier than it appears in $G(n,m)$.<br /><br />Michael Krivelevich, Peleg Michaelihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p28Fri, 17 Feb 2017 00:00:00 +1100Symmetric Graphs with Respect to Graph Entropy
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p29
<pre><!--StartFragment--> Let <span>$F_G(P)$</span> be a functional defined on the set of all the probability distributions on the vertex set of a graph <span>$G$</span>. We say that <span>$G$</span> is <em>symmetric with respect to</em> <span>$F_G(P)$</span> if the uniform distribution on <span>$V(G)$</span> maximizes <span>$F_G(P)$</span>. Using the <span>combinatorial</span> definition of the entropy of a graph in terms of its vertex packing <span>polytope</span> and the relationship between the graph entropy and fractional chromatic number, we characterize all graphs which are symmetric with respect to graph entropy. We show that a graph is symmetric with respect to graph entropy if and only if its vertex set can be uniformly covered by its maximum size independent sets. This is also equivalent to saying that the fractional chromatic number of $G$, $\chi_f(G)$, is equal to $\frac{n}{\alpha(G)}$, where $n = |V(G)|$ and $\alpha(G)$ is the independence number of $G$. Furthermore, given any strictly positive probability distribution <span>$P$</span> on the vertex set of a graph <span>$G$</span>, we show that <span>$P$</span> is a <span>maximizer</span> of the entropy of graph <span>$G$</span> if and only if its vertex set can be uniformly covered by its maximum weighted independent sets. We also show that the problem of deciding if a graph is symmetric with respect to graph entropy, where the weight of the <span>vertices</span> is given by probability distribution <span>$P$</span>, is co-NP-hard.<!--EndFragment--></pre>Seyed Saeed Changiz Rezaei, Ehsan Chiniforooshanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p29Fri, 17 Feb 2017 00:00:00 +1100Rigged Configurations for all Symmetrizable Types
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p30
In an earlier work, the authors developed a rigged configuration model for the crystal $B(\infty)$ (which also descends to a model for irreducible highest weight crystals via a cutting procedure). However, the result obtained was only valid in finite types, affine types, and simply-laced indefinite types. In this paper, we show that the rigged configuration model proposed does indeed hold for all symmetrizable types. As an application, we give an easy combinatorial condition that gives a Littlewood-Richardson rule using rigged configurations which is valid in all symmetrizable Kac-Moody types.Ben Salisbury, Travis Scrimshawhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p30Fri, 17 Feb 2017 00:00:00 +1100Elliptic Rook and File Numbers
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p31
Utilizing elliptic weights, we construct an elliptic analogue of rook numbers for Ferrers boards. Our elliptic rook numbers generalize Garsia and Remmel's $q$-rook numbers by two additional independent parameters $a$ and $b$, and a nome $p$. The elliptic rook numbers are shown to satisfy an elliptic extension of a factorization theorem which in the classical case was established by Goldman, Joichi and White and extended to the $q$-case by Garsia and Remmel. We obtain similar results for elliptic analogues of Garsia and Remmel's $q$-file numbers for skyline boards. We also provide an elliptic extension of the $j$-attacking model introduced by Remmel and Wachs. Various applications of our results include elliptic analogues of (generalized) Stirling numbers of the first and second kind, Lah numbers, Abel numbers, and $r$-restricted versions thereof.Michael J. Schlosser, Meesue Yoohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p31Fri, 17 Feb 2017 00:00:00 +1100Anti-Power Prefixes of the Thue-Morse Word
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p32
<pre>Recently, <span>Fici</span>, <span>Restivo</span>, Silva, and Zamboni defined a <span>$k$</span>-anti-power to be a word of the form <span>$w_1w_2\cdots w_k$</span>, where <span>$w_1,w_2,\ldots,w_k$</span> are distinct words of the same length. They defined <span>$AP(x,k)$</span> to be the set of all positive integers <span>$m$</span> such that the prefix of length <span>$km$</span> of the word <span>$x$</span> is a <span>$k$</span>-anti-power. Let <span>${\bf t}$</span> denote the <span>Thue</span>-Morse word, and let <span>$\mathcal F(k)=AP({\bf t},k)\cap(2\mathbb Z^+-1)$</span>. For <span>$k\geq 3$</span>, <span>$\gamma(k)=\min(\mathcal F(k))$</span> and <span>$\Gamma(k)=\max((2\mathbb Z^+-1)\setminus\mathcal F(k))$</span> are well-defined odd positive integers. <span>Fici</span> <span>et</span> <span>al</span>. speculated that <span>$\gamma(k)$</span> grows linearly in <span>$k$</span>. We prove that this is indeed the case by showing that <span>$1/2\leq\displaystyle{\liminf_{k\to\infty}}(\gamma(k)/k)\leq 9/10$</span> and <span>$1\leq\displaystyle{\limsup_{k\to\infty}}(\gamma(k)/k)\leq 3/2$</span>. In addition, we prove that <span>$\displaystyle{\liminf_{k\to\infty}}(\Gamma(k)/k)=3/2$</span> and <span>$\displaystyle{\limsup_{k\to\infty}}(\Gamma(k)/k)=3$</span>. </pre>Colin Defanthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p32Fri, 17 Feb 2017 00:00:00 +1100Refining the Hierarchies of Classes of Geometric Intersection Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p33
<pre>We analyse properties of geometric intersection graphs to show the strict containment between some natural classes of geometric intersection graphs. In particular, we show the following properties:</pre><ul><li>A graph $G$ is outerplanar if and only if the 1-subdivision of $G$ is outer-segment.</li><li>For each integer $k\ge 1$, the class of intersection graphs of segments with $k$ different lengths is a strict subclass of the class of intersection graphs of segments with $k+1$ different lengths.</li><li>For each integer $k\ge 1$, the class of intersection graphs of disks with $k$ different sizes is a strict subclass of the class of intersection graphs of disks with $k+1$ different sizes.</li><li>The class of outer-segment graphs is a strict subclass of the class of outer-string graphs.</li></ul>Sergio Cabello, Miha Jejčičhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p33Fri, 17 Feb 2017 00:00:00 +1100Rainbow Turán Problems for Paths and Forests of Stars
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p34
<p>For a fixed graph $F$, we would like to determine the maximum number of edges in a properly edge-colored graph on $n$ vertices which does not contain a <em>rainbow copy</em> of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^*(n,F)$, is the <em>rainbow Tur<span>á</span>n number</em> of $F$, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstra<span>ë</span>te [<em>Combinatorics, Probability and Computing</em> <strong>16</strong> (2007)]. We determine $ex^*(n,F)$ exactly when $F$ is a forest of stars, and give bounds on $ex^*(n,F)$ when $F$ is a path with $l$ edges, disproving a conjecture in the aforementioned paper for $l=4$.</p>Daniel Johnston, Cory Palmer, Amites Sarkarhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p34Fri, 17 Feb 2017 00:00:00 +1100Strong Games Played on Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p35
<pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">In a strong game played on the edge set of a graph </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> there are two players, Red and Blue, alternating turns in claiming previously </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">unclaimed edges of </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">clique </span><span style="color: #008000;">$K_k$</span><span style="color: #000000;">, a perfect matching, a Hamilton cycle, etc.). </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;"><br /></span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">In this paper we consider strong games played on the edge set of a random graph </span><span style="color: #008000;">$G</span><span style="color: #008000;">\sim G(n,p)$</span><span> on </span><span style="color: #008000;">$n$</span><span> vertices. We prove that </span><span style="color: #008000;">$G\sim G(n,p)$</span><span> is typically such that Red can win the perfect </span><span>matching game played on </span><span style="color: #008000;">$E(G)$</span><span>, provided that </span><span style="color: #008000;">$p\in(0,1)$</span><span> is a fixed constant.</span></pre><pre style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </pre>Asaf Ferber, Pascal Pfisterhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p35Fri, 17 Feb 2017 00:00:00 +1100Ramsey Numbers of Connected Clique Matchings
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p36
<p>We determine the Ramsey number of a connected clique matching. That is, we show that if $G$ is a $2$-edge-coloured complete graph on $(r^2-r-1)n-r+1$ vertices, then there is a monochromatic connected subgraph containing $n$ disjoint copies of $K_r$, and that this number of vertices cannot be reduced.</p>Barnaby Robertshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p36Fri, 17 Feb 2017 00:00:00 +1100The Three Colour Hat Guessing Game on Cycle Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p37
<p>We study a cooperative game in which each member of a team of <em>N</em> players, wearing coloured hats and situated at the vertices of the cycle graph with <em>N</em> vertices, is guessing their own hat colour merely on the basis of observing the hats worn by their two neighbours without exchanging the information. Each hat can have one of three colours. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colours. We prove that a winning strategy exists if and only if <em>N</em> is divisible by 3 or <em>N =</em> 4. This asymmetric game is an example of relational system using incomplete information about an unpredictable situation, where at least one participant has to act properly.</p>Witold Szczechlahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p37Fri, 17 Feb 2017 00:00:00 +1100A $q$-Analog of Foulkes' Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p38
We propose a $q$-analog of classical plethystic conjectures due to Foulkes. In our conjectures, a divided difference of plethysms of Hall-Littlewood polynomials $H_n(\boldsymbol{x};q)$ replaces the analogous difference of plethysms of complete homogeneous symmetric functions $h_n(\boldsymbol{x})$ in Foulkes' conjecture. At $q=0$, we get back the original statement of Foulkes, and we show that our version holds at $q=1$. We discuss further supporting evidence, as well as various generalizations, including a $(q,t)$-version.François Bergeronhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p38Fri, 17 Feb 2017 00:00:00 +1100Inversion Generating Functions for Signed Pattern Avoiding Permutations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p39
We consider the classical Mahonian statistics on the set $B_n(\Sigma)$ of signed permutations in the hyperoctahedral group $B_n$ which avoid all patterns in $\Sigma$, where $\Sigma$ is a set of patterns of length two. In 2000, Simion gave the cardinality of $B_n(\Sigma)$ in the cases where $\Sigma$ contains either one or two patterns of length two and showed that $\left|B_n(\Sigma)\right|$ is constant whenever $\left|\Sigma\right|=1$, whereas in most but not all instances where $\left|\Sigma\right|=2$, $\left|B_n(\Sigma)\right|=(n+1)!$. We answer an open question of Simion by providing bijections from $B_n(\Sigma)$ to $S_{n+1}$ in these cases where $\left|B_n(\Sigma)\right|=(n+1)!$. In addition, we extend Simion's work by providing a combinatorial proof in the language of signed permutations for the major index on $B_n(21, \bar{2}\bar{1})$ and by giving the major index on $D_n(\Sigma)$ for $\Sigma =\{21, \bar{2}\bar{1}\}$ and $\Sigma=\{12,21\}$. The main result of this paper is to give the inversion generating functions for $B_n(\Sigma)$ for almost all sets $\Sigma$ with $\left|\Sigma\right|\leq2.$Naiomi T. Cameron, Kendra Killpatrickhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p39Fri, 17 Feb 2017 00:00:00 +1100