bluuebunny/crossref_metadata_2025 huggingface dataset:
Ramsey equivalence of $K_n$ and $K_n+K_{n-1}$
Authors: Bloom Thomas F. , Liebenau Anita
Published: January 2020

We prove that, for $n\geqslant 4$, the graphs $K_n$ and $K_n+K_{n-1}$ are Ramsey equivalent. That is, if $G$ is such that any red-blue colouring of its edges creates a monochromatic $K_n$ then it must also possess a monochromatic $K_n+K_{n-1}$. This resolves a conjecture of Szabó, Zumstein, and Zürcher.The result is tight in two directions. Firstly, it is known that $K_n$ is not Ramsey equivalent to $K_n+2K_{n-1}$. Secondly, $K_3$ is not Ramsey equivalent to $K_3+K_{2}$. We prove that any graph which witnesses this non-equivalence must contain $K_6$ as a subgraph.
Analogies between the Crossing Number and the Tangle Crossing Number
Authors: Anderson Robin , Bai Shuliang , Barrera-Cruz Fidel , Czabarka Éva , Da Lozzo Giordano , Hobson Natalie L. F. , Lin Jephian C.-H. , Mohr Austin , Smith Heather C. , Székely László A. , Whitlatch Hays
Published: January 2020

Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching between the two leaf-sets. These objects are of use in phylogenetics and are represented with straight-line drawings where the leaves of the two plane binary trees are on two parallel lines and only the matching edges can cross. The tangle crossing number of a tanglegram is the minimum number of crossings over all such drawings and is related to biologically relevant quantities, such as the number of times a parasite switched hosts.Our main results for tanglegrams which parallel known theorems for crossing numbers are as follows. The removal of a single matching edge in a tanglegram with $n$ leaves decreases the tangle crossing number by at most $n-3$, and this is sharp. Additionally, if $\gamma(n)$ is the maximum tangle crossing number of a tanglegram with $n$ leaves, we prove $\frac{1}{2}\binom{n}{2}(1-o(1))\le\gamma(n)<\frac{1}{2}\binom{n}{2}$. For an arbitrary tanglegram $T$, the tangle crossing number, $\mathrm{crt}(T)$, is NP-hard to compute (Fernau et al. 2005). We provide an algorithm which lower bounds $\mathrm{crt}(T)$ and runs in $O(n^4)$ time. To demonstrate the strength of the algorithm, simulations on tanglegrams chosen uniformly at random suggest that the tangle crossing number is at least $0.055n^2$ with high probabilty, which matches the result that the tangle crossing number is $\Theta(n^2)$ with high probability (Czabarka et al. 2017).
Circular Chromatic Index of Generalized Blanuša Snarks
Authors: Ghebleh Mohammad
Published: January 2020

In his Master's thesis, Ján Mazák proved that the circular chromatic index of the type 1 generalized Blanuša snark $B^1_n$ equals $3+{2\over n}$. This result provided the first infinite set of values of the circular chromatic index of snarks. In this paper we show the type 2 generalized Blanuša snark $B^2_n$ has circular chromatic index $3+{1/\lfloor{1+3n/2}\rfloor}$. In particular, this proves that all numbers $3+1/n$ with $n\ge 2$ are realized as the circular chromatic index of a snark. For $n=1,2$ our proof is computer-assisted.
Primary Decomposition of Ideals of Lattice Homomorphisms
Authors: Sharifan Leila , Estaji Ali Akbar , Malekbala Ghazaleh
Published: January 2020

For two given finite lattices $L$ and $M$, we introduce the ideal of lattice homomorphism $J(L,M)$, whose minimal monomial generators correspond to lattice homomorphisms $\phi : L\to M$. We show that $L$ is a distributive lattice if and only if the equidimensinal part of $J(L,M)$ is the same as the equidimensional part of the ideal of poset homomorphisms $I(L,M)$. Next, we study the minimal primary decomposition of $J(L,M)$ when $L$ is a distributive lattice and $M=[2]$. We present some methods to check if a monomial prime ideal belongs to $\mathrm{ass}(J(L,[2]))$, and we give an upper bound in terms of combinatorial properties of $L$ for the height of the minimal primes. We also show that if each minimal prime ideal of $J(L,[2])$ has height at most three, then $L$ is a planar lattice and $\mathrm{width}(L)\leq 2$. Finally, we compute the minimal primary decomposition when $L=[m]\times [n]$ and $M=[2]$.
The Rise-Contact Involution on Tamari Intervals
Authors: Pons Viviane
Published: January 2020

We describe an involution on Tamari intervals and $m$-Tamari intervals. This involution switches two sets of statistics known as the "rises" and the "contacts" and so proves an open conjecture from Préville-Ratelle on intervals of the $m$-Tamari lattice.
A Limit Theorem for the Six-length of Random Functional Graphs with a Fixed Degree Sequence
Authors: Leckey Kevin , Wormald Nick
Published: January 2020

We obtain results on the limiting distribution of the six-length of a random functional graph, also called a   functional digraph or random mapping, with given in-degree sequence. The six-length  of a vertex $v\in V$  is defined from the associated mapping, $f:V\to V$, to be the maximum $i\in V$ such that the elements $v, f(v), \ldots, f^{i-1}(v)$ are all distinct. This has relevance to the study of algorithms for integer factorisation.
Hypergraph Saturation Irregularities
Authors: Behague Natalie C.
Published: January 2020

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.
A New Lower Bound for the Size of an Affine Blocking Set
Authors: De Boeck Maarten , Van de Voorde Geertrui
Published: January 2020

