bluuebunny/crossref_metadata_2025 huggingface dataset:
Almost Product Evaluation of Hankel Determinants
Authors: Eğecioğlu Ömer , Redmond Timothy , Ryavec Charles
Published: January 2020

An extensive literature exists describing various techniques for the evaluation of Hankel determinants. The prevailing methods such as Dodgson condensation, continued fraction expansion, LU decomposition, all produce product formulas when they are applicable. We mention the classic case of the Hankel determinants with binomial entries ${3 k +2 \choose k}$ and those with entries ${3 k \choose k}$; both of these classes of Hankel determinants have product form evaluations. The intermediate case, ${3 k +1 \choose k}$ has not been evaluated. There is a good reason for this: these latter determinants do not have product form evaluations. In this paper we evaluate the Hankel determinant of ${3 k +1 \choose k}$. The evaluation is a sum of a small number of products, an almost product. The method actually provides more, and as applications, we present the salient points for the evaluation of a number of other Hankel determinants with polynomial entries, along with product and almost product form evaluations at special points.
Envy-Free Cake Divisions Cannot be Found by Finite Protocols
Authors: Stromquist Walter
Published: January 2020

We show that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single connected piece.
Symmetric Simplicial Pseudoline Arrangements
Authors: Berman Leah Wrenn
Published: January 2020

A simplicial arrangement of pseudolines is a collection of topological lines in the projective plane where each region that is formed is triangular. This paper refines and develops David Eppstein's notion of a kaleidoscope construction for symmetric pseudoline arrangements to construct and analyze several infinite families of simplicial pseudoline arrangements with high degrees of geometric symmetry. In particular, all simplicial pseudoline arrangements with the symmetries of a regular $k$-gon and three symmetry classes of pseudolines, consisting of the mirrors of the $k$-gon and two other symmetry classes, plus sometimes the line at infinity, are classified, and other interesting families (with more symmetry classes of pseudolines) are discussed.
Transversal Lattices
Authors: Bonin Joseph E.
Published: January 2020

A flat of a matroid is cyclic if it is a union of circuits; such flats form a lattice under inclusion and, up to isomorphism, all lattices can be obtained this way. A lattice is a Tr-lattice if all matroids whose lattices of cyclic flats are isomorphic to it are transversal. We investigate some sufficient conditions for a lattice to be a Tr-lattice; a corollary is that distributive lattices of dimension at most two are Tr-lattices. We give a necessary condition: each element in a Tr-lattice has at most two covers. We also give constructions that produce new Tr-lattices from known Tr-lattices.
Computing Parametric Rational Generating Functions with a Primal Barvinok Algorithm
Authors: Köppe Matthias , Verdoolaege Sven
Published: January 2020

Computations with Barvinok's short rational generating functions are traditionally being performed in the dual space, to avoid the combinatorial complexity of inclusion–exclusion formulas for the intersecting proper faces of cones. We prove that, on the level of indicator functions of polyhedra, there is no need for using inclusion–exclusion formulas to account for boundary effects: All linear identities in the space of indicator functions can be purely expressed using partially open variants of the full-dimensional polyhedra in the identity. This gives rise to a practically efficient, parametric Barvinok algorithm in the primal space.
Maximal Nontraceable Graphs with Toughness less than One
Authors: Bullock Frank , Frick Marietjie , Singleton Joy , Van Aardt Susan , Mynhardt Kieka (C.M.)
Published: January 2020

A graph $G$ is maximal nontraceable (MNT) if $G$ does not have a hamiltonian path but, for every $e\in E\left( \overline{G}\right) $, the graph $G+e$ has a hamiltonian path. A graph $G$ is 1-tough if for every vertex cut $S$ of $G$ the number of components of $G-S$ is at most $|S|$. We investigate the structure of MNT graphs that are not 1-tough. Our results enable us to construct several interesting new classes of MNT graphs.
Ear Decompositions in Combed Graphs
Authors: De Carvalho Marcelo H. , Little C. H. C.
Published: January 2020

We introduce the concept of combed graphs and present an ear decomposition theorem for this class of graphs. This theorem includes the well known ear decomposition theorem for matching covered graphs proved by Lovász and Plummer. Then we use the ear decomposition theorem to show that any two edges of a 2-connected combed graph lie in a balanced circuit of an equivalent combed graph. This result generalises the theorem that any two edges in a matching covered graph with at least four vertices belong to an alternating circuit.
Edit Distance and its Computation
Authors: Balogh József , Martin Ryan
Published: January 2020

In this paper, we provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be computed without using Szemerédi's Regularity Lemma directly. Using this new method, we are able to compute the edit distance from hereditary properties for which it was previously unknown. For some graphs $H$, the edit distance from ${\rm Forb}(H)$ is computed, where ${\rm Forb}(H)$ is the class of graphs which contain no induced copy of graph $H$. Those graphs for which we determine the edit distance asymptotically are $H=K_a+E_b$, an $a$-clique with $b$ isolated vertices, and $H=K_{3,3}$, a complete bipartite graph. We also provide a graph, the first such construction, for which the edit distance cannot be determined just by considering partitions of the vertex set into cliques and cocliques. In the process, we develop weighted generalizations of Turán's theorem, which may be of independent interest.
Coefficients of Functional Compositions Often Grow Smoothly
Authors: Bender Edward A. , Canfield E. Rodney , Richmond L. Bruce
Published: January 2020

The coefficients of a power series $A(x)$ are smooth if $a_{n-1}/a_n$ approaches a limit. If $A(x)=F(G(x))$ and $f_n^{1/n}$ approaches a limit, then the coefficients of $A(x)$ are often smooth. We use this to show that the coefficients of the exponential generating function for graphs embeddable on a given surface are smooth, settling a problem of McDiarmid.
An Anti-Ramsey Condition on Trees
Authors: Picollelli Michael E.
Published: January 2020

