HOME > Journal Current TOC
Electronic Journal of Combinatorics [0 followers] Follow Open Access journal ISSN (Print) 1077-8926 Published by Electronic Journal of Combinatorics [1 journal] |
- Anagram-Free Graph Colouring
Authors: Tim E. Wilson, David R. Wood
Pages: 2 - 20
Abstract: An anagram is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al.[Random Structures & Algorithms 2002] asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and $k$-anagram-free colouring.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- A Generalization of Erdős' Matching Conjecture
Authors: Christos Pelekis, Israel Rocha
Pages: 2 - 21
Abstract: Let $\mathcal{H}=(V,\mathcal{E})$ be an $r$-uniform hypergraph on $n$ vertices and fix a positive integer $k$ such that $1\le k\le r$. A $k$-matching of $\mathcal{H}$ is a collection of edges $\mathcal{M}\subset \mathcal{E}$ such that every subset of $V$ whose cardinality equals $k$ is contained in at most one element of $\mathcal{M}$. The $k$-matching number of $\mathcal{H}$ is the maximum cardinality of a $k$-matching. A well-known problem, posed by Erdős, asks for the maximum number of edges in an $r$-uniform hypergraph under constraints on its $1$-matching number. In this article we investigate the more general problem of determining the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices subject to the constraint that its $k$-matching number is strictly less than $a$. The problem can also be seen as a generalization of the well-known $k$-intersection problem. We propose candidate hypergraphs for the solution of this problem, and show that the extremal hypergraph is among this candidate set when $n\ge 4r\binom{r}{k}^2\cdot a$.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- Some Variations on a Theme of Irina Mel'nichuk Concerning the
Avoidability of Patterns in Strings of Symbols
Authors: George F. McNulty
Pages: 2 - 22
Abstract: The set of all doubled patterns on $n$ or fewer letters can be avoided on an alphabet with $k$ letters, where $k$ is the least even integer strictly greater than $n+1$, with the exception of $n=4$. The set of all doubled patterns on $4$ or fewer letters can be avoided on the $8$-letter alphabet. The set of all avoidable patterns on $n$ or fewer letters can be avoided on an alphabet with $2(n+2)$ letters.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- Chromatic Index, Treewidth and Maximum Degree
Authors: Henning Bruhn, Laura Gellert, Richard Lang
Pages: 2 - 23
Abstract: We conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. We also show that any graph $G$ with treewidth $k\geq 4$ and maximum degree $2k-1$ satisfies $\chi'(G)=\Delta(G)$, extending an old result of Vizing.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- Deferred On-Line Bipartite Matching
Authors: Jakub Kozik, Grzegorz Matecki
Pages: 2 - 24
Abstract: We present a new model for the problem of on-line matching on bipartite graphs. Suppose that one part of a graph is given, but the vertices of the other part are presented in an on-line fashion. In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever. In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty). Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex, with the restriction that each element belongs to at most one group. We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals $1-\pi/\cosh(\frac{\sqrt{3}}{2}\pi)\approx 0.588$.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- Semiregular Automorphisms in Vertex-Transitive Graphs of Order $3p^2$
Authors: Dragan Marušič
Pages: 2 - 25
Abstract: It has been conjectured that automorphism groups of vertex-transitive (di)graphs, and more generally $2$-closures of transitive permutation groups, must necessarily possess a fixed-point-free element of prime order, and thus a non-identity element with all orbits of the same length, in other words, a semiregular element. It is the purpose of this paper to prove that vertex-transitive graphs of order $3p^2$, where $p$ is a prime, contain semiregular automorphisms.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- Edge Reconstruction of the Ihara Zeta Function
Authors: Gunther Cornelissen, Janne Kool
Pages: 2 - 26
Abstract: We show that if a graph $G$ has average degree $\overline d \geq 4$, then the Ihara zeta function of $G$ is edge-reconstructible. We prove some general spectral properties of the edge adjacency operator $T$: it is symmetric for an indefinite form and has a "large" semi-simple part (but it can fail to be semi-simple in general). We prove that this implies that if $\overline d>4$, one can reconstruct the number of non-backtracking (closed or not) walks through a given edge, the Perron-Frobenius eigenvector of $T$ (modulo a natural symmetry), as well as the closed walks that pass through a given edge in both directions at least once.
PubDate: 2018-05-11
Issue No: Vol. 25, No. 2 (2018)
- Clique Trees of Infinite Locally Finite Chordal Graphs
Authors: Christoph Hofer-Temmel, Florian Lehner
Pages: 2 - 9
Abstract: We investigate clique trees of infinite locally finite chordal graphs. Our main contribution is a bijection between the set of clique trees and the product of local finite families of finite trees. Even more, the edges of a clique tree are in bijection with the edges of the corresponding collection of finite trees. This allows us to enumerate the clique trees of a chordal graph and extend various classic characterisations of clique trees to the infinite setting.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Vertex-Transitive Direct Products of Graphs
Authors: Richard H. Hammack, Wilfried Imrich
Pages: 2 - 10
Abstract: It is known that for graphs $A$ and $B$ with odd cycles, the direct product $A\times B$ is vertex-transitive if and only if both $A$ and $B$ are vertex-transitive. But this is not necessarily true if one of $A$ or $B$ is bipartite, and until now there has been no characterization of such vertex-transitive direct products. We prove that if $A$ and $B$ are both bipartite, or both non-bipartite, then $A\times B$ is vertex-transitive if and only if both $A$ and $B$ are vertex-transitive. Also, if $A$ has an odd cycle and $B$ is bipartite, then $A\times B$ is vertex-transitive if and only if both $A\times K_2$ and $B$ are vertex-transitive.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Hypergraph Saturation Irregularities
Authors: Natalie C. Behague
Pages: 2 - 11
Abstract: Let $\mathcal{F}$ be a family of $r$-graphs. An $r$-graph $G$ is called $\mathcal{F}$-saturated if it does not contain any members of $\mathcal{F}$ but adding any edge creates a copy of some $r$-graph in $\mathcal{F}$. The saturation number $\operatorname{sat}(\mathcal{F},n)$ is the minimum number of edges in an $\mathcal{F}$-saturated graph on $n$ vertices. We prove that there exists a finite family $\mathcal{F}$ such that $\operatorname{sat}(\mathcal{F},n) / n^{r-1}$ does not tend to a limit. This settles a question of Pikhurko.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- On Vertex-Disjoint Paths in Regular Graphs
Authors: Jie Han
Pages: 2 - 12
Abstract: Let $c\in (0, 1]$ be a real number and let $n$ be a sufficiently large integer. We prove that every $n$-vertex $c n$-regular graph $G$ contains a collection of $\lfloor 1/c \rfloor$ paths whose union covers all but at most $o(n)$ vertices of $G$. The constant $\lfloor 1/c \rfloor$ is best possible when $1/c\notin \mathbb{N}$ and off by $1$ otherwise. Moreover, if in addition $G$ is bipartite, then the number of paths can be reduced to $\lfloor 1/(2c) \rfloor$, which is best possible.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- A New Upper Bound for Cancellative Pairs
Authors: Barnabás Janzer
Pages: 2 - 13
Abstract: A pair $(\mathcal{A},\mathcal{B})$ of families of subsets of an $n$-element set is called cancellative if whenever $A,A'\in\mathcal{A}$ and $B\in\mathcal{B}$ satisfy $A\cup B=A'\cup B$, then $A=A'$, and whenever $A\in\mathcal{A}$ and $B,B'\in\mathcal{B}$ satisfy $A\cup B=A\cup B'$, then $B=B'$. It is known that there exist cancellative pairs with $ \mathcal{A} \mathcal{B} $ about $2.25^n$, whereas the best known upper bound on this quantity is $2.3264^n$. In this paper we improve this upper bound to $2.2682^n$. Our result also improves the best known upper bound for Simonyi's sandglass conjecture for set systems.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Erdős-Ginzburg-Ziv Constants by Avoiding Three-Term Arithmetic
Progressions
Authors: Jacob Fox, Lisa Sauermann
Pages: 2 - 14
Abstract: For a finite abelian group $G$, The Erdős-Ginzburg-Ziv constant $\mathfrak{s}(G)$ is the smallest $s$ such that every sequence of $s$ (not necessarily distinct) elements of $G$ has a zero-sum subsequence of length $\operatorname{exp}(G)$. For a prime $p$, let $r(\mathbb{F}_p^n)$ denote the size of the largest subset of $\mathbb{F}_p^n$ without a three-term arithmetic progression. Although similar methods have been used to study $\mathfrak{s}(G)$ and $r(\mathbb{F}_p^n)$, no direct connection between these quantities has previously been established. We give an upper bound for $\mathfrak{s}(G)$ in terms of $r(\mathbb{F}_p^n)$ for the prime divisors $p$ of $\operatorname{exp}(G)$. For the special case $G=\mathbb{F}_p^n$, we prove $\mathfrak{s}(\mathbb{F}_p^n)\leq 2p\cdot r(\mathbb{F}_p^n)$. Using the upper bounds for $r(\mathbb{F}_p^n)$ of Ellenberg and Gijswijt, this result improves the previously best known upper bounds for $\mathfrak{s}(\mathbb{F}_p^n)$ given by Naslund.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- On the Smallest Snarks with Oddness 4 and Connectivity 2
Authors: Jan Goedgebeur
Pages: 2 - 15
Abstract: A snark is a bridgeless cubic graph which is not 3-edge-colourable. The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph.
Lukot'ka, Máčajová, Mazák and Škoviera showed in [Electron. J. Combin. 22 (2015)] that the smallest snark with oddness 4 has 28 vertices and remarked that there are exactly two such graphs of that order. However, this remark is incorrect as — using an exhaustive computer search — we show that there are in fact three snarks with oddness 4 on 28 vertices. In this note we present the missing snark and also determine all snarks with oddness 4 up to 34 vertices.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Bipartite Ramsey Numbers for Graphs of Small Bandwidth
Authors: Lili Shen, Qizhong Lin, Qinghai Liu
Pages: 2 - 16
Abstract: A graph $H=(W,E_H)$ is said to have bandwidth at most $b$ if there exists a labeling of $W$ as $w_1,w_2,\dots,w_n$ such that $ i-j \leq b$ for every edge $w_iw_j\in E_H$, and a bipartite balanced $(\beta,\Delta)$-graph $H$ is a bipartite graph with bandwidth at most $\beta W $ and maximum degree at most $\Delta$, and furthermore it has a proper 2-coloring $\chi :W\rightarrow[2]$ such that $ \chi^{-1}(1) - \chi^{-1}(2) \leq\beta \chi^{-1}(2) $. We prove that for any fixed $0<\gamma<1$ and integer $\Delta\ge1$, there exist a constant $\beta=\beta(\gamma,\Delta)>0$ and a natural number $n_0$ such that for every balanced $(\beta,\Delta)$-graph $H$ on $n\geq n_0$ vertices the bipartite Ramsey number $br(H,H)$ is at most $(1+\gamma)n$. In particular, $br(C_{2n},C_{2n})=(2+o(1))n$.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- On Bergeron's Positivity Problem for $q$-Binomial Coefficients
Authors: Fabrizio Zanello
Pages: 2 - 17
Abstract: F. Bergeron recently asked the intriguing question whether $\binom{b+c}{b}_q -\binom{a+d}{d}_q$ has nonnegative coefficients as a polynomial in $q$, whenever $a,b,c,d$ are positive integers, $a$ is the smallest, and $ad=bc$. We conjecture that, in fact, this polynomial is also always unimodal, and combinatorially show our conjecture for $a\le 3$ and any $b,c\ge 4$. The main ingredient will be a novel (and rather technical) application of Zeilberger's KOH theorem.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Subgraphs with Large Minimum $\ell$-Degree in Hypergraphs where Almost All
$\ell$-Degrees are Large
Authors: Victor Falgas-Ravry, Allan Lo
Pages: 2 - 18
Abstract: Let $G$ be an $r$-uniform hypergraph on $n$ vertices such that all but at most $\varepsilon \binom{n}{\ell}$ $\ell$-subsets of vertices have degree at least $p \binom{n-\ell}{r-\ell}$. We show that $G$ contains a large subgraph with high minimum $\ell$-degree.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Counting Compositions over Finite Abelian Groups
Authors: Zhicheng Gao, Andrew MacFie, Qiang Wang
Pages: 2 - 19
Abstract: We find the number of compositions over finite abelian groups under two types of restrictions: (i) each part belongs to a given subset and (ii) small runs of consecutive parts must have given properties. Waring's problem over finite fields can be converted to type (i) compositions, whereas Carlitz and "locally Mullen" compositions can be formulated as type (ii) compositions. We use the multisection formula to translate the problem from integers to group elements, the transfer matrix method to do exact counting, and finally the Perron-Frobenius theorem to derive asymptotics. We also exhibit bijections involving certain restricted classes of compositions.
PubDate: 2018-04-27
Issue No: Vol. 25, No. 2 (2018)
- Sharp Lower Bounds on the Spectral Radius of Uniform Hypergraphs
Concerning Degrees
Authors: Liying Kang, Lele Liu, Erfang Shan
Pages: 2 - 1
Abstract: Let $\mathcal{A}(H)$ and $\mathcal{Q}(H)$ be the adjacency tensor and signless Laplacian tensor of an $r$-uniform hypergraph $H$. Denote by $\rho(H)$ and $\rho(\mathcal{Q}(H))$ the spectral radii of $\mathcal{A}(H)$ and $\mathcal{Q}(H)$, respectively. In this paper we present a lower bound on $\rho(H)$ in terms of vertex degrees and we characterize the extremal hypergraphs attaining the bound, which solves a problem posed by Nikiforov [Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455–535]. Also, we prove a lower bound on $\rho(\mathcal{Q}(H))$ concerning degrees and give a characterization of the extremal hypergraphs attaining the bound.
PubDate: 2018-04-13
Issue No: Vol. 25, No. 2 (2018)
- Eigenvalue Bounds for the Signless $p$-Laplacian
Authors: Elizandro Max Borba, Uwe Schwerdtfeger
Pages: 2 - 2
Abstract: We consider the signless $p$-Laplacian $Q_p$ of a graph, a generalisation of the quadratic form of the signless Laplacian matrix (the case $p=2$). In analogy to Rayleigh's principle the minimum and maximum of $Q_p$ on the $p$-norm unit sphere are called its smallest and largest eigenvalues, respectively. We show a Perron-Frobenius property and basic inequalites for the largest eigenvalue and provide upper and lower bounds for the smallest eigenvalue in terms of a graph parameter related to the bipartiteness. The latter result generalises bounds by Desai and Rao and, interestingly, at $p=1$ upper and lower bounds coincide.
PubDate: 2018-04-13
Issue No: Vol. 25, No. 2 (2018)
- On the Poset and Asymptotics of Tesler Matrices
Authors: Jason O'Neill
Pages: 2 - 4
Abstract: Tesler matrices are certain integral matrices counted by the Kostant partition function and have appeared recently in Haglund's study of diagonal harmonics. In 2014, Drew Armstrong defined a poset on such matrices and conjectured that the characteristic polynomial of this poset is a power of $q-1$. We use a method of Hallam and Sagan to prove a stronger version of this conjecture for posets of a certain class of generalized Tesler matrices. We also study bounds for the number of Tesler matrices and how they compare to the number of parking functions, the dimension of the space of diagonal harmonics.
PubDate: 2018-04-13
Issue No: Vol. 25, No. 2 (2018)
- A New Approach for Examining $q$-Steiner Systems
Authors: Tuvi Etzion
Pages: 2 - 8
Abstract: One of the most intriguing problems in $q$-analogs of designs and codes is the existence question of an infinite family of $q$-analog of Steiner systems (spreads not included) in general, and the existence question for the $q$-analog of the Fano plane in particular.We exhibit a completely new method to attack this problem. In the process we define a new family of designs whose existence is implied by the existence of $q$-Steiner systems, but could exist even if the related $q$-Steiner systems do not exist.The method is based on a possible system obtained by puncturing all the subspaces of the $q$-Steiner system several times. We define the punctured system as a new type of design and enumerate the number of subspaces of various types that it might have. It will be evident that its existence does not imply the existence of the related $q$-Steiner system. On the other hand, this type of design demonstrates how close can we get to the related $q$-Steiner system.Necessary conditions for the existence of such designs are presented. These necessary conditions will be also necessary conditions for the existence of the related $q$-Steiner system. Trivial and nontrivial direct constructions and a nontrivial recursive construction for such designs are given. Some of the designs have a symmetric structure, which is uniform in the dimensions of the existing subspaces in the system. Most constructions are based on this uniform structure of the design or its punctured designs.
PubDate: 2018-04-13
Issue No: Vol. 25, No. 2 (2018)
- Residual $q$-Fano Planes and Related Structures
Authors: Tuvi Etzion, Niv Hooker
Pages: 2 - 3
Abstract: One of the most intriguing problems for $q$-analogs of designs, is the existence question of an infinite family of $q$-Steiner systems that are not spreads. In particular the most interesting case is the existence question for the $q$-analog of the Fano plane, known also as the $q$-Fano plane. These questions are in the front line of open problems in block design. There was a common belief and a conjecture that such structures do not exist. Only recently, $q$-Steiner systems were found for one set of parameters. In this paper, a definition for the $q$-analog of the residual design is presented. This new definition is different from previous known definition, but its properties reflect better the $q$-analog properties. The existence of a design with the parameters of the residual $q$-Steiner system in general and the residual $q$-Fano plane in particular are examined. We construct different residual $q$-Fano planes for all $q$, where $q$ is a prime power. The constructed structure is just one step from a construction of a $q$-Fano plane.
PubDate: 2018-04-03
Issue No: Vol. 25, No. 2 (2018)
- Hamilton Circles in Cayley Graphs
Authors: Babak Miraftab, Tim Rühmann
Pages: 2 - 5
Abstract: For locally finite infinite graphs the notion of Hamilton cycles can be extended to Hamilton circles, homeomorphic images of $S^1$ in the Freudenthal compactification. In this paper we prove a sufficient condition for the existence of Hamilton circles in locally finite Cayley graphs.
PubDate: 2018-04-03
Issue No: Vol. 25, No. 2 (2018)
- On the Existence of Frobenius Digraphical Representations
Authors: Pablo Spiga
Pages: 2 - 6
Abstract: A Frobenius group is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A digraphical, respectively graphical, Frobenius representation, DFR and GFR for short, of a Frobenius group $F$ is a digraph, respectively graph, whose automorphism group as a group of permutations of the vertex set is $F$. The problem of classifying which Frobenius groups admit a DFR and GFR has been proposed by Mark Watkins and Thomas Tucker and is a natural extension of the problem of classifying which groups that have a digraphical, respectively graphical, regular representation.In this paper, we give a partial answer to a question of Mark Watkins and Thomas Tucker concerning Frobenius representations: "All but finitely many Frobenius groups with a given Frobenius complement have a DFR".
PubDate: 2018-04-03
Issue No: Vol. 25, No. 2 (2018)
- Even Subgraph Expansions for the Flow Polynomial of Planar Graphs with
Maximum Degree at Most 4
Authors: Qingying Deng, Xian'an Jin, Fengming Dong, Eng Guan Tay
Pages: 2 - 7
Abstract: As projections of links, 4-regular plane graphs are important in combinatorial knot theory. The flow polynomial of 4-regular plane graphs has a close relation with the two-variable Kauffman polynomial of links. F. Jaeger in 1991 provided even subgraph expansions for the flow polynomial of cubic plane graphs. Starting from and based on Jaeger's work, by introducing splitting systems of even subgraphs, we extend Jaeger's results from cubic plane graphs to plane graphs with maximum degree at most 4 including 4-regular plane graphs as special cases. Several consequences are derived and further work is discussed.
PubDate: 2018-04-03
Issue No: Vol. 25, No. 2 (2018)