A blocking set in an affine plane is a set of points $B$ such that every line contains at least one point of $B$. The best known lower bound for blocking sets in arbitrary (non-desarguesian) affine planes was derived in the 1980's by Bruen and Silverman. In this note, we improve on this result by showing that a blocking set of an affine plane of order $q$, $q\geqslant 25$, contains at least $q+\lfloor\sqrt{q}\rfloor+3$ points.
The Matching Polynomials and Spectral Radii of Uniform Supertrees
Authors: Su Li , Kang Liying , Li Honghai , Shan Erfang
Published: January 2020

We study matching polynomials of uniform hypergraph and spectral radii of uniform supertrees. By comparing the matching polynomials of supertrees, we extend Li and Feng's results on grafting operations on graphs to supertrees. Using the methods of grafting operations on supertrees and comparing matching polynomials of supertrees, we determine the first $\lfloor\frac{d}{2}\rfloor+1$ largest spectral radii of $r$-uniform supertrees with size $m$ and diameter $d$. In addition, the first two smallest spectral radii of supertrees with size $m$ are determined.
The Canonical Join Complex
Authors: Barnard Emily
Published: January 2020

A canonical join representation is a certain minimal "factorization" of an element in a finite lattice $L$ analogous to the prime factorization of an integer from number theory. The expression $\bigvee A =w$ is the canonical join representation of $w$ if $A$ is the unique lowest subset of $L$ satisfying $\bigvee A=w$ (where "lowest" is made precise by comparing order ideals under containment). Canonical join representations appear in many familiar guises, with connections to comparability graphs and noncrossing partitions. When each element in $L$ has a canonical join representation, we define the canonical join complex to be the abstract simplicial complex of subsets $A$ such that $\bigvee A$ is a canonical join representation. We characterize the class of finite lattices whose canonical join complex is flag, and show how the canonical join complex is related to the topology of $L$.
Derangements and Euler's difference table for $C_\ell\wr S_n$
Authors: Faliharimalala Hilarion L. M. , Zeng Jiang
Published: January 2020

Euler's difference table associated to the sequence $\{n!\}$ leads naturally to the counting formula for the derangements. In this paper we study Euler's difference table associated to the sequence $\{\ell^n n!\}$ and the generalized derangement problem. For the coefficients appearing in the later table we will give the combinatorial interpretations in terms of two kinds of $k$-successions of the group $C_\ell\wr S_n$. In particular for $\ell=1$ we recover the known results for the symmetric groups while for $\ell=2$ we obtain the corresponding results for the hyperoctahedral groups.
A Bijection for Essentially 4-Connected Toroidal Triangulations
Authors: Bonichon Nicolas , Lévêque Benjamin
Published: January 2020

Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have been intensively studied and used for many applications (drawing algorithm, random generation, enumeration, ...). In this paper we introduce and study a generalization of these objects for the toroidal case. Contrary to what happens in the plane, the set of toroidal transversal structures of a given toroidal triangulation is partitioned into several distributive lattices. We exhibit a subset of toroidal transversal structures, called balanced, and show that it forms a single distributive lattice. Then, using the minimal element of the lattice, we are able to enumerate bijectively essentially 4-connected toroidal triangulations.
Cumulative Subtraction Games
Authors: Cohensius Gal , Larsson Urban , Meir Reshef , Wahlstedt David
Published: January 2020

We study a variation of Nim-type subtraction games, called Cumulative Subtraction (CS). Two players alternate in removing pebbles out of a joint pile, and their actions add or remove points to a common score. We prove that the zero-sum outcome in optimal play of a CS with a finite number of possible actions is eventually periodic, with period $2s$, where $s$ is the size of the largest available action. This settles a conjecture by Stewart in his Ph.D. thesis (2011). Specifically, we find a quadratic bound, in the size of $s$, on when the outcome function must have become periodic. In case of exactly two possible actions, we give an explicit description of optimal play.
Lattice Homomorphisms Between Weak Orders
Authors: Reading Nathan
Published: January 2020

We classify surjective lattice homomorphisms $W\to W'$ between the weak orders on finite Coxeter groups.  Equivalently, we classify lattice congruences $\Theta$ on $W$ such that the quotient $W/\Theta$ is isomorphic to $W'$.  Surprisingly, surjective homomorphisms exist quite generally:  They exist if and only if the diagram of $W'$ is obtained from the diagram of $W$ by deleting vertices, deleting edges, and/or decreasing edge labels.  A surjective homomorphism $W\to W'$ is determined by its restrictions to rank-two standard parabolic subgroups of $W$.  Despite seeming natural in the setting of Coxeter groups, this determination in rank two is nontrivial.  Indeed, from the combinatorial lattice theory point of view, all of these classification results should appear unlikely a priori.  As an application of the classification of surjective homomorphisms between weak orders, we also obtain a classification of surjective homomorphisms between Cambrian lattices and a general construction of refinement relations between Cambrian fans.
On the Möbius Function and Topology of General Pattern Posets
Authors: Smith Jason P.
Published: January 2020

We introduce a formal definition of a pattern poset which encompasses several previously studied posets in the literature. Using this definition we present some general results on the Möbius function and topology of such pattern posets. We prove our results using a poset fibration based on the embeddings of the poset, where embeddings are representations of occurrences. We show that the Möbius function of these posets is intrinsically linked to the number of embeddings, and in particular to so called normal embeddings. We present results on when topological properties such as Cohen-Macaulayness and shellability are preserved by this fibration. Furthermore, we apply these results to some pattern posets and derive alternative proofs of existing results, such as Björner's results on subword order.
Equidistributed Statistics on Fishburn Matrices and Permutations
Authors: Chen Dandan , Yan Sherry  H.F. , Zhou Robin D.P.
Published: January 2020

Recently, Jelinek conjectured that there exists a bijection between certain restricted permutations and Fishburn matrices such that the bijection verifies the equidistribution of several statistics. The main objective of this paper is to establish such a bijection.
Biased Positional Games and Small Hypergraphs with Large Covers
Authors: Krivelevich Michael , Szabó Tibor
Published: January 2020