Let $H$ be a finite tree. We consider trees $T$ such that if the edges of $T$ are colored so that no color occurs more than $b$ times, then $T$ has a subgraph isomorphic to $H$ in which no color is repeated. We will show that if $H$ falls into a few classes of trees, including those of diameter at most $4$, then the minimum value of $e(T)$ is provided by a known construction, supporting a conjecture of Bohman, Frieze, Pikhurko and Smyth.
Graph-Based Upper Bounds for the Probability of the Union of Events
Authors: Veneziani Pierangela
Published: January 2020

We consider the problem of generating upper bounds for the probability of the union of events when the individual probabilities of the events as well as the probabilities of pairs of these events are known. By formulating the problem as a Linear Program, we can obtain bounds as objective function values corresponding to dual basic feasible solutions. The new upper bounds are based on underlying bipartite and threshold type graph structures.
Nonexistence of Triples of Nonisomorphic Connected Graphs with Isomorphic Connected $P_3$-graphs
Authors: Li Xueliang , Liu Yan
Published: January 2020

In the paper "Broersma and Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444", the authors asked a problem whether there is a triple of mutually nonisomorphic connected graphs which have an isomorphic connected $P_3$-graph. In this paper, we show that there is no such triple, and thus completely solve this problem.
On Pattern-Avoiding Partitions
Authors: Jelínek Vít , Mansour Toufik
Published: January 2020

A set partition of size $n$ is a collection of disjoint blocks $B_1,B_2,\ldots$, $B_d$ whose union is the set $[n]=\{1,2,\ldots,n\}$. We choose the ordering of the blocks so that they satisfy $\min B_1 < \min B_2 < \cdots < \min B_d$. We represent such a set partition by a canonical sequence $\pi_1,\pi_2,\ldots,\pi_n$, with $\pi_i=j$ if $i\in B_j$. We say that a partition $\pi$ contains a partition $\sigma$ if the canonical sequence of $\pi$ contains a subsequence that is order-isomorphic to the canonical sequence of $\sigma$. Two partitions $\sigma$ and $\sigma'$ are equivalent, if there is a size-preserving bijection between $\sigma$-avoiding and $\sigma'$-avoiding partitions. We determine all the equivalence classes of partitions of size at most $7$. This extends previous work of Sagan, who described the equivalence classes of partitions of size at most $3$. Our classification is largely based on several new infinite families of pairs of equivalent patterns. For instance, we prove that there is a bijection between $k$-noncrossing and $k$-nonnesting partitions, with a notion of crossing and nesting based on the canonical sequence. Our results also yield new combinatorial interpretations of the Catalan numbers and the Stirling numbers.
Small Group Divisible Steiner Quadruple Systems
Authors: Zhuravlev Artem A. , Keranen Melissa S. , Kreher Donald L.
Published: January 2020

A group divisible Steiner quadruple system, is a triple $(X, {\cal H}, {\cal B})$ where $X$ is a $v$-element set of points, ${\cal H} = \{H_1,H_2,\ldots,H_r\}$ is a partition of $X$ into holes and ${\cal B}$ is a collection of $4$-element subsets of $X$ called blocks such that every $3$-element subset is either in a block or a hole but not both. In this article we investigate the existence and non-existence of these designs. We settle all parameter situations on at most 24 points, with 6 exceptions. A uniform group divisible Steiner quadruple system is a system in which all the holes have equal size. These were called by Mills G-designs and their existence is completely settled in this article.
The Crossing Number of a Projective Graph is Quadratic in the Face–Width
Authors: Gitler I. , Hliněný P. , Leaños J. , Salazar G.
Published: January 2020

We show that for each integer $g\geq0$ there is a constant $c_g > 0$ such that every graph that embeds in the projective plane with sufficiently large face–width $r$ has crossing number at least $c_g r^2$ in the orientable surface $\Sigma_g$ of genus $g$. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree.
The Map Asymptotics Constant $t_g$
Authors: Bender Edward A. , Gao Zhicheng , Richmond L. Bruce
Published: January 2020

The constant $t_g$ appears in the asymptotic formulas for a variety of rooted maps on the orientable surface of genus $g$. Heretofore, studying this constant has been difficult. A new recursion derived by Goulden and Jackson for rooted cubic maps provides a much simpler recursion for $t_g$ that leads to estimates for its asymptotics.
Hyperbolization of Euclidean Ornaments
Authors: Gagern Martin von , Richter-Gebert Jürgen
Published: January 2020

In this article we outline a method that automatically transforms an Euclidean ornament into a hyperbolic one. The necessary steps are pattern recognition, symmetry detection, extraction of a Euclidean fundamental region, conformal deformation to a hyperbolic fundamental region and tessellation of the hyperbolic plane with this patch. Each of these steps has its own mathematical subtleties that are discussed in this article. In particular, it is discussed which hyperbolic symmetry groups are suitable generalizations of Euclidean wallpaper groups. Furthermore it is shown how one can take advantage of methods from discrete differential geometry in order to perform the conformal deformation of the fundamental region. Finally it is demonstrated how a reverse pixel lookup strategy can be used to obtain hyperbolic images with optimal resolution.
A Multivariate Interlace Polynomial and its Computation for Graphs of Bounded Clique-Width
Authors: Courcelle Bruno
Published: January 2020

