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