We prove that in the biased $(1:b)$ Hamiltonicity and $k$-connectivity Maker-Breaker games ($k>0$ is a constant), played on the edges of the complete graph $K_n$, Maker has a winning strategy for $b\le(\log 2-o(1))n/\log n$. Also, in the biased $(1:b)$ Avoider-Enforcer game played on $E(K_n)$, Enforcer can force Avoider to create a Hamilton cycle when $b\le (1-o(1))n/\log n$. These results are proved using a new approach, relying on the existence of hypergraphs with few edges and large covering number.
A Combinatorial Derivation with Schröder Paths of a Determinant Representation of Laurent Biorthogonal Polynomials
Authors: Kamioka Shuhei
Published: January 2020

A combinatorial proof in terms of Schröder paths and other weighted plane paths is given for a determinant representation of Laurent biorthogonal polynomials (LBPs) and that of coefficients of their three-term recurrence equation. In this process, it is clarified that Toeplitz determinants of the moments of LBPs and their minors can be evaluated by enumerating certain kinds of configurations of Schröder paths in a plane.
The ν-Tamari Lattice via ν-Trees, ν-Bracket Vectors, and Subword Complexes
Authors: Ceballos Cesar , Padrol Arnau , Sarmiento Camilo
Published: January 2020

We give a new interpretation of the $\nu$-Tamari lattice of Préville-Ratelle and Viennot in terms of a rotation lattice of $\nu$-trees. This uncovers the relation with known combinatorial objects such as north-east fillings, \mbox{tree-like} tableaux and subword complexes. We provide a simple description of the lattice property using certain bracket vectors of $\nu$-trees, and show that the Hasse diagram of the $\nu$-Tamari lattice can be obtained as the facet adjacency graph of certain subword complex. Finally, this point of view generalizes to multi $\nu$-Tamari complexes, and gives (conjectural) insight on their geometric realizability via polytopal subdivisions of multiassociahedra.
A Two-Sided Analogue of the Coxeter Complex
Authors: Petersen T. Kyle
Published: January 2020

For any Coxeter system $(W,S)$ of rank $n$, we study an abstract boolean complex (simplicial poset) of dimension $2n-1$ that contains the Coxeter complex as a relative subcomplex. For finite $W$, this complex is first described in work of Hultman. Faces are indexed by triples $(I,w,J)$, where $I$ and $J$ are subsets of the set $S$ of simple generators, and $w$ is a minimal length representative for the parabolic double coset $W_I w W_J$. There is exactly one maximal face for each element of the group $W$. The complex is shellable and thin, which implies the complex is a sphere for the finite Coxeter groups. In this case, a natural refinement of the $h$-polynomial is given by the "two-sided" $W$-Eulerian polynomial, i.e., the generating function for the joint distribution of left and right descents in $W$.
Exact Solution of Some Quarter Plane Walks with Interacting Boundaries
Authors: Beaton N. R. , Owczarek A. L. , Rechnitzer A.
Published: January 2020

The set of random walks with different step sets (of short steps) in the quarter plane has provided a rich set of models that have profoundly different integrability properties. In particular, 23 of the 79 effectively different models can be shown to have generating functions that are algebraic or differentiably finite. Here we investigate how this integrability may change in those 23 models where in addition to length one also counts the number of sites of the walk touching either the horizontal and/or vertical boundaries of the quarter plane. This is equivalent to introducing interactions with those boundaries in a statistical mechanical context. We are able to solve for the generating function in a number of cases. For example, when counting the total number of boundary sites without differentiating whether they are horizontal or vertical, we can solve the generating function of a generalised Kreweras model. However, in many instances we are not able to solve as the kernel methodology seems to break down when including counts with the boundaries.
On the Rank of a Random Binary Matrix
Authors: Cooper Colin , Frieze Alan , Pegden Wesley
Published: January 2020

We study the rank of a random $n \times m$ matrix $\mathbf{A}_{n,m;k}$ with entries from $GF(2)$, and exactly $k$ unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all ${n \choose k}$ such columns.

We obtain an asymptotically correct estimate for the rank as a function of the number of columns $m$ in terms of $c,n,k$, and where $m=cn/k$. The matrix $\mathbf{A}_{n,m;k}$ forms the vertex-edge incidence matrix of a $k$-uniform random hypergraph $H$. The rank of $\mathbf{A}_{n,m;k}$ can be expressed as follows. Let $|C_2|$ be the number of vertices of the 2-core of $H$, and $|E(C_2)|$ the number of edges. Let $m^*$ be the value of $m$ for which $|C_2|= |E(C_2)|$. Then w.h.p. for $m<m^*$ the rank of $\mathbf{A}_{n,m;k}$ is asymptotic to $m$, and for $m \ge m^*$ the rank is asymptotic to $m-|E(C_2)|+|C_2|$.

In addition, assign i.i.d. $U[0,1]$ weights $X_i, i \in {1,2,...m}$ to the columns, and define the weight of a set of columns $S$ as $X(S)=\sum_{j \in S} X_j$. Define a basis as a set of $n-𝟙 (k\text{ even})$ linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for $k=2$,   the expected length of a minimum weight spanning tree tends to $\zeta(3)\sim 1.202$.
Rigid Linkages and Partial Zero Forcing
Authors: Ferrero Daniela , Flagg Mary , Hall H. Tracy , Hogben Leslie , Lin Jephian C.-H. , Meyer Seth A. , Nasserasr Shahla , Shader Bryan
Published: January 2020