We define a multivariate polynomial that generalizes in a unified way the two-variable interlace polynomial defined by Arratia, Bollobás and Sorkin on the one hand, and a one-variable variant of it defined by Aigner and van der Holst on the other. We determine a recursive definition for our polynomial that is based on local complementation and pivoting like the recursive definitions of Tutte's polynomial and of its multivariate generalizations are based on edge deletions and contractions. We also show that bounded portions of our polynomial can be evaluated in polynomial time for graphs of bounded clique-width. Our proof uses an expression of the interlace polynomial in monadic second-order logic, and works actually for every polynomial expressed in monadic second-order logic in a similar way.
Unit Rectangle Visibility Graphs
Authors: Dean Alice M. , Ellis-Monaghan Joanna A. , Hamilton Sarah , Pangborn Greta
Published: January 2020

Over the past twenty years, rectangle visibility graphs have generated considerable interest, in part due to their applicability to VLSI chip design. Here we study unit rectangle visibility graphs, with fixed dimension restrictions more closely modeling the constrained dimensions of gates and other circuit components in computer chip applications. A graph $G$ is a unit rectangle visibility graph (URVG) if its vertices can be represented by closed unit squares in the plane with sides parallel to the axes and pairwise disjoint interiors, in such a way that two vertices are adjacent if and only if there is a non-degenerate horizontal or vertical band of visibility joining the two rectangles. Our results include necessary and sufficient conditions for $K_n$, $K_{m,n}$, and trees to be URVGs, as well as a number of general edge bounds.
Hurwitz Equivalence in Tuples of Generalized Quaternion Groups and Dihedral Groups
Authors: Hou Xiang-dong
Published: January 2020

Let $Q_{2^m}$ be the generalized quaternion group of order $2^m$ and $D_N$ the dihedral group of order $2N$. We classify the orbits in $Q_{2^m}^n$ and $D_{p^m}^n$ ($p$ prime) under the Hurwitz action.
Augmented Rook Boards and General Product Formulas
Authors: Miceli Brian K. , Remmel Jeffrey
Published: January 2020

There are a number of so-called factorization theorems for rook polynomials that have appeared in the literature. For example, Goldman, Joichi and White showed that for any Ferrers board $B = F(b_1, b_2, \ldots, b_n)$, $$\prod_{i=1}^n (x+b_i-(i-1)) = \sum_{k=0}^n r_k(B) (x)\downarrow_{n-k}$$ where $r_k(B)$ is the $k$-th rook number of $B$ and $(x)\downarrow_k = x(x-1) \cdots (x-(k-1))$ is the usual falling factorial polynomial. Similar formulas where $r_k(B)$ is replaced by some appropriate generalization of the $k$-th rook number and $(x)\downarrow_k$ is replaced by polynomials like $(x)\uparrow_{k,j} = x(x+j) \cdots (x+j(k-1))$ or $(x)\downarrow_{k,j} = x(x-j) \cdots (x-j(k-1))$ can be found in the work of Goldman and Haglund, Remmel and Wachs, Haglund and Remmel, and Briggs and Remmel. We shall refer to such formulas as product formulas. The main goal of this paper is to develop a new rook theory setting in which we can give a uniform combinatorial proof of a general product formula that includes, as special cases, essentially all the product formulas referred to above. We shall also prove $q$-analogues and $(p,q)$-analogues of our general product formula.
The $11$-element case of Frankl's conjecture
Authors: Bošnjak Ivica , Marković Petar
Published: January 2020

In 1979, P. Frankl conjectured that in a finite union-closed family ${\cal F}$ of finite sets, ${\cal F}\neq\{\emptyset\}$, there has to be an element that belongs to at least half of the sets in ${\cal F}$. We prove this when $|\bigcup{\cal F}|\leq 11$.
The Scattering Matrix of a Graph
Authors: Mizuno Hirobumi , Sato Iwao
Published: January 2020

Recently, Smilansky expressed the determinant of the bond scattering matrix of a graph by means of the determinant of its Laplacian. We present another proof for this Smilansky's formula by using some weighted zeta function of a graph. Furthermore, we reprove a weighted version of Smilansky's formula by Bass' method used in the determinant expression for the Ihara zeta function of a graph.
A Character on the Quasi-Symmetric Functions coming from Multiple Zeta Values
Authors: Hoffman Michael E.
Published: January 2020

We define a homomorphism $\zeta$ from the algebra of quasi-symmetric functions to the reals which involves the Euler constant and multiple zeta values. Besides advancing the study of multiple zeta values, the homomorphism $\zeta$ appears in connection with two Hirzebruch genera of almost complex manifolds: the $\Gamma$-genus (related to mirror symmetry) and the $\hat{\Gamma}$-genus (related to an $S^1$-equivariant Euler class). We decompose $\zeta$ into its even and odd factors in the sense of Aguiar, Bergeron, and Sottille, and demonstrate the usefulness of this decomposition in computing $\zeta$ on the subalgebra of symmetric functions (which suffices for computations of the $\Gamma$- and $\hat{\Gamma}$-genera).
Circular Degree Choosability
Authors: Norine Serguei , Zhu Xuding
Published: January 2020

We extend a characterization of degree-choosable graphs due to Borodin, and Erdős, Rubin and Taylor, to circular list-colorings.
On the Discrepancy of Quasi-Progressions
Authors: Vijay Sujith
Published: January 2020

A quasi-progression, also known as a Beatty sequence, consists of successive multiples of a real number, with each multiple rounded down to the largest integer not exceeding it. In 1986, Beck showed that given any $2$-colouring, the hypergraph of quasi-progressions contained in $\{0,1,\ldots,n \}$ corresponding to almost all real numbers in $(1, \infty)$ have discrepancy at least $\log^{*} n$, the inverse of the tower function. We improve the lower bound to $(\log n)^{1/4 - o(1)}$, and also show that there is some quasi-progression with discrepancy at least $(1/50) n^{1/6}$. The results remain valid even if the $2$-colouring is replaced by a partial colouring of positive density.
Laplacian Integral Graphs with Maximum Degree $3$
Authors: Kirkland Steve
Published: January 2020

