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)Thu, 13 Apr 2017 10:37:13 +1000OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60A Construction of Uniquely $n$-Colorable Digraphs with Arbitrarily Large Digirth
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p1
A natural digraph analogue of the graph-theoretic concept of an `independent set' is that of an `acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets and we say a digraph is uniquely $n$-colorable when this decomposition is unique up to relabeling. It was shown probabilistically in [A. Harutyunyan et al., Uniquely $D$-colorable digraphs with large girth, Canad. J. Math., <strong>64</strong>(6): 1310-1328, 2012] that there exist uniquely $n$-colorable digraphs with arbitrarily large girth. Here we give a construction of such digraphs and prove that they have circular chromatic number $n$. The graph-theoretic notion of `homomorphism' also gives rise to a digraph analogue. An acyclic homomorphism from a digraph $D$ to a digraph $H$ is a mapping $\varphi: V(D) \rightarrow V(H)$ such that $uv \in A(D)$ implies that either $\varphi(u)\varphi(v) \in A(H)$ or $\varphi(u)=\varphi(v)$, and all the `fibers' $\varphi^{-1}(v)$, for $v \in V(H)$, of $\varphi$ are acyclic. In this language, a core is a digraph $D$ for which there does not exist an acyclic homomorphism from $D$ to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.Michael Severinohttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p1Thu, 13 Apr 2017 00:00:00 +1000Chromatic Symmetric Functions of Hypertrees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p2
The chromatic symmetric function $X_H$ of a hypergraph $H$ is the sum of all monomials corresponding to proper colorings of $H$. When $H$ is an ordinary graph, it is known that $X_H$ is positive in the fundamental quasisymmetric functions $F_S$, but this is not the case for general hypergraphs. We exhibit a class of hypergraphs $H$ <span>—</span> hypertrees with prime-sized edges <span>—</span> for which $X_H$ is $F$-positive, and give an explicit combinatorial interpretation for the $F$-coefficients of $X_H$.Jair Taylorhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p2Thu, 13 Apr 2017 00:00:00 +1000Counting Outerplanar Maps
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p3
<p>A map is outerplanar if all its vertices lie in the outer face. We enumerate various classes of rooted outerplanar maps with respect to the number of edges and vertices. The proofs involve several bijections with lattice paths. As a consequence of our results, we obtain an efficient scheme for encoding simple outerplanar maps.</p>Ivan Geffner, Marc Noyhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p3Thu, 13 Apr 2017 00:00:00 +1000Strong Emergence of Wave Patterns on Kadanoff Sandpiles
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p4
Emergence is easy to exhibit, but very hard to formally explain. This paper deals with square sand grains moving around on nicely stacked columns in one dimension (the physical sandpile is two dimensional, but the support of sand columns is one dimensional). The Kadanoff sandpile model is a discrete dynamical system describing the evolution of finitely many sand grains falling from an hourglass (or equivalently from a finite stack of sand grains) to a stable configuration. The repeated application of a simple local rule let grains move until reaching a fixed point. The difficulty of understanding its behavior, despite the simplicity of its rule, is the main interest of the model. In this paper we prove the emergence of exact wave patterns periodically repeated on fixed points. Remarkably, those regular patterns do not cover the entire fixed point, but eventually <em>emerge</em> from a seemingly disordered segment: grains are added on the left, triggering avalanches that become regular as they fall down the sandpile. The proof technique we set up associated arguments of linear algebra and combinatorics, which interestingly allow to formally demonstrate the emergence of regular patterns without requiring a precise understanding of the non-regular initial segment's dynamic.Kévin Perrot, Eric Rémilahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p4Thu, 13 Apr 2017 00:00:00 +1000Large Cliques in Sparse Random Intersection Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p5
An intersection graph defines an adjacency relation between subsets $S_1,\dots, S_n$ of a finite set $W=\{w_1,\dots, w_m\}$: the subsets $S_i$ and $S_j$ are adjacent if they intersect. Assuming that the subsets are drawn independently at random according to the probability distribution $\mathbb{P}(S_i=A)=P(|A|){\binom{m}{|A|}}^{-1}$, $A\subseteq W$, where $P$ is a probability on $\{0, 1, \dots, m\}$, we obtain the random intersection graph $G=G(n,m,P)$. We establish the asymptotic order of the clique number $\omega(G)$ of a sparse random intersection graph as $n,m\to+\infty$. For $m = \Theta(n)$ we show that the maximum clique is of size $(1-\alpha/2)^{-\alpha/2}n^{1-\alpha/2}(\ln n)^{-\alpha/2}(1+o_P(1))$ in the case where the asymptotic degree distribution of $G$ is a power-law with exponent $\alpha \in (1,2)$. It is of size $\frac {\ln n} {\ln \ln n}(1+o_P(1))$ if the degree distribution has bounded variance, i.e., $\alpha>2$. We construct a simple polynomial-time algorithm which finds a clique of the optimal order $\omega(G) (1-o_P(1))$.<br /><br />Mindaugas Bloznelis, Valentas Kurauskashttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p5Thu, 13 Apr 2017 00:00:00 +1000Small Feedback Vertex Sets in Planar Digraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p6
<p>Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $g\ge 4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|\le \tfrac{5n-5}9$ if $g=4$, $|X|\le \tfrac{2n-5}4$ if $g=5$, and $|X|\le \tfrac{2n-6}{g}$ if $g\ge 6$. This improves recent results of Golowich and Rolnick.</p>Louis Esperet, Laetitia Lemoine, Frédéric Maffrayhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p6Thu, 13 Apr 2017 00:00:00 +1000A New Bijective Proof of Babson and Steingrímsson's Conjecture
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p7
<p>Babson and Steingrímsson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Given a permutation $\pi$, let $des(\pi)$ denote the descent number of $\pi$ and $maj(\pi)$ denote the major index of $\pi$. Babson and Steingrímsson conjectured that $(des,stat)$ and $(des,maj)$ are equidistributed on $S_n$. Foata and Zeilberger settled this conjecture using q-enumeration, generating functions and Maple packages ROTA and PERCY. Later, Burstein provided a bijective proof of a refinement of this conjecture. In this paper, we give a new bijective proof of this conjecture.</p>Joanna N. Chen, Shouxiao Lihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p7Thu, 13 Apr 2017 00:00:00 +1000Neighborhood Reconstruction and Cancellation of Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p8
<p>We connect two seemingly unrelated problems in graph theory.</p><p>Any graph $G$ has a <em>neighborhood multiset</em> $\mathscr{N}(G)= \{N(x) \mid x\in V(G)\}$ whose elements are precisely the open vertex-neighborhoods of $G$. In general there exist non-isomorphic graphs $G$ and $H$ for which $\mathscr{N}(G)=\mathscr{N}(H)$. The <em>neighborhood reconstruction problem</em> asks the conditions under which $G$ is uniquely reconstructible from its neighborhood multiset, that is, the conditions under which $\mathscr{N}(G)=\mathscr{N}(H)$ implies $G\cong H$. Such a graph is said to be <em>neighborhood-reconstructible</em>.</p><p>The <em>cancellation problem</em> for the direct product of graphs seeks the conditions under which $G\times K\cong H\times K$ implies $G\cong H$. Lov<span>á</span>sz proved that this is indeed the case if $K$ is not bipartite. A second instance of the cancellation problem asks for conditions on $G$ that assure $G\times K\cong H\times K$ implies $G\cong H$ for any bipartite~$K$ with $E(K)\neq \emptyset$. A graph $G$ for which this is true is called a <em>cancellation graph</em>.</p><p>We prove that the neighborhood-reconstructible graphs are precisely the cancellation graphs. We also present some new results on cancellation graphs, which have corresponding implications for neighborhood reconstruction. We are particularly interested in the (yet-unsolved) problem of finding a simple structural characterization of cancellation graphs (equivalently, neighborhood-reconstructible graphs).</p>Richard H. Hammack, Cristina Mullicanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p8Thu, 13 Apr 2017 00:00:00 +1000On $xD$-Generalizations of Stirling Numbers and Lah Numbers via Graphs and Rooks
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p9
This paper studies the generalizations of the Stirling numbers of both kinds and the Lah numbers in association with the normal ordering problem in the Weyl algebra $W=\langle x,D|Dx-xD=1\rangle$. Any word $\omega\in W$ with $m$ $x$'s and $n$ $D$'s can be expressed in the normally ordered form $\omega=x^{m-n}\sum_{k\ge 0} {{\omega}\brace {k}} x^{k}D^{k}$, where ${{\omega}\brace {k}}$ is known as the Stirling number of the second kind for the word $\omega$. This study considers the expansions of restricted words $\omega$ in $W$ over the sequences $\{(xD)^{k}\}_{k\ge 0}$ and $\{xD^{k}x^{k-1}\}_{k\ge 0}$. Interestingly, the coefficients in individual expansions turn out to be generalizations of the Stirling numbers of the first kind and the Lah numbers. The coefficients will be determined through enumerations of some combinatorial structures linked to the words $\omega$, involving decreasing forest decompositions of quasi-threshold graphs and non-attacking rook placements on Ferrers boards. Extended to $q$-analogues, weighted refinements of the combinatorial interpretations are also investigated for words in the $q$-deformed Weyl algebra.Sen-Peng Eu, Tung-Shan Fu, Yu-Chang Liang, Tsai-Lien Wonghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p9Thu, 13 Apr 2017 00:00:00 +1000The Coupling Method for Inhomogeneous Random Intersection Graphs.
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p10
We present new results concerning threshold functions for a wide family of random intersection graphs. To this end we improve and generalize the coupling method introduced for random intersection graphs so that it may be used for a wider range of parameters. Using the new approach we are able to tighten the best known results concerning random intersection graphs and establish threshold functions for some monotone properties of inhomogeneous random intersection graphs. Considered properties are: $k$-connectivity, matching containment and hamiltonicity.Katarzyna Rybarczykhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p10Thu, 13 Apr 2017 00:00:00 +1000Juxtaposing Catalan Permutation Classes with Monotone Ones
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p11
<div class="page" title="Page 1"><div class="layoutArea"><div class="column"><p>This paper enumerates all juxtaposition classes of the form "$\mathrm{Av}(abc)$ next to $\mathrm{Av}(xy)$", where $abc$ is a permutation of length three and $xy$ is a permutation of length two. We use Dyck paths decorated by sequences of points to represent elements from such a juxtaposition class. Context free grammars are then used to enumerate these decorated Dyck paths.</p></div></div></div>Robert Brignall, Jakub Sliačanhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p11Thu, 13 Apr 2017 00:00:00 +1000Maximal Partial Spreads of Polar Spaces
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p12
Some constructions of maximal partial spreads of finite classical polar spaces are provided. In particular we show that, for $n \ge 1$, $\mathcal{H}(4n-1,q^2)$ has a maximal partial spread of size $q^{2n}+1$, $\mathcal{H}(4n+1,q^2)$ has a maximal partial spread of size $q^{2n+1}+1$ and, for $n \ge 2$, $\mathcal{Q}^+(4n-1,q)$, $\mathcal{Q}(4n-2,q)$, $\mathcal{W}(4n-1,q)$, $q$ even, $\mathcal{W}(4n-3,q)$, $q$ even, have a maximal partial spread of size $q^n+1$.Antonio Cossidente, Francesco Pavesehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p12Thu, 13 Apr 2017 00:00:00 +1000Forbidden Pairs with a Common Graph Generating Almost the Same Sets
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p13
<p>Let $\mathcal{H}$ be a family of connected graphs. A graph $G$ is said to be $\mathcal{H}$-free if $G$ does not contain any members of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{F}(\mathcal{H})$ be the family of connected $\mathcal{H}$-free graphs. In this context, the members of $\mathcal{H}$ are called forbidden subgraphs.</p><p>In this paper, we focus on two pairs of forbidden subgraphs containing a common graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $H_{1}$ is twin-less. If the symmetric difference of $\mathcal{F}(\{H_{1},H_{2}\})$ and $\mathcal{F}(\{H_{1},H_{3}\})$ is finite and the tuple $(H_{1};H_{2},H_{3})$ is non-trivial in a sense, then $H_{2}$ and $H_{3}$ are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [Combin. Probab. Comput. <strong>22</strong> (2013) 733<span>–</span>748] concerning forbidden pairs.</p>Shuya Chiba, Jun Fujisawa, Michitaka Furuya, Hironobu Ikarashihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p13Thu, 13 Apr 2017 00:00:00 +1000On Spherical Designs of Some Harmonic Indices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p14
<p>A finite subset $Y$ on the unit sphere $S^{n-1} \subseteq \mathbb{R}^n$ is called a spherical design of harmonic index $t$, if the following condition is satisfied: $\sum_{\mathbf{x}\in Y}f(\mathbf{x})=0$ for all real homogeneous harmonic polynomials $f(x_1,\ldots,x_n)$ of degree $t$. Also, for a subset $T$ of $\mathbb{N} = \{1,2,\cdots \}$, a finite subset $Y \subseteq S^{n-1}$ is called a spherical design of harmonic index $T,$ if $\sum_{\mathbf{x}\in Y}f(\mathbf{x})=0$ is satisfied for all real homogeneous harmonic polynomials $f(x_1,\ldots,x_n)$ of degree $k$ with $k\in T$.</p><p>In the present paper we first study Fisher type lower bounds for the sizes of spherical designs of harmonic index $t$ (or for harmonic index $T$). We also study `tight' spherical designs of harmonic index $t$ or index $T$. Here `tight' means that the size of $Y$ attains the lower bound for this Fisher type inequality. The classification problem of tight spherical designs of harmonic index $t$ was started by Bannai-Okuda-Tagami (2015), and the case $t = 4$ was completed by Okuda-Yu (2016). In this paper we show the classification (non-existence) of tight spherical designs of harmonic index 6 and 8, as well as the asymptotic non-existence of tight spherical designs of harmonic index $2e$ for general $e\geq 3$. We also study the existence problem for tight spherical designs of harmonic index $T$ for some $T$, in particular, including index $T = \{8,4\}$.</p>Yan Zhu, Eiichi Bannai, Etsuko Bannai, Kyoung-Tark Kim, Wei-Hsuan Yuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p14Thu, 13 Apr 2017 00:00:00 +1000New Results on $k$-Independence of Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p15
<p>Let $G = (V, E)$ be a graph and $k \geq 0$ an integer. A $k$-independent set $S \subseteq G$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. Denote by $\alpha_{k}(G)$ the maximum cardinality of a $k$-independent set of $G$. For a graph $G$ on $n$ vertices and average degree $d$, Tur<span>á</span>n's theorem asserts that $\alpha_{0}(G) \geq \frac{n}{d+1}$, where the equality holds if and only if $G$ is a union of cliques of equal size. For general $k$ we prove that $\alpha_{k}(G) \geq \dfrac{(k+1)n}{d+k+1}$, improving on the previous best bound $\alpha_{k}(G) \geq \dfrac{(k+1)n}{ \lceil d \rceil+k+1}$ of Caro and Hansberg [E-JC, 2013]. For $1$-independence we prove that equality holds if and only if $G$ is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a $1$-factor). For $2$-independence, we prove that equality holds if and only if $G$ is an independent set. Furthermore when $d>0$ is an integer divisible by 3 we prove that $\alpha_2(G) \geq \dfrac{3n}{d+3} \left( 1 + \dfrac{12}{5d^2 + 25d + 18} \right)$.</p>Shimon Koganhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p15Fri, 05 May 2017 00:00:00 +1000On the Maximum Running Time in Graph Bootstrap Percolation
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p16
<p>Graph bootstrap percolation is a simple cellular automaton introduced by Bollob<span>á</span>s in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially `infect' all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a new infected copy of $H$ in $K_n$. We say that $G$ <em>percolates</em> if eventually every edge in $K_n$ is infected. The extremal question about the size of the smallest percolating sets when $H = K_r$ was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollob<span>á</span>s: what is the maximum time the process can run before it stabilizes? It is an easy observation that for $r=3$ this maximum is $\lceil \log_2 (n-1) \rceil $. However, a new phenomenon occurs for $r=4$ when, as we show, the maximum time of the process is $n-3$. For $r \geq 5$ the behaviour of the dynamics is even more complex, which we demonstrate by showing that the $K_r$-bootstrap process can run for at least $n^{2-\varepsilon_r}$ time steps for some $\varepsilon_r$ that tends to $0$ as $r \to \infty$.</p>Béla Bollobás, Michał Przykucki, Oliver Riordan, Julian Sahasrabudhehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p16Fri, 05 May 2017 00:00:00 +1000Three Interactions of Holes in Two Dimensional Dimer Systems
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p17
<p>Consider the unit triangular lattice in the plane with origin $O$, drawn so that one of the sets of lattice lines is vertical. Let $l$ and $l'$ denote respectively the vertical and horizontal lines that intersect $O$. Suppose the plane contains a pair of triangular holes of side length two, distributed symmetrically with respect to $l$ and $l'$ and oriented so that both holes point toward the origin. In the following article rhombus tilings of three different regions of the plane are considered, namely: tilings of the entire plane; tilings of the half plane that lies to the left of $l$ (where $l$ is considered a free boundary, so unit rhombi are allowed to protrude halfway across it); and tilings of the half plane that lies just below the fixed boundary $l'$. Asymptotic expressions for the interactions of the triangular holes in these three different regions are obtained thus providing further evidence for Ciucu's ongoing program that seeks to draw parallels between gaps in dimer systems on the hexagonal lattice and certain electrostatic phenomena.</p>Tomack Gilmorehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p17Fri, 05 May 2017 00:00:00 +1000Infinite Excursions of Router Walks on Regular Trees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p18
<p>A rotor configuration on a graph contains in every vertex an infinite ordered sequence of rotors, each is pointing to a neighbor of the vertex. After sampling a configuration according to some probability measure, a rotor walk is a deterministic process: at each step it chooses the next unused rotor in its current location, and uses it to jump to the neighboring vertex to which it points. Rotor walks capture many aspects of the expected behavior of simple random walks. However, this similarity breaks down for the property of having an infinite excursion. In this paper we study that question for natural random configuration models on regular trees. Our results suggest that in this context the rotor model behaves like the simple random walk unless it is not "close to" the standard rotor-router model.</p>Sebastian Müller, Tal Orenshteinhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p18Fri, 05 May 2017 00:00:00 +1000On the Caccetta-Häggkvist Conjecture with a Forbidden Transitive Tournament
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p19
The Caccetta-Häggkvist Conjecture asserts that every oriented graph on $n$ vertices without directed cycles of length less than or equal to $l$ has minimum outdegree at most $(n-1)/l$. In this paper we state a conjecture for graphs missing a transitive tournament on $2^k+1$ vertices, with a weaker assumption on minimum outdegree. We prove that the Caccetta-Häggkvist Conjecture follows from the presented conjecture and show matching constructions for all $k$ and $l$. The main advantage of considering this generalized conjecture is that it reduces the set of the extremal graphs and allows using an induction.<br /><br />We also prove the triangle case of the conjecture for $k=1$ and $2$ by using the Razborov's flag algebras. In particular, it proves the most interesting and studied case of the Caccetta-Häggkvist Conjecture in the class of graphs without the transitive tournament on 5 vertices. It is also shown that the extremal graph for the case $k=2$ has to be a blow-up of a directed cycle on 4 vertices having in each blob an extremal graph for the case $k=1$ (complete regular bipartite graph), which confirms the conjectured structure of the extremal examples.Andrzej Grzesikhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p19Fri, 05 May 2017 00:00:00 +1000On the Minimum Number of Monochromatic Generalized Schur Triples
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p20
The solution to the problem of finding the minimum number of monochromatic triples $(x,y,x+ay)$ with $a\geq 2$ being a fixed positive integer over any 2-coloring of $[1,n]$ was conjectured by Butler, Costello, and Graham (2010) and Thanathipanonda (2009). We solve this problem using a method based on Datskovsky's proof (2003) on the minimum number of monochromatic Schur triples $(x,y,x+y)$. We do this by exploiting the combinatorial nature of the original proof and adapting it to the general problem.<br /><br />Thotsaporn Thanatipanonda, Elaine Wonghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p20Fri, 05 May 2017 00:00:00 +1000A Structural Characterization for Certifying Robinsonian Matrices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p21
A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.<br /><br />Monique Laurent, Matteo Seminaroti, Shin-ichi Tanigawahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p21Fri, 05 May 2017 00:00:00 +1000Double Posets and the Antipode of QSym
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p22
A quasisymmetric function is assigned to every double poset (that is, every finite set endowed with two partial orders) and any weight function on its ground set. This generalizes well-known objects such as monomial and fundamental quasisymmetric functions, (skew) Schur functions, dual immaculate functions, and quasisymmetric $\left(P, \omega\right)$-partition enumerators. We prove a formula for the antipode of this function that holds under certain conditions (which are satisfied when the second order of the double poset is total, but also in some other cases); this restates (in a way that to us seems more natural) a result by Malvenuto and Reutenauer, but our proof is new and self-contained. We generalize it further to an even more comprehensive setting, where a group acts on the double poset by automorphisms.Darij Grinberghttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p22Fri, 05 May 2017 00:00:00 +1000Pretty Good State Transfer on Circulant Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p23
Let $G$ be a graph with adjacency matrix $A$. The transition matrix of $G$ relative to $A$ is defined by $H(t):=\exp{\left(-itA\right)}$, where $t\in {\mathbb R}$. The graph $G$ is said to admit pretty good state transfer between a pair of vertices $u$ and $v$ if there exists a sequence of real numbers $\{t_k\}$ and a complex number $\gamma$ of unit modulus such that $\lim\limits_{k\rightarrow\infty} H(t_k) e_u=\gamma e_v.$ We find that the cycle $C_n$ as well as its complement $\overline{C}_n$ admit pretty good state transfer if and only if $n$ is a power of two, and it occurs between every pair of antipodal vertices. In addition, we look for pretty good state transfer in more general circulant graphs. We prove that union (edge disjoint) of an integral circulant graph with a cycle, each on $2^k$ $(k\geq 3)$ vertices, admits pretty good state transfer. The complement of such union also admits pretty good state transfer. Using Cartesian products, we find some non-circulant graphs admitting pretty good state transfer.Hiranmoy Pal, Bikash Bhattacharjyahttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p23Wed, 17 May 2017 00:00:00 +1000Quantum State Transfer in Coronas
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p24
<p>We study state transfer in quantum walks on graphs relative to the adjacency matrix. Our motivation is to understand how the addition of pendant subgraphs affect state transfer. For two graphs $G$ and $H$, the Frucht-Harary corona product $G \circ H$ is obtained by taking $|G|$ copies of the cone $K_{1} + H$ and by identifying the conical vertices according to $G$. Our work explores conditions under which the corona $G \circ H$ exhibits state transfer. We also describe new families of graphs with state transfer based on the corona product. Some of these constructions provide a generalization of related known results.</p>Ethan Ackelsberg, Zachary Brehm, Ada Chan, Joshua Mundinger, Christino Tamonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p24Fri, 19 May 2017 00:00:00 +1000Majority Colourings of Digraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p25
We prove that every digraph has a vertex 4-colouring such that for each vertex $v$, at most half the out-neighbours of $v$ receive the same colour as $v$. We then obtain several results related to the conjecture obtained by replacing 4 by 3.Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Woodhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p25Fri, 19 May 2017 00:00:00 +1000Generating Functions for Inverted Semistandard Young Tableaux and Generalized Ballot Numbers
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p26
An inverted semistandard Young tableau is a row-standard tableau along with a collection of inversion pairs that quantify how far the tableau is from being column semistandard. Such a tableau with precisely $k$ inversion pairs is said to be a $k$-inverted semistandard Young tableau. Building upon earlier work by Fresse and the author, this paper develops generating functions for the numbers of $k$-inverted semistandard Young tableaux of various shapes $\lambda$ and contents $\mu$. An easily-calculable generating function is given for the number of $k$-inverted semistandard Young tableaux that "standardize" to a fixed semistandard Young tableau. For $m$-row shapes $\lambda$ and standard content $\mu$, the total number of $k$-inverted standard Young tableaux of shape $\lambda$ is then enumerated by relating such tableaux to $m$-dimensional generalizations of Dyck paths and counting the numbers of "returns to ground" in those paths. In the rectangular specialization of $\lambda = n^m$ this yields a generating function that involves $m$-dimensional analogues of the famed Ballot numbers. Our various results are then used to directly enumerate all $k$-inverted semistandard Young tableaux with arbitrary content and two-row shape $\lambda = a^1 b^1$, as well as all $k$-inverted standard Young tableaux with two-column shape $\lambda=2^n$.Paul Drubehttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p26Fri, 19 May 2017 00:00:00 +1000