Connections between vital linkages and zero forcing are established. Specifically, the notion of a rigid linkage is introduced as a special kind of unique linkage and it is shown that spanning forcing paths of a zero forcing process form a spanning rigid linkage and thus a vital linkage. A related generalization of zero forcing that produces a rigid linkage via a coloring process is developed. One of the motivations for introducing zero forcing is to provide an upper bound on the maximum multiplicity of an eigenvalue among the real symmetric matrices described by a graph. Rigid linkages and a related notion of rigid shortest linkages are utilized to obtain bounds on the multiplicities of eigenvalues of this family of matrices.
Latin Cubes with Forbidden Entries
Authors: Casselgren Carl Johan , Markström Klas , Pham Lan Anh
Published: January 2020

We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant $\gamma > 0$ such that if $n=2^t$ and $A$ is a $3$-dimensional $n\times n\times n$ array where every cell contains at most $\gamma n$ symbols, and every symbol occurs at most $\gamma n$ times in every line of $A$, then $A$ is avoidable; that is, there is a Latin cube $L$ of order $n$ such that for every $1\leq i,j,k\leq n$, the symbol in position $(i,j,k)$ of $L$ does not appear in the corresponding cell of $A$.
Johnson Type Bounds for Mixed Dimension Subspace Codes
Authors: Honold Thomas , Kiermaier Michael , Kurz Sascha
Published: January 2020

Subspace codes, i.e., sets of subspaces of $\mathbb{F}_q^v$, are applied in random linear network coding. Here we give improved upper bounds for their cardinalities based on the Johnson bound for constant dimension codes.
Chromatic Polynomials of Oriented Graphs
Authors: Cox Danielle , Duffy Christopher
Published: January 2020

The oriented chromatic polynomial of a oriented graph outputs the number of oriented $k$-colourings for any input $k$. We fully classify those oriented graphs for which the oriented graph has the same chromatic polynomial as the underlying simple graph, closing an open problem posed by Sopena. We find that such oriented graphs can be both identified and constructed in polynomial time as they are exactly the family of quasi-transitive oriented co-interval graphs. We study the analytic properties of this polynomial and show that there exist oriented graphs which have chromatic polynomials have roots, including negative real roots,  that cannot be realized as the root of any chromatic polynomial of a simple graph.
A Uniform Approach to Complexes arising from Forests
Authors: Marietti Mario , Testa Damiano
Published: January 2020

In this paper we present a unifying approach to study the homotopy type of several complexes arising from forests. We show that this method applies uniformly to many complexes that have been extensively studied in the recent years.
On the Generalized Spectral Characterizations of Eulerian Graphs
Authors: Qiu Lihong , Ji Yizhe , Wang Wei
Published: January 2020

A graph $G$ is said to be determined by its generalized spectra (DGS for short) if, for any graph $H$, graphs $H$ and $G$ are cospectral with cospectral complements imply that $H$ is isomorphic to $G$. In Wang (J. Combin. Theory, Ser. B, 122 (2017) 438-451), the author gave a simple method for a graph to be DGS. However, the method does not apply to Eulerian graphs. In this paper, we gave a simple method for a large family of Eulerian graphs to be DGS. Numerical experiments are also presented to illustrate the effectiveness of the proposed method.
The Biclique Covering Number of Grids
Authors: Guo Krystal , Huynh Tony , Macchia Marco
Published: January 2020

We determine the exact value of the biclique covering number for all grid graphs.
Permutational Powers of a Graph
Authors: Cavaleri Matteo , D'Angeli Daniele , Donno Alfredo
Published: January 2020

This paper introduces a new graph construction, the permutational power of a graph, whose adjacency matrix is obtained by the composition of a permutation matrix with the adjacency matrix of the graph. It is shown that this construction recovers the classical zig-zag product of graphs when the permutation is an involution, and it is in fact more general. We start by discussing necessary and sufficient conditions on the permutation and on the adjacency matrix of a graph to guarantee their composition to represent an adjacency matrix of a graph, then we focus our attention on the cases in which the permutational power does not reduce to a zig-zag product. We show that the cases of interest are those in which the adjacency matrix is singular. This leads us to frame our problem in the context of equitable partitions, obtained by identifying vertices having the same neighborhood. The families of cyclic and complete bipartite graphs are treated in details.
New Probabilistic Upper Bounds on the Domination Number of a Graph
Authors: Jafari Rad Nader
Published: January 2020

A subset $S$ of vertices of a graph $G$ is a dominating set of $G$ if every vertex in $V(G)-S$ has a neighbor in $S$. The domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. In this paper, we obtain new (probabilistic) upper bounds for the domination number of a graph, and improve previous bounds given by Arnautov (1974), Payan (1975), and Caro and Roditty (1985) for any graph, and Harant, Pruchnewski and Voigt (1999) for regular graphs.
Combinatorial Cluster Expansion Formulas from Triangulated Surfaces
Authors: Yurikusa Toshiya
Published: January 2020

We give a cluster expansion formula for cluster algebras with principal coefficients defined from triangulated surfaces in terms of maximal independent sets of angles. Our formula simplifies the cluster expansion formula given by Musiker, Schiffler and Williams in terms of perfect matchings of snake graphs. A key point of our proof is to give a bijection between maximal independent sets of angles in some triangulated polygon and perfect matchings of the corresponding snake graph. Moreover, they also correspond bijectively with perfect matchings of the corresponding bipartite graph and minimal cuts of the corresponding quiver with potential.
Planar Ramsey Graphs
Authors: Axenovich Maria , Schade Ursula , Thomassen Carsten , Ueckerdt Torsten
Published: January 2020

We say that a graph $H$ is planar unavoidable if there is a planar graph $G$ such that any red/blue coloring of the edges of $G$ contains a monochromatic copy of $H$, otherwise we say that $H$ is planar avoidable. That is, $H$ is planar unavoidable if there is a Ramsey graph for $H$ that is planar. It follows from the Four-Color Theorem and a result of Gonçalves that if a graph is planar unavoidable then it is bipartite and outerplanar. We prove that the cycle on $4$ vertices and any path are planar unavoidable. In addition, we prove that all trees of radius at most $2$ are planar unavoidable and there are trees of radius $3$ that are planar avoidable. We also address the planar unavoidable notion in more than two colors.
On Unimodality Problems in Pascal's Triangle
Authors: Su Xun-Tuan , Wang Yi
Published: January 2020

Many sequences of binomial coefficients share various unimodality properties. In this paper we consider the unimodality problem of a sequence of binomial coefficients located in a ray or a transversal of the Pascal triangle. Our results give in particular an affirmative answer to a conjecture of Belbachir et al which asserts that such a sequence of binomial coefficients must be unimodal. We also propose two more general conjectures.
Balanced Triangulations on few Vertices and an Implementation of Cross-Flips
Authors: Venturello Lorenzo
Published: January 2020

A $d$-dimensional simplicial complex is balanced if the underlying graph is $(d+1)$-colorable. We present an implementation of cross-flips, a set of local moves introduced by Izmestiev, Klee and Novik which connect any two PL-homeomorphic balanced combinatorial manifolds. As a result we exhibit a vertex minimal balanced triangulation of the real projective plane, of the dunce hat and of the real projective space, as well as several balanced triangulations of surfaces and 3-manifolds on few vertices. In particular we construct small balanced triangulations of the 3-sphere that are non-shellable and shellable but not vertex decomposable.
Matching Complexes of Small Grids
Authors: Matsushita Takahiro
Published: January 2020

The matching complex $M(G)$ of a simple graph $G$ is the simplicial complex consisting of the matchings on $G$. The matching complex $M(G)$ is isomorphic to the independence complex of the line graph $L(G)$. 

Braun and Hough introduced a family of graphs $\Delta^m_n$, which is a generalization of the line graph of the $(n \times 2)$-grid graph. In this paper, we show that the independence complex of $\Delta^m_n$ is a wedge of spheres. This gives an answer to a problem suggested by Braun and Hough.
Statistical Properties of Lambda Terms
Authors: Bendkowski Maciej , Bodini Olivier , Dovgal Sergey
Published: January 2020

We present a quantitative, statistical analysis of random lambda terms in the De Bruijn notation. Following an analytic approach using multivariate generating functions, we investigate the distribution of various combinatorial parameters of random open and closed lambda terms, including the number of redexes, head abstractions, free variables or the De Bruijn index value profile. Moreover, we conduct an average-case complexity analysis of finding the leftmost-outermost redex in random lambda terms showing that it is on average constant. The main technical ingredient of our analysis is a novel method of dealing with combinatorial parameters inside certain infinite, algebraic systems of multivariate generating functions. Finally, we briefly discuss the random generation of lambda terms following a given skewed parameter distribution and provide empirical results regarding a series of more involved combinatorial parameters such as the number of open subterms and binding abstractions in closed lambda terms.
Uglov Bipartitions and Extended Young Diagrams
Authors: Jacon Nicolas
Published: January 2020

We study the class of Uglov bipartitions and prove a generalization of a conjecture by Dipper, James and Murphy. We give two consequences concerning the computation of canonical bases in affine type $A$ and the description of decomposition matrices for Hecke algebras of type $B_n$ in arbitrary characteristic.
Canonical Forms for Dihedral and Symmetric Groups
Authors: Shwartz Robert
Published: January 2020

In this paper we introduce the elementary factorization of the standard OGS for the symmetric group, and show how it encodes the inversion and descent set statistics. Proofs follow from exchange laws for powers of Coxeter elements in the principal flag.
The New dinv is Not So New
Authors: D'Adderio Michele , Iraci Alessandro
Published: January 2020

In [Duane, Garsia, Zabrocki 2013] the authors introduced a new dinv statistic, denoted ndinv, on the two part case of the shuffle conjecture (Haglund et al. 2005) in order to prove a compositional refinement. Though in [Hicks, Kim 2013] a non-recursive (but algorithmic) definition of ndinv has been given, this statistic still looks a bit unnatural. In this paper we "unveil the mystery" around the ndinv, by showing bijectively that the ndinv actually matches the usual dinv statistic in a special case of the generalized Delta conjecture in [Haglund, Remmel, Wilson 2018]. Moreover, we give also a non-compositional proof of the "ehh" case of the shuffle conjecture (after [Garsia, Xin, Zabrocki 2014]) by bijectively proving a relation with the two part case of the Delta conjecture.
Heterochromatic Matchings in Edge-Colored Graphs
Authors: Wang Guanghui , Li Hao
Published: January 2020

Let $G$ be an (edge-)colored graph. A heterochromatic matching of $G$ is a matching in which no two edges have the same color. For a vertex $v$, let $d^c(v)$ be the color degree of $v$. We show that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$ has a heterochromatic matching of size $\big\lceil{5k-3\over 12}\big\rceil$. For a colored bipartite graph with bipartition $(X,Y)$, we prove that if it satisfies a Hall-like condition, then it has a heterochromatic matching of cardinality $\big\lceil{|X|\over 2}\big\rceil$, and we show that this bound is best possible.
New Graphs of Finite Mutation Type
Authors: Derksen Harm , Owen Theodore
Published: January 2020