A graph is said to be Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. Using combinatorial and matrix-theoretic techniques, we identify, up to isomorphism, the $21$ connected Laplacian integral graphs of maximum degree $3$ on at least $6$ vertices.
The Ramsey Number of Diamond-Matchings and Loose Cycles in Hypergraphs
Authors: Gyárfás András , Sárközy Gábor N. , Szemerédi Endre
Published: January 2020

The $2$-color Ramsey number $R({\cal{C}}_n^3,{\cal{C}}_n^3)$ of a $3$-uniform loose cycle ${\cal{C}}_n$ is asymptotic to $5n/4$ as has been recently proved by Haxell, Łuczak, Peng, Rödl, Ruciński, Simonovits and Skokan. Here we extend their result to the $r$-uniform case by showing that the corresponding Ramsey number is asymptotic to ${(2r-1)n\over 2r-2}$. Partly as a tool, partly as a subject of its own, we also prove that for $r\ge 2$, $R(kD_r,kD_r)=k(2r-1)-1$ and $R(kD_r,kD_r,kD_r)=2kr-2$ where $kD_r$ is the hypergraph having $k$ disjoint copies of two $r$-element hyperedges intersecting in two vertices.
Discovering Hook Length Formulas by an Expansion Technique
Authors: Han Guo-Niu
Published: January 2020

We introduce a hook length expansion technique and explain how to discover old and new hook length formulas for partitions and plane trees. The new hook length formulas for trees obtained by our method can be proved rather easily, whereas those for partitions are much more difficult and some of them still remain open conjectures. We also develop a Maple package HookExp for computing the hook length expansion. The paper can be seen as a collection of hook length formulas for partitons and plane trees. All examples are illustrated by HookExp and, for many easy cases, expained by well-known combinatorial arguments.
Strongly Maximal Matchings in Infinite Graphs
Authors: Aharoni Ron , Berger Eli , Georgakopoulos Agelos , Sprüssel Philipp
Published: January 2020

Given an assignment of weights $w$ to the edges of an infinite graph $G$, a matching $M$ in $G$ is called strongly $w$-maximal if for any matching $N$ there holds $\sum\{w(e) \mid e \in N \setminus M\} \le \sum\{w(e) \mid e \in M \setminus N\}$. We prove that if $w$ assumes only finitely many values all of which are rational then $G$ has a strongly $w$-maximal matching. This result is best possible in the sense that if we allow irrational values or infinitely many values then there need not be a strongly $w$-maximal matching.
Universally Image Partition Regularity
Authors: De Dibyendu , Paul Ram Krishna
Published: January 2020

Many of the classical results of Ramsey Theory, for example Schur's Theorem, van der Waerden's Theorem, Finite Sums Theorem, are naturally stated in terms of image partition regularity of matrices. Many characterizations are known of image partition regularity over ${\Bbb N}$ and other subsemigroups of $({\Bbb R},+)$. In this paper we introduce a new notion which we call universally image partition regular matrices, which are in fact image partition regular over all semigroups and everywhere. We also prove that such matrices exist in abundance.
Dihedral f-Tilings of the Sphere by Equilateral and Scalene Triangles - III
Authors: Breda A. M. d'Azevedo , Ribeiro Patrícia S. , Santos Altino F.
Published: January 2020

The study of spherical dihedral f-tilings by equilateral and isosceles triangles was introduced in [3]. Taking as prototiles equilateral and scalene triangles, we are faced with three possible ways of adjacency. In [4] and [5] two of these possibilities were studied. Here, we complete this study, describing the f-tilings related to the remaining case of adjacency, including their symmetry groups. A table summarizing the results concerning all dihedral f-tilings by equilateral and scalene triangles is given in Table 2.
A Complete Grammar for Decomposing a Family of Graphs into 3-Connected Components
Authors: Chapuy Guillaume , Fusy Éric , Kang Mihyun , Shoilekova Bilyana
Published: January 2020

Tutte has described in the book "Connectivity in graphs" a canonical decomposition of any graph into 3-connected components. In this article we translate (using the language of symbolic combinatorics) Tutte's decomposition into a general grammar expressing any family ${\cal G}$ of graphs (with some stability conditions) in terms of the subfamily ${\cal G}_3$ of graphs in ${\cal G}$ that are 3-connected (until now, such a general grammar was only known for the decomposition into $2$-connected components). As a byproduct, our grammar yields an explicit system of equations to express the series counting a (labelled) family of graphs in terms of the series counting the subfamily of $3$-connected graphs. A key ingredient we use is an extension of the so-called dissymmetry theorem, which yields negative signs in the grammar and associated equation system, but has the considerable advantage of avoiding the difficult integration steps that appear with other approaches, in particular in recent work by Giménez and Noy on counting planar graphs. As a main application we recover in a purely combinatorial way the analytic expression found by Giménez and Noy for the series counting labelled planar graphs (such an expression is crucial to do asymptotic enumeration and to obtain limit laws of various parameters on random planar graphs). Besides the grammar, an important ingredient of our method is a recent bijective construction of planar maps by Bouttier, Di Francesco and Guitter. Finally, our grammar applies also to the case of unlabelled structures, since the dissymetry theorem takes symmetries into account. Even if there are still difficulties in counting unlabelled 3-connected planar graphs, we think that our grammar is a promising tool toward the asymptotic enumeration of unlabelled planar graphs, since it circumvents some difficult integral calculations.
A Traceability Conjecture for Oriented Graphs
Authors: Frick Marietjie , Van Aardt Susan A , Dunbar Jean E , Nielsen Morten H , Oellermann Ortrud R
Published: January 2020

