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, 14 Oct 2016 13:20:56 +1100OJS 2.3.6.0http://blogs.law.harvard.edu/tech/rss60Isotropic Matroids I: Multimatroids and Neighborhoods
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p1
<p>Several properties of the isotropic matroid of a looped simple graph are presented. Results include a characterization of the multimatroids that are associated with isotropic matroids and several ways in which the isotropic matroid of $G$ incorporates information about graphs locally equivalent to $G$. Specific results of the latter type include a characterization of graphs that are locally equivalent to bipartite graphs, a direct proof that two forests are isomorphic if and only if their isotropic matroids are isomorphic, and a way to express local equivalence indirectly, using only edge pivots.</p>Robert Brijder, Lorenzo Traldihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p1Fri, 14 Oct 2016 00:00:00 +1100Isotropic Matroids II: Circle Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p2
<p>We present several characterizations of circle graphs, which follow from Bouchet’s circle graph obstructions theorem.</p>Robert Brijder, Lorenzo Traldihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p2Fri, 14 Oct 2016 00:00:00 +1100On the Potts Antiferromagnet on Random Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p3
Extending a prior result of Contucci et al. [Comm. Math. Phys. 2013], we determine the free energy of the Potts antiferromagnet on the Erdős–Rényi random graph at all temperatures for average degrees $d\le (2k-1)\ln k - 2 - k^{-1/2}$. In particular, we show that for this regime of $d$ there does not occur a phase transition.Amin Coja-Oghlan, Nor Jaafarihttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p3Fri, 14 Oct 2016 00:00:00 +1100Coloring Non-Crossing Strings
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p4
For a family of geometric objects in the plane $\mathcal{F}=\{S_1,\ldots,S_n\}$, define $\chi(\mathcal{F})$ as the least integer $\ell$ such that the elements of $\mathcal{F}$ can be colored with $\ell$ colors, in such a way that any two intersecting objects have distinct colors. When $\mathcal{F}$ is a set of pseudo-disks that may only intersect on their boundaries, and such that any point of the plane is contained in at most $k$ pseudo-disks, it can be proven that $\chi(\mathcal{F})\le 3k/2 + o(k)$ since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudo-disks are replaced by a family $\mathcal{F}$ of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of $\mathcal{F}$ are only allowed to "touch" each other. Such a family is said to be $k$-touching if no point of the plane is contained in more than $k$ elements of $\mathcal{F}$. We give bounds on $\chi(\mathcal{F})$ as a function of $k$, and in particular we show that $k$-touching segments can be colored with $k+5$ colors. This partially answers a question of Hliněný (1998) on the chromatic number of contact systems of strings.Louis Esperet, Daniel Gonçalves, Arnaud Labourelhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p4Fri, 14 Oct 2016 00:00:00 +1100Packing Polynomials on Multidimensional Integer Sectors
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p5
<p>Denoting the real numbers and the nonnegative integers, respectively, by ${\bf R}$ and ${\bf N}$, let $S$ be a subset of ${\bf N}^n$ for $n = 1, 2,\ldots$, and $f$ be a mapping from ${\bf R}^n$ into ${\bf R}$. We call $f$ a <em>packing function</em> on $S$ if the restriction $f|_{S}$ is a bijection onto ${\bf N}$. For all positive integers $r_1,\ldots,r_{n-1}$, we consider the <em>integer sector </em>\[I(r_1, \ldots, r_{n-1}) =\{(x_1,\ldots,x_n) \in N^n \; | \; x_{i+1} \leq r_ix_i \mbox{ for } i = 1,\ldots,n-1 \}.\] Recently, Melvyn B. Nathanson (2014) proved that for $n=2$ there exist two quadratic packing polynomials on the sector $I(r)$. Here, for $n>2$ we construct $2^{n-1}$ packing polynomials on multidimensional integer sectors. In particular, for each packing polynomial on ${\bf N}^n$ we construct a packing polynomial on the sector $I(1, \ldots, 1)$.</p>Luis B. Moraleshttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p5Fri, 14 Oct 2016 00:00:00 +1100On Matchings in Stochastic Kronecker Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p6
<p>The stochastic Kronecker graph is a random structure whose vertex set is a hypercube and the probability of an edge depends on the structure of its ends. We prove that a.a.s. as soon as the stochastic Kronecker graph becomes connected it contains a perfect matching.</p>Justyna Banaszakhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p6Mon, 03 Oct 2016 20:47:23 +1100On Almost-Regular Edge Colourings of Hypergraphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p7
<p>We prove that if ${\cal{H}}=(V({\cal{H}}),{\cal{E}}({\cal{H}}))$ is a hypergraph, $\gamma$ is an edge colouring of ${\cal{H}}$, and $S\subseteq V({\cal{H}})$ such that any permutation of $S$ is an automorphism of ${\cal{H}}$, then there exists a permutation $\pi$ of ${\cal{E}}({\cal{H}})$ such that $|\pi(E)|=|E|$ and $\pi(E)\setminus S=E\setminus S$ for each $E\in{\cal{H}}({\cal{H}})$, and such that the edge colouring $\gamma'$ of ${\cal{H}}$ given by $\gamma'(E)=\gamma(\pi^{-1}(E))$ for each $E\in{\cal{E}}({\cal{H}})$ is almost regular on $S$. The proof is short and elementary. We show that a number of known results, such as Baranyai's Theorem on almost-regular edge colourings of complete $k$-uniform hypergraphs, are easy corollaries of this theorem.</p>Darryn Bryanthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p7Fri, 14 Oct 2016 00:00:00 +1100Upper Bounds for Stern's Diatomic Sequence and Related Sequences
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p8
<pre>Let <span>$(s_2(n))_{n=0}^\infty$</span> denote Stern's diatomic sequence. For <span>$n\geq 2$</span>, we may view <span>$s_2(n)$</span> as the number of partitions of <span>$n-1$</span> into powers of <span>$2$</span> with each part occurring at most twice. More generally, for integers <span>$b,n\geq 2$</span>, let <span>$s_b(n)$</span> denote the number of partitions of <span>$n-1$</span> into powers of <span>$b$</span> with each part occurring at most <span>$b$</span> times. Using this <span>combinatorial</span> interpretation of the sequences <span>$s_b(n)$</span>, we use the transfer-matrix method to develop a means of calculating <span>$s_b(n)$</span> for certain values of <span>$n$</span>. This then allows us to derive upper bounds for <span>$s_b(n)$</span> for certain values of <span>$n$</span>. In the special case <span>$b=2$</span>, our bounds improve upon the current upper bounds for the Stern sequence. In addition, we are able to prove that <span>$\displaystyle{\limsup_{n\rightarrow\infty}\frac{s_b(n)}{n^{\log_b\phi}}=\frac{(b^2-1)^{\log_b\phi}}{\sqrt 5}}$</span>.</pre>Colin Defanthttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p8Fri, 14 Oct 2016 00:00:00 +1100The Smith and Critical Groups of the Square Rook's Graph and its Complement
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p9
Let $R_{n}$ denote the graph with vertex set consisting of the squares of an $n \times n$ grid, with two squares of the grid adjacent when they lie in the same row or column. This is the square rook's graph, and can also be thought of as the Cartesian product of two complete graphs of order $n$, or the line graph of the complete bipartite graph $K_{n,n}$. In this paper we compute the Smith group and critical group of the graph $R_{n}$ and its complement. This is equivalent to determining the Smith normal form of both the adjacency and Laplacian matrix of each of these graphs. In doing so we verify a 1986 conjecture of Rushanan.Joshua E. Ducey, Jonathan Gerhard, Noah Watsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p9Fri, 14 Oct 2016 00:00:00 +1100All or Nothing at All
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p10
We continue a study of unconditionally secure all-or-nothing transforms (AONT) begun by Stinson (2001). An AONT is a bijective mapping that constructs $s$ outputs from $s$ inputs. We consider the security of $t$ inputs, when $s-t$ outputs are known. Previous work concerned the case $t=1$; here we consider the problem for general $t$, focussing on the case $t=2$. We investigate constructions of binary matrices for which the desired properties hold with the maximum probability. Upper bounds on these probabilities are obtained via a quadratic programming approach, while lower bounds can be obtained from combinatorial constructions based on symmetric BIBDs and cyclotomy. We also report some results on exhaustive searches and random constructions for small values of $s$.Paolo D'Arco, Navid Nasr Esfahani, Douglas R. Stinsonhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p10Wed, 05 Oct 2016 20:42:42 +1100A Short Conceptual Proof of Narayana's Path-Counting Formula
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p11
We deduce Narayana's formula for the number of lattice paths that fit in a Young diagram as a direct consequence of the Gessel-Viennot theorem on non-intersecting lattice paths.Mihai Ciucuhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p11Fri, 14 Oct 2016 00:00:00 +1100