To a directed graph without loops or $2$-cycles, we can associate a skew-symmetric matrix with integer entries. Mutations of such skew-symmetric matrices, and more generally skew-symmetrizable matrices, have been defined in the context of cluster algebras by Fomin and Zelevinsky. The mutation class of a graph $\Gamma$ is the set of all isomorphism classes of graphs that can be obtained from $\Gamma$ by a sequence of mutations. A graph is called mutation-finite if its mutation class is finite. Fomin, Shapiro and Thurston constructed mutation-finite graphs from triangulations of oriented bordered surfaces with marked points. We will call such graphs "of geometric type". Besides graphs with $2$ vertices, and graphs of geometric type, there are only 9 other "exceptional" mutation classes that are known to be finite. In this paper we introduce 2 new exceptional finite mutation classes.
The Cyclic Sieving Phenomenon on Circular Dyck Paths
Authors: Alexandersson Per , Linusson Svante , Potka Samu
Published: January 2020

We give a $q$-enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Alexandersson and Panova. Furthermore, we show that this $q$-analogue exhibits the cyclic sieving phenomenon under a natural action of the cyclic group. The enumeration and cyclic sieving is generalized to Möbius paths. We also discuss properties of a generalization of cyclic sieving, which we call subset cyclic sieving, and introduce the notion of Lyndon-like cyclic sieving that concerns special recursive properties of combinatorial objects exhibiting the cyclic sieving phenomenon.
Dependencies Among Dependencies in Matroids
Authors: Oxley James , Wang Suijie
Published: January 2020

In 1971, Rota introduced the concept of derived matroids to investigate "dependencies among dependencies" in matroids. In this paper, we study the derived matroid $\delta M$ of an ${\mathbb F}$-representation of a matroid $M$. The matroid $\delta M$ has a naturally associated ${\mathbb F}$-representation, so we can define a sequence $\delta M$, $\delta^2 M$, \dots . The main result classifies such derived sequences of matroids into three types: finite, cyclic, and divergent. For the first two types, we obtain complete characterizations and thereby resolve some of the questions that Longyear posed in 1980 for binary matroids. For the last type, the divergence is estimated by the coranks of the matroids in the derived sequence.
Difference Families, Skew Hadamard Matrices, and Critical Groups of Doubly Regular Tournaments
Authors: Pantangi Venkata Raghu Tej
Published: January 2020

In this paper we investigate the structure of the critical groups of doubly-regular tournaments (DRTs) associated with skew Hadamard difference families (SDFs) with one, two, or four blocks. Brown and Ried found that the existence of a skew Hadamard matrix of order $n+1$ is equivalent to the existence of a DRT on $n$ vertices. A well known construction of a skew Hadamard matrix order $n$ is by constructing skew Hadamard difference sets in abelian groups of order $n-1$. The Paley skew Hadamard matrix is an example of one such construction. Szekeres and Whiteman constructed skew Hadamard matrices from skew Hadamard difference families with two blocks. Wallis and Whiteman constructed skew Hadamard matrices from skew Hadamard difference families with four blocks. In this paper we consider the critical groups of DRTs associated with skew Hadamard matrices constructed from skew Hadamard difference families with one, two or four blocks. We compute the critical groups of DRTs associated with skew Hadamard difference families with two or four blocks. We also compute the critical group of the Paley tournament and show that this tournament is inequivalent to the other DRTs we considered. Consequently we prove that the associated skew Hadamard matrices are not equivalent.
A Natural Series for the Natural Logarithm
Authors: Dasbach Oliver T.
Published: January 2020

Rodriguez Villegas expressed the Mahler measure of a polynomial in terms of an infinite series. Lück's combinatorial $L^2$-torsion leads to similar series expressions for the Gromov norm of a knot complement. In this note we show that those formulae yield interesting power series expansions for the logarithm function. This generalizes an infinite series of Lehmer for the natural logarithm of $4$.
On a Class of Hyperplanes of the Symplectic and Hermitian Dual Polar Spaces
Authors: De Bruyn Bart
Published: January 2020

Let $\Delta$ be a symplectic dual polar space $DW(2n-1,{\Bbb K})$ or a Hermitian dual polar space $DH(2n-1,{\Bbb K},\theta)$, $n \geq 2$. We define a class of hyperplanes of $\Delta$ arising from its Grassmann-embedding and discuss several properties of these hyperplanes. The construction of these hyperplanes allows us to prove that there exists an ovoid of the Hermitian dual polar space $DH(2n-1,{\Bbb K},\theta)$ arising from its Grassmann-embedding if and only if there exists an empty $\theta$-Hermitian variety in ${\rm PG}(n-1,{\Bbb K})$. Using this result we are able to give the first examples of ovoids in thick dual polar spaces of rank at least 3 which arise from some projective embedding. These are also the first examples of ovoids in thick dual polar spaces of rank at least 3 for which the construction does not make use of transfinite recursion.
The Number of 0-1-2 Increasing Trees as Two Different Evaluations of the Tutte Polynomial of a Complete Graph
Authors: Merino C.
Published: January 2020

If $T_{n}(x,y)$ is the Tutte polynomial of the complete graph $K_n$, we have the equality $T_{n+1}(1,0)=T_{n}(2,0)$. This has an almost trivial proof with the right combinatorial interpretation of $T_{n}(1,0)$ and $T_{n}(2,0)$. We present an algebraic proof of a result with the same flavour as the latter: $T_{n+2}(1,-1)=T_n(2,-1)$, where $T_{n}(1,-1)$ has the combinatorial interpretation of being the number of 0–1–2 increasing trees on $n$ vertices.
On Base Partitions and Cover Partitions of Skew Characters
Authors: Gutschwager Christian
Published: January 2020

In this paper we give an easy combinatorial description for the base partition ${\cal B}$ of a skew character $[{\cal A}]$, which is the intersection of all partitions $\alpha$ whose corresponding character $[\alpha]$ appears in $[{\cal A}]$. This we use to construct the cover partition ${\cal C}$ for the ordinary outer product as well as for the Schubert product of two characters and for some skew characters, here the cover partition is the union of all partitions whose corresponding character appears in the product or in the skew character. This gives us also the Durfee size for arbitrary Schubert products.
A Note on Neighbour-Distinguishing Regular Graphs Total-Weighting
Authors: Przybyło Jakub
Published: January 2020