A (di)graph $G$ of order $n$ is $k$-traceable (for some $k$, $1\leq k\leq n$) if every induced sub(di)graph of $G$ of order $k$ is traceable. It follows from Dirac's degree condition for hamiltonicity that for $k\geq2$ every $k$-traceable graph of order at least $2k-1$ is hamiltonian. The same is true for strong oriented graphs when $k=2,3,4,$ but not when $k\geq5$. However, we conjecture that for $k\geq2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. The truth of this conjecture would imply the truth of an important special case of the Path Partition Conjecture for Oriented Graphs. In this paper we show the conjecture is true for $k \leq 5$ and for certain classes of graphs. In addition we show that every strong $k$-traceable oriented graph of order at least $6k-20$ is traceable. We also characterize those graphs for which all walkable orientations are $k$-traceable.
Lattice Points in Minkowski Sums
Authors: Haase Christian , Nill Benjamin , Paffenholz Andreas , Santos Francisco
Published: January 2020

Fakhruddin has proved that for two lattice polygons $P$ and $Q$ any lattice point in their Minkowski sum can be written as a sum of a lattice point in $P$ and one in $Q$, provided $P$ is smooth and the normal fan of $P$ is a subdivision of the normal fan of $Q$. We give a shorter combinatorial proof of this fact that does not need the smoothness assumption on $P$.
How Long Can a Graph be Kept Planar?
Authors: Anuradha V. , Jain Chinmay , Snoeyink Jack , Szabó Tibor
Published: January 2020

The graph (non-)planarity game is played on the complete graph $K_n$ between an Enforcer and an Avoider, each of whom take one edge per round. The game ends when the edges chosen by Avoider form a non-planar subgraph. We show that Avoider can play for $3n-26$ turns, improving the previous bound of $3n-28\sqrt n$.
Shellability of a Poset of Polygonal Subdivisions
Authors: Ekedahl Torsten
Published: January 2020

We introduce a sequence of posets closely related to the associahedra. In this we are motivated by reasons similar to those of Stasheff in the case of the associahedra. We make a study of this poset showing that it has an inductive structure with proper downwards intervals being products of smaller posets in the same series and associahedra. Using this we also show that they are thin dual CL-shellable and in particular that they are the face poset of a regular cell decomposition of the ball.
Bijective Proofs of Identities from Colored Binary Trees
Authors: Yan Sherry H.F.
Published: January 2020

This note provides bijective proofs of two combinatorial identities involving generalized Catalan number $C_{m,5}(n)={m\over 5n+m}{5n+m\choose n}$ recently proposed by Sun.
A Note on Polynomials and $f$-Factors of Graphs
Authors: Shirazi Hamed , Verstraëte Jacques
Published: January 2020

Let $G = (V,E)$ be a graph, and let $f : V \rightarrow 2^{\Bbb Z}$ be a function assigning to each $v \in V$ a set of integers in $\{0,1,2,\dots,d(v)\}$, where $d(v)$ denotes the degree of $v$ in $G$. Lovász defines an $f$-factor of $G$ to be a spanning subgraph $H$ of $G$ in which $d_{H}(v) \in f(v)$ for all $v \in V$. Using the combinatorial nullstellensatz of Alon, we prove that if $|f(v)| > \lceil {1\over 2}d(v) \rceil$ for all $v \in V$, then $G$ has an $f$-factor. This result is best possible and verifies a conjecture of Addario-Berry, Dalal, Reed and Thomason.
On Harmonious Colouring of Trees
Authors: Aflaki A. , Akbari S. , Edwards K.J. , Eskandani D.S. , Jamaali M. , Ravanbod H.
Published: January 2020

Let $G$ be a simple graph and $\Delta(G)$ denote the maximum degree of $G$. A harmonious colouring of $G$ is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number $h(G)$ is the least number of colours in such a colouring. In this paper it is shown that if $T$ is a tree of order $n$ and $\Delta(T)\geq\frac{n}{2}$, then there exists a harmonious colouring of $T$ with $\Delta(T)+1$ colours such that every colour is used at most twice. Thus $h(T)=\Delta(T)+1$. Moreover, we prove that if $T$ is a tree of order $n$ and $\Delta(T) \le \Big\lceil\frac{n}{2}\Big\rceil$, then there exists a harmonious colouring of $T$ with $\Big\lceil \frac{n}{2}\Big \rceil +1$ colours such that every colour is used at most twice. Thus $h(T)\leq \Big\lceil \frac{n}{2} \Big\rceil +1$.
On the Diameter of Matroid Ports
Authors: Martí-Farré Jaume , Padró Carles , Vázquez Leonor
Published: January 2020

A clutter or antichain on a set defines a hypergraph. Matroid ports are a special class of clutters, and this paper deals with the diameter of matroid ports, that is, the diameter of the corresponding hypergraphs. Specifically, we prove that the diameter of every matroid port is at most $2$. The main interest of our result is its application to secret sharing. Brickell and Davenport proved in 1989 that the minimal qualified subsets of every ideal secret sharing scheme form a matroid port. Therefore, our result provides a new necessary condition for an access structure to admit an ideal secret sharing scheme.
Evaluation of a Multiple Integral of Tefera via Properties of the Exponential Distribution
Authors: Yu Yaming
Published: January 2020

An interesting integral originally obtained by Tefera ("A multiple integral evaluation inspired by the multi-WZ method," Electron. J. Combin., 1999, #N2) via the WZ method is proved using calculus and basic probability. General recursions for a class of such integrals are derived and associated combinatorial identities are mentioned.
Coupon Collecting with Quotas
Authors: May Russell
Published: January 2020

We analyze a variant of the coupon collector's problem, in which the probabilities of obtaining coupons and the numbers of coupons in a collection may be non-uniform. We obtain a finite expression for the generating function of the probabilities to complete a collection and show how this generalizes several previous results about the coupon collector's problem. Also, we provide applications about computational complexity and approximation.
Minimal Percolating Sets in Bootstrap Percolation
Authors: Morris Robert
Published: January 2020

In standard bootstrap percolation, a subset $A$ of the grid $[n]^2$ is initially infected. A new site is then infected if at least two of its neighbours are infected, and an infected site stays infected forever. The set $A$ is said to percolate if eventually the entire grid is infected. A percolating set is said to be minimal if none of its subsets percolate. Answering a question of Bollobás, we show that there exists a minimal percolating set of size $4n^2/33 + o(n^2)$, but there does not exist one larger than $(n + 2)^2/6$.
On Domination in 2-Connected Cubic Graphs
Authors: Stodolsky B. Y.
Published: January 2020

In 1996, Reed proved that the domination number, $\gamma(G)$, of every $n$-vertex graph $G$ with minimum degree at least $3$ is at most $3n/8$ and conjectured that $\gamma(H)\leq\lceil n/3\rceil$ for every connected $3$-regular (cubic) $n$-vertex graph $H$. In [1] this conjecture was disproved by presenting a connected cubic graph $G$ on $60$ vertices with $\gamma(G)=21$ and a sequence $\{G_k\}_{k=1}^{\infty}$ of connected cubic graphs with $\lim_{k\to\infty}{\gamma(G_k)\over|V(G_k)|} \geq{1\over3}+{1\over69}$. All the counter-examples, however, had cut-edges. On the other hand, in [2] it was proved that $\gamma(G)\leq\ 4n/11$ for every connected cubic $n$-vertex graph $G$ with at least $10$ vertices. In this note we construct a sequence of graphs $\{G_k\}_{k=1}^{\infty}$ of $2$-connected cubic graphs with $\lim_{k\to\infty}{\gamma(G_k)\over|V(G_k)|} \geq{1\over3}+{1\over78}$, and a sequence $\{G_l'\}_{l=1}^{\infty}$ of connected cubic graphs where for each $G_l'$ we have ${\gamma(G_l')\over|V(G_l')|} >{1\over3}+{1\over69}$.
A Pairing Strategy for Tic-Tac-Toe on the Integer Lattice with Numerous Directions
Authors: Kruczek Klay , Sundberg Eric
Published: January 2020

We consider a tic-tac-toe game played on the $d$-dimensional integer lattice. The game that we investigate is a Maker–Breaker version of tic-tac-toe. In a Maker–Breaker game, the first player, Maker, only tries to occupy a winning line and the second player, Breaker, only tries to stop Maker from occupying a winning line. We consider the bounded number of directions game, in which we designate a finite set of direction-vectors ${\cal S} \subset{\Bbb Z}^d$ which determine the set of winning lines. We show by a simple pairing strategy that Breaker can win this game if the length of each winning line is at least $3|{\cal S}|.$ It should be noted that Breaker's winning strategy can be used as a drawing strategy for Player 2 in the strong version of this game.
Erdős-Ko-Rado-Type Theorems for Colored Sets
Authors: Li Yu-Shuang , Wang Jun
Published: January 2020

An Erdős-Ko-Rado-type theorem was established by Bollobás and Leader for $q$-signed sets and by Ku and Leader for partial permutations. In this paper, we establish an LYM-type inequality for partial permutations, and prove Ku and Leader's conjecture on maximal $k$-uniform intersecting families of partial permutations. Similar results on general colored sets are presented.
Nonabelian Groups with $(96,20,4)$ Difference Sets
Authors: AbuGhneim Omar A. , Smith Ken W.
Published: January 2020

We resolve the existence problem of $(96,20,4)$ difference sets in 211 of 231 groups of order $96$. If $G$ is a group of order $96$ with normal subgroups of orders $3$ and $4$ then by first computing $32$- and $24$-factor images of a hypothetical $(96,20,4)$ difference set in $G$ we are able to either construct a difference set or show a difference set does not exist. Of the 231 groups of order 96, 90 groups admit $(96,20,4)$ difference sets and $121$ do not. The ninety groups with difference sets provide many genuinely nonabelian difference sets. Seven of these groups have exponent 24. These difference sets provide at least $37$ nonisomorphic symmetric $(96,20,4)$ designs.
Coloured Generalised Young Diagrams for Affine Weyl-Coxeter Groups
Authors: King R. C. , Welsh T. A.
Published: January 2020

Coloured generalised Young diagrams $T(w)$ are introduced that are in bijective correspondence with the elements $w$ of the Weyl-Coxeter group $W$ of $\mathfrak{g}$, where $\mathfrak{g}$ is any one of the classical affine Lie algebras $\mathfrak{g}=A^{(1)}_\ell$, $B^{(1)}_\ell$, $C^{(1)}_\ell$, $D^{(1)}_\ell$, $A^{(2)}_{2\ell}$, $A^{(2)}_{2\ell-1}$ or $D^{(2)}_{\ell+1}$. These diagrams are coloured by means of periodic coloured grids, one for each $\mathfrak{g}$, which enable $T(w)$ to be constructed from any expression $w=s_{i_1}s_{i_2}\cdots s_{i_t}$ in terms of generators $s_k$ of $W$, and any (reduced) expression for $w$ to be obtained from $T(w)$. The diagram $T(w)$ is especially useful because $w(\Lambda)-\Lambda$ may be readily obtained from $T(w)$ for all $\Lambda$ in the weight space of $\mathfrak{g}$. With $\overline{\mathfrak{g}}$ a certain maximal finite dimensional simple Lie subalgebra of $\mathfrak{g}$, we examine the set $W_s$ of minimal right coset representatives of $\overline{W}$ in $W$, where $\overline{W}$ is the Weyl-Coxeter group of $\overline{\mathfrak{g}}$. For $w\in W_s$, we show that $T(w)$ has the shape of a partition (or a slight variation thereof) whose $r$-core takes a particularly simple form, where $r$ or $r/2$ is the dual Coxeter number of $\mathfrak{g}$. Indeed, it is shown that $W_s$ is in bijection with such partitions.
The $m$-Colored Composition Poset
Authors: Drake Brian , Petersen T. Kyle
Published: January 2020

We define a partial order on colored compositions with many properties analogous to Young's lattice. We show that saturated chains correspond to colored permutations, and that covering relations correspond to a Pieri-type rule for colored quasi-symmetric functions. We also show that the poset is CL-shellable. In the case of a single color, we recover the subword order on binary words.
A Characterization of Balanced Episturmian Sequences
Authors: Paquin Geneviève , Vuillon Laurent
Published: January 2020

It is well-known that Sturmian sequences are the non ultimately periodic sequences that are balanced over a 2-letter alphabet. They are also characterized by their complexity: they have exactly $(n+1)$ distinct factors of length $n$. A natural generalization of Sturmian sequences is the set of infinite episturmian sequences. These sequences are not necessarily balanced over a $k$-letter alphabet, nor are they necessarily aperiodic. In this paper, we characterize balanced episturmian sequences, periodic or not, and prove Fraenkel's conjecture for the special case of episturmian sequences. It appears that balanced episturmian sequences are all ultimately periodic and they can be classified in 3 families.
Distinguishing Infinite Graphs
Authors: Imrich Wilfried , Klavžar Sandi , Trofimov Vladimir
Published: January 2020

The distinguishing number $D(G)$ of a graph $G$ is the least cardinal number $\aleph$ such that $G$ has a labeling with $\aleph$ labels that is only preserved by the trivial automorphism. We show that the distinguishing number of the countable random graph is two, that tree-like graphs with not more than continuum many vertices have distinguishing number two, and determine the distinguishing number of many classes of infinite Cartesian products. For instance, $D(Q_{n}) = 2$, where $Q_{n}$ is the infinite hypercube of dimension ${n}$.
Arranging Numbers on Circles to Reach Maximum Total Variations
Authors: Liao Ying-Jie , Shieh Min-Zheng , Tsai Shi-Chun
Published: January 2020

The dartboard problem is to arrange $n$ numbers on a circle to obtain maximum risk, which is the sum of the $q$-th power of the absolute differences of adjacent numbers, for $q\ge 1$. Curtis showed that the dartboard problem admits a greedy algorithm. We generalize the dartboard problem by considering more circles and the goal is to arrange $kn$ number on $k$ circles to obtain the maximum risk. In this paper, we characterize an optimal arrangement for $k=2$ and show that the generalized dartboard problem also admits a greedy algorithm.
Tilings of the sphere with right triangles III: the asymptotically obtuse families
Authors: Dawson Robert J. MacG. , Doyle Blair
Published: January 2020

Sommerville and Davies classified the spherical triangles that can tile the sphere in an edge-to-edge fashion. However, if the edge-to-edge restriction is relaxed, there are other such triangles; here, we continue the classification of right triangles with this property begun in our earlier papers. We consider six families of triangles classified as "asymptotically obtuse", and show that they contain two non-edge-to-edge tiles, one (with angles of $90^\circ$, $105^\circ$ and $45^\circ)$ believed to be previously unknown.
Maximal Projective Degrees for Strict Partitions
Authors: Bernstein D. , Henke A. , Regev A.
Published: January 2020

Let $\lambda$ be a partition, and denote by $f^\lambda$ the number of standard tableaux of shape $\lambda$. The asymptotic shape of $\lambda$ maximizing $f^\lambda$ was determined in the classical work of Logan and Shepp and, independently, of Vershik and Kerov. The analogue problem, where the number of parts of $\lambda$ is bounded by a fixed number, was done by Askey and Regev – though some steps in this work were assumed without a proof. Here these steps are proved rigorously. When $\lambda$ is strict, we denote by $g^\lambda$ the number of standard tableau of shifted shape $\lambda$. We determine the partition $\lambda$ maximizing $g^\lambda$ in the strip. In addition we give a conjecture related to the maximizing of $g^\lambda$ without any length restrictions.
Hereditary Properties of Tournaments
Authors: Balogh József , Bollobás Béla , Morris Robert
Published: January 2020

A collection of unlabelled tournaments ${\cal P}$ is called a hereditary property if it is closed under isomorphism and under taking induced sub-tournaments. The speed of ${\cal P}$ is the function $n \mapsto |{\cal P}_n|$, where ${\cal P}_n = \{T \in {\cal P} : |V(T)| = n\}$. In this paper, we prove that there is a jump in the possible speeds of a hereditary property of tournaments, from polynomial to exponential speed. Moreover, we determine the minimal exponential speed, $|{\cal P}_n| = c^{(1+o(1))n}$, where $c \simeq 1.47$ is the largest real root of the polynomial $x^3 = x^2 + 1$, and the unique hereditary property with this speed.
Explicit Enumeration of Triangulations with Multiple Boundaries
Authors: Krikun Maxim
Published: January 2020

We enumerate rooted triangulations of a sphere with multiple holes by the total number of edges and the length of each boundary component. The proof relies on a combinatorial identity due to W.T. Tutte.
Ternary Linear Codes and Quadrics
Authors: Yoshida Yuri , Maruta Tatsuya
Published: January 2020

For an $[n,k,d]_3$ code ${\cal C}$ with $gcd(d,3)=1$, we define a map $w_G$ from $\Sigma={\rm PG}(k-1,3)$ to the set of weights of codewords of ${\cal C}$ through a generator matrix $G$. A $t$-flat $\Pi$ in $\Sigma$ is called an $(i,j)_t$ flat if $(i,j)=(|\Pi \cap F_0|,|\Pi \cap F_1|)$, where $F_0 = \{P \in \Sigma | w_G(P) \equiv 0 \pmod{3}\}$, $F_1 = \{P \in \Sigma | w_G(P) \not\equiv 0,d \pmod{3}\}$. We give geometric characterizations of $(i,j)_t$ flats, which involve quadrics. As an application to the optimal linear codes problem, we prove the non-existence of a $[305,6,202]_3$ code, which is a new result.
Compact Hyperbolic Coxeter $n$-Polytopes with $n+3$ Facets
Authors: Tumarkin Pavel
Published: January 2020

We use methods of combinatorics of polytopes together with geometrical and computational ones to obtain the complete list of compact hyperbolic Coxeter $n$-polytopes with $n+3$ facets, $4\le n\le 7$. Combined with results of Esselmann this gives the classification of all compact hyperbolic Coxeter $n$-polytopes with $n+3$ facets, $n\ge 4$. Polytopes in dimensions $2$ and $3$ were classified by Poincaré and Andreev.
Unbounded Regions of Infinitely Logconcave Sequences
Authors: Uminsky David , Yeats Karen
Published: January 2020

We study the properties of a logconcavity operator on a symmetric, unimodal subset of finite sequences. In doing so we are able to prove that there is a large unbounded region in this subset that is $\infty$-logconcave. This problem was motivated by the conjecture of Boros and Moll that the binomial coefficients are $\infty$-logconcave.
The Cluster Basis of ${\Bbb Z}[x_{1,1},\dots, x_{3,3}]$
Authors: Skandera Mark
Published: January 2020

We show that the set of cluster monomials for the cluster algebra of type $D_4$ contains a basis of the ${\Bbb Z}$-module ${\Bbb Z}[x_{1,1},\dots,x_{3,3}]$. We also show that the transition matrices relating this cluster basis to the natural and the dual canonical bases are unitriangular and nonnegative. These results support a conjecture of Fomin and Zelevinsky on the equality of the cluster and dual canonical bases. In the event that this conjectured equality is true, our results also imply an explicit factorization of each dual canonical basis element as a product of cluster variables.
Color Neighborhood Union Conditions for Long Heterochromatic Paths in Edge-Colored Graphs
Authors: Chen He , Li Xueliang
Published: January 2020

Let $G$ be an edge-colored graph. A heterochromatic (rainbow, or multicolored) path of $G$ is such a path in which no two edges have the same color. Let $CN(v)$ denote the color neighborhood of a vertex $v$ of $G$. In a previous paper, we showed that if $|CN(u)\cup CN(v)|\geq s$ (color neighborhood union condition) for every pair of vertices $u$ and $v$ of $G$, then $G$ has a heterochromatic path of length at least $\lfloor{2s+4\over5}\rfloor$. In the present paper, we prove that $G$ has a heterochromatic path of length at least $\lceil{s+1\over2}\rceil$, and give examples to show that the lower bound is best possible in some sense.
Matroid Automorphisms of the $F_4$ Root System
Authors: Fried Stephanie , Gerek Aydin , Gordon Gary , Peruničić Andrija
Published: January 2020

Let $F_4$ be the root system associated with the 24-cell, and let $M(F_4)$ be the simple linear dependence matroid corresponding to this root system. We determine the automorphism group of this matroid and compare it to the Coxeter group $W$ for the root system. We find non-geometric automorphisms that preserve the matroid but not the root system.
Flexibility of Embeddings of Bouquets of Circles on the Projective Plane and Klein Bottle
Authors: Yang Yan , Liu Yanpei
Published: January 2020

In this paper, we study the flexibility of embeddings of bouquets of circles on the projective plane and the Klein bottle. The numbers (of equivalence classes) of embeddings of bouquets of circles on these two nonorientable surfaces are obtained in explicit expressions. As their applications, the numbers (of isomorphism classes) of rooted one-vertex maps on these two nonorientable surfaces are deduced.
PEMETAAN PRILAKU PENGGUNAAN MEDIA INFORMASI DALAM MENGAKSES INFORMASI KESEHATAN REPRODUKSI DI KALANGAN PELAJAR DI JAWA BARAT
Authors: Dida Susanne , Lukman Syauqy , Sono Sukarno , Herison Feliza , Priyatna Centurion Chandratama , Zaidan Arif Rifqi , Prihyugiarto Titut Yuli
Published: January 2020

Penelitian ini bertujuan untuk (a) mengetahui dan kemudian menjabarkan perilaku penggunaan media informasi di kalangan remaja dalam mencari informasi tentang kesehatan reproduksi; serta (b) perilaku penggunaan internetnya. Penelitian ini menggunakan metode deskriptif dengan populasi remaja tahun pertama hingga keempat dengan rentang umur 18 hingga 24 tahun yang berada di Jawa Barat. Penggumpulan data akan dilakukan melalui angket, wawancara dan observasi. Tipe penelitian ini adalah penelitian deskriptif dengan data kualitatif dan kuantitatif yang dilakukan dengan tujuan menggambarkan atau mendeskripsikan obyek dan fenomena yang berkaitan dengan komunikasi kesehatan, khususnya seputar informasi kesehatan reproduksi di kalangan remaja dengan tujuan untuk memetakan pola, prilaku penggunaan media informasi di kalangan remaja di Jawa Barat. Hasil dari penelitian menunjukkan bahwa platform media informasi yang banyak diakses di kalangan remaja adalah melalui media sosial, paling tinggi instagram dan twitter sedangkan paling rendah koran kemudian diikuti radio. Metode penyampaian pesan dengan infografis dan meme dirasa paling efektif disampaikan melalui media sosial, ini menjadi sesuatu yang perlu diperhatikan dalam mengemas pesan-pesan kesehatan reproduksi untuk remaja, baik oleh BKKBN, maupun pihak-pihak lain yang berkepentingan.