We investigate the following modification of a problem posed by Karoński, Łuczak and Thomason [J. Combin. Theory, Ser. B 91 (2004) 151–157]. Let us assign positive integers to the edges and vertices of a simple graph $G$. As a result we obtain a vertex-colouring of $G$ by sums of weights assigned to the vertex and its adjacent edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary $G$? We know that the answer is yes if $G$ is a 3-colourable, complete or 4-regular graph. Moreover, it is enough to use weights from $1$ to $11$, as well as from $1$ to $\lfloor{\chi(G)\over2}\rfloor+1$, for an arbitrary graph $G$. Here we show that weights from $1$ to $7$ are enough for all regular graphs.
$k$-Cycle Free One-Factorizations of Complete Graphs
Authors: Meszka Mariusz
Published: January 2020

It is proved that for every $n\geq 3$ and every even $k\geq 4$, where $k\neq 2n$, there exists one-factorization of the complete graph $K_{2n}$ such that any two one-factors do not induce a graph with a cycle of length $k$ as a component. Moreover, some infinite classes of one-factorizations, in which lengths of cycles induced by any two one-factors satisfy a given lower bound, are constructed.
Combinatorial Interpretations for Rank-Two Cluster Algebras of Affine Type
Authors: Musiker Gregg , Propp James
Published: January 2020

Fomin and Zelevinsky show that a certain two-parameter family of rational recurrence relations, here called the $(b,c)$ family, possesses the Laurentness property: for all $b,c$, each term of the $(b,c)$ sequence can be expressed as a Laurent polynomial in the two initial terms. In the case where the positive integers $b,c$ satisfy $bc < 4$, the recurrence is related to the root systems of finite-dimensional rank $2$ Lie algebras; when $bc>4$, the recurrence is related to Kac-Moody rank $2$ Lie algebras of general type. Here we investigate the borderline cases $bc=4$, corresponding to Kac-Moody Lie algebras of affine type. In these cases, we show that the Laurent polynomials arising from the recurence can be viewed as generating functions that enumerate the perfect matchings of certain graphs. By providing combinatorial interpretations of the individual coefficients of these Laurent polynomials, we establish their positivity.
Structural Properties of Twin-Free Graphs
Authors: Charon Irène , Honkala Iiro , Hudry Olivier , Lobstein Antoine
Published: January 2020

Consider a connected undirected graph $G=(V,E)$, a subset of vertices $C \subseteq V$, and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centered at $v$, i.e., the set of all vertices linked to $v$ by a path of at most $r$ edges. If for all vertices $v \in V$, the sets $B_r(v) \cap C$ are all nonempty and different, then we call $C$ an $r$-identifying code. A graph admits at least one $r$-identifying code if and only if it is $r$-twin-free, that is, the sets $B_r(v)$, $v \in V$, are all different. We study some structural problems in $r$-twin-free graphs, such as the existence of the path with $2r+1$ vertices as a subgraph, or the consequences of deleting one vertex.
Constructing Hypohamiltonian Snarks with Cyclic Connectivity $5$ and $6$
Authors: Máčajová Edita , Škoviera Martin
Published: January 2020

A graph is hypohamiltonian if it is not hamiltonian but every vertex-deleted subgraph is. In this paper we study hypohamiltonian snarks – cubic hypohamiltonian graphs with chromatic index 4. We describe a method, based on superposition of snarks, which produces new hypohamiltonian snarks from old ones. By choosing suitable ingredients we can achieve that the resulting graphs are cyclically $5$-connected or $6$-connected. Previously, only three sporadic hypohamiltonian snarks with cyclic connectivity 5 had been found, while the flower snarks of Isaacs were the only known family of cyclically 6-connected hypohamiltonian snarks. Our method produces hypohamiltonian snarks with cyclic connectivity $5$ and $6$ for all but finitely many even orders.
Balancing Cyclic $R$-ary Gray Codes
Authors: Flahive Mary , Bose Bella
Published: January 2020

New cyclic $n$-digit Gray codes are constructed over $\{0, 1, \ldots, R-1 \}$ for all $R \ge 3$, $n \ge 2$. These codes have the property that the distribution of the digit changes (transition counts) is close to uniform: For each $n \ge 2$, every transition count is within $R-1$ of the average $R^n/n$, and for the $2$-digit codes every transition count is either $\lfloor{R^2/2} \rfloor$ or $\lceil{R^2/2} \rceil$.
The Universal Embedding of the Near Polygon ${\Bbb G}_n$
Authors: De Bruyn Bart
Published: January 2020

In an earlier paper, we showed that the dual polar space $DH(2n-1,4)$, $n \geq 2$, has a sub near-$2n$-gon ${\Bbb G}_n$ with a large automorphism group. In this paper, we determine the absolutely universal embedding of this near polygon. We show that the generating and embedding ranks of ${\Bbb G}_n$ are equal to ${2n \choose n}$. We also show that the absolutely universal embedding of ${\Bbb G}_n$ is the unique full polarized embedding of this near polygon.
Edge-Bandwidth of the Triangular Grid
Authors: Akhtar Reza , Jiang Tao , Pritikin Dan
Published: January 2020

In 1995, Hochberg, McDiarmid, and Saks proved that the vertex-bandwidth of the triangular grid $T_n$ is precisely $n+1$; more recently Balogh, Mubayi, and Pluhár posed the problem of determining the edge-bandwidth of $T_n$. We show that the edge-bandwidth of $T_n$ is bounded above by $3n-1$ and below by $3n-o(n)$.
Pengaruh Dana Kampung Terhadap Peningkatan Pembangunan Jalan (Studi Pada Kampung Liman Benawi Kecamatan Trimurjo Kabupaten Lampung Tengah)
Authors: Rohadi Nyono , Mersa Sudarman
Published: January 2020

Artikel ini membahas tentang pengaruh dana kampong terhadap peningkatan pembangunan jalan. Mengambil studi pada Kampung Liman Benawi Kecamatan Trimurjo Kabupaten Lampung Tengah. Pendekatan penelitian adalah kuantitatif. Menggunakan bantuan instrumen kuisioner, total sampel yang terlibat dalam penelitian ini berjumlah 30 orang responden. Hasil analisis korelasi product moment tersebut  di atas didapat nilai X2hitung = 0,547, kemudian dikonsultasikan dengan nilai  X2tabel  pada taraf nyata 5% = 0,312, sehingga X2hitung > X2tabel pada taraf nyata 5%.  Dengan demikian dapat disimpulkan bahwa ada hubungan antara dana Kampung dengan pembangunan jalan lapen di Kampung Liman Benawi Kecamatan Trimurjo Kabupten Lampung Tengah. Sedangkan  besarnya pengaruh  antara  dan Kampung untuk pembangunan jalan lapen sebesar 29,92% (nilai koefisien determinasi).
Perbandingan Kinerja Pegawai Sebelum Dan Sesudah Penerapan E-Government (Studi Pada Badan Pengelolaan Keuangan Dan Aset Daerah Kabupaten Tanggamus)
Authors: Handika Reza , Yulianto Yulianto , Suripto Suripto
Published: January 2020

Kinerja pegawai sektor publik selama ini dianggap masih rendah. Egovernment menjadi salah satu langkah dalam meningkatkan kinerja karyawan. Penelitian ini bertujuan untuk membedakan dan menganalisis kinerja seorang karyawan sebelum dan sesudah implementasi e-government di BPKAD Kabupaten Tanggamus. Penelitian ini bersifat eksplanatori dengan metode pendekatan kuantitatif. Teknik pengumpulan data menggunakan kuesioner, dengan 36 orang sampel diambil dari populasi 57 pegawai BPKAD Kabupaten Tanggamus. Teknik pengambilan sampel menggunakan Incidental dengan rumus Slovin. Data dianalisis dengan menggunakan Metode Analisis diskriminan. Hasil penelitian diuji dengan metode menggunakan variabel kinerja 3 karyawan. Menunjukkan bahwa ada perbedaan yang signifikan dalam jumlah variabel dan ketepatan waktu kerja sebelum dan sesudah implementasi e-gov, sedangkan dalam variabel kualitas pekerjaan tidak menunjukkan adanya perbedaan yang signifikan. Variabel ketiga diperoleh dari kinerja karyawan sebelum dan sesudah implementasi e-gov menggunakan Lambda Wilk dengan nilai signifikansi. Nilai 0,000 α 0,05 <demikian menunjukkan bahwa telah terdapat perbedaan yang nyata (signifikan) antara kinerja karyawan sebelum penerapan kinerja e-government dengan karyawan setelah penerapan e-gov di BPKAD Kabupaten Tanggamus. E-government memiliki pengaruh nyata dalam hal peningkatan kinerja petugas. Penerapan e-gov mampu secara signifikan meningkatkan kuantitas pekerjaan dan ketepatan waktu, meskipun dalam hal kualitas pekerjaan belum tampak perbedaan yang signifikan, dalam penerapan sepenuhnya e-government telah m
DISCLOSURE EKUITAS MEREK DALAM LAPORAN PERUSAHAAN
Authors: Wardianto Kussuyatmono Bagus
Published: January 2020

Makalah ini bertujuan untuk memberikan gambaran terkait disclosure ekuitas merek dalam laporan tahunan dan keuangan perusahaan.Makalah ini juga bertujuan untuk memberikan masukan kepada Otoritas Jasa Keuangan (OJK) dan Dewan Standar Akuntasi Keuangan mengenai disclosure ekuitas merek dalam laporan tahunan dan keuangan perusahaan. Makalah ini ditulis menggunakan kajian pustaka yang mendalam dan diikuti dengan penyajian data deskriptif terkait penghitungan ekuitas merek. Mengingat arti pentingnya ekuitas merek bagi manajemen perusahaan dan investor maka melalui makalah ini dirasa perlu memberi saran kepada OJK, Dewan Standar Akuntansi Keuangan terkait disclosure ekuitas merek dalam laporan tahunan dan keuangan perusahaan.
Implementasi Program Pencegahan Penyakit Tidak Menular Di Puskesmas Cangkringan Kabupaten Sleman
Authors: Mahardika Krisnanda , Utami Sri
Published: January 2020

Peraturan Menteri Kesehatan No. 75 tahun 2014 tentang Pusat Kesehatan Masyarakat menyatakan bahwa Upaya Kesehatan Masyarakat (UKM) adalah setiap kegiatan untuk menjaga dan meningkatkan kesehatan serta mencegah dan mengatasi masalah kesehatan yang menargetkan keluarga, kelompok dan masyarakat. Tujuan dari penelitian ini adalah untuk mengetahui implementasi Program Pencegahan Penyakit Tidak Menular di Puskesmas Cangkringan, Kabupaten Sleman. Penelitian ini menggunakan pendekatan kualitatif deskriptif. Pengumpulan data dilakukan dengan teknik observasi, wawancara, dan dokumentasi. Indikator penelitian berdasarkan Peraturan Sleman No. 49 tahun 2013 tentang Standar Layanan Minimum dan MoU BPJS tentang kerjasama dengan FKTP. Hasil penelitian tentang implementasi program pencegahan untuk penyakit tidak menular belum maksimal. Ini terjadi karena masalah dengan Sumber Daya, Komunikasi, Disposisi, dan Struktur Birokrasi.