bluuebunny/crossref_metadata_2025 huggingface dataset:
Minimum Number of Additive Tuples in Groups of Prime Order
Authors: Chervak Ostap , Pikhurko Oleg , Staden Katherine
Published: January 2020

For a prime number $p$ and a sequence of integers $a_0,\dots,a_k\in \{0,1,\dots,p\}$, let $s(a_0,\dots,a_k)$ be the minimum number of $(k+1)$-tuples $(x_0,\dots,x_k)\in A_0\times\dots\times A_k$ with $x_0=x_1+\dots + x_k$, over subsets $A_0,\dots,A_k\subseteq\mathbb{Z}_p$ of sizes $a_0,\dots,a_k$ respectively. We observe that an elegant argument of Samotij and Sudakov can be extended to show that there exists an extremal configuration with all sets $A_i$ being intervals of appropriate length. The same conclusion also holds for the related problem, posed by Bajnok, when $a_0=\dots=a_k=:a$ and $A_0=\dots=A_k$, provided $k$ is not equal 1 modulo $p$. Finally, by applying basic Fourier analysis, we show for Bajnok's problem that if $p\geqslant 13$ and $a\in\{3,\dots,p-3\}$ are fixed while $k\equiv 1\pmod p$ tends to infinity, then the extremal configuration alternates between at least two affine non-equivalent sets.

 

A corrigendum was added March 12, 2019.
On the Adjacency Spectra of Hypertrees
Authors: Clark Gregory J. , Cooper Joshua N.
Published: January 2020

We show that $\lambda$ is an eigenvalue of a $k$-uniform hypertree $(k \geq 3)$ if and only if it is a root of a particular matching polynomial for a connected induced subtree. We then use this to provide a spectral characterization for power hypertrees. Notably, the situation is quite different from that of ordinary trees, i.e., $2$-uniform trees. We conclude by presenting an example (an $11$ vertex, $3$-uniform non-power hypertree) illustrating these phenomena.
Nonempty Intersection of Longest Paths in $2K_2$-Free Graphs
Authors: Golan Gili , Shan Songling
Published: January 2020

In 1966, Gallai asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallai's question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, and series-parallel graphs. A graph is $2K_2$-free if it does not contain two independent edges as an induced subgraph. In this short note, we show that, in nonempty $2K_2$-free graphs, every vertex of maximum degree is common to all longest paths. Our result implies that all longest paths in a nonempty $2K_2$-free graph have a nonempty intersection. In particular, it strengthens the result on split graphs, as split graphs are $2K_2$-free.
On Certain Edge-Transitive Bicirculants
Authors: Jajcay Robert , Miklavič Štefko , Šparl Primož , Vasiljević Gorazd
Published: January 2020

A graph $\Gamma$ of even order is a bicirculant if it admits an automorphism with two orbits of equal length. Symmetry properties of bicirculants, for which at least one of the induced subgraphs on the two orbits of the corresponding semiregular automorphism is a cycle, have been studied, at least for the few smallest possible valences. For valences $3$, $4$ and $5$, where the corresponding bicirculants are called generalized Petersen graphs, Rose window graphs and Tabač jn graphs, respectively, all edge-transitive members have been classified. While there are only 7 edge-transitive generalized Petersen graphs and only 3 edge-transitive Tabač jn graphs, infinite families of edge-transitive Rose window graphs exist. The main theme of this paper is the question of the existence of such bicirculants for higher valences. It is proved that infinite families of edge-transitive examples of valence $6$ exist and among them infinitely many arc-transitive as well as infinitely many half-arc-transitive members are identified. Moreover, the classification of the ones of valence $6$ and girth $3$ is given. As a corollary, an infinite family of half-arc-transitive graphs of valence $6$ with universal reachability relation, which were thus far not known to exist, is obtained.
Random Planar Maps and Graphs with Minimum Degree Two and Three
Authors: Noy Marc , Ramos Lander
Published: January 2020

We find precise asymptotic estimates for the number of planar maps and graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the core of a random planar graph is of order $c \log(n)$ for an explicit constant $c$. These results provide new information on the structure of random planar graphs.
Hamilton $\ell$-Cycles in Randomly Perturbed Hypergraphs
Authors: McDowell Andrew , Mycroft Richard
Published: January 2020

We prove that for integers $2 \leqslant \ell < k$ and a small constant $c$, if a $k$-uniform hypergraph with linear minimum codegree is randomly 'perturbed' by changing non-edges to edges independently at random with probability $p \geqslant O(n^{-(k-\ell)-c})$, then with high probability the resulting $k$-uniform hypergraph contains a Hamilton $\ell$-cycle. This complements a recent analogous result for Hamilton $1$-cycles due to Krivelevich, Kwan and Sudakov, and a comparable theorem in the graph case due to Bohman, Frieze and Martin.
Hypergraph Coverings and their Zeta Functions
Authors: Li Deqiong , Hou Yaoping
Published: January 2020

Let $H$ be a finite hypergraph. The concept of hypergraph coverings over $H$ is introduced, and we can generate all hypergraph coverings by permutation voltage assignments of the edge-colored graph or the incidence graph of $H$. Consequently, we show two explicit decomposition formulae for the zeta function of any hypergraph covering $\overline{H}$ over $H$ which indicates that the zeta function of $H$ divides the zeta function of $\overline{H}$.
A Notion of Inversion Number Associated to Certain Quiver Flag Varieties
Authors: Fresse Lucas
Published: January 2020

We define an algebraic variety $X(d,A)$ consisting of matrices whose rows and columns are partial flags. This is a smooth, projective variety, and we describe it as an iterated bundle of Grassmannian varieties. Moreover, we show that $X(d,A)$ has a cell decomposition, in which the cells are parametrized by certain matrices of sets and their dimensions are given by a notion of inversion number. On the other hand, we consider the Spaltenstein variety of partial flags which are stabilized by a given nilpotent endomorphism. We partition this variety into locally closed subvarieties which are affine bundles over certain varieties called $Y_T$, parametrized by semistandard tableaux $T$. We show that the varieties $Y_T$ are in fact isomorphic to varieties of the form $X(d,A)$. We deduce that each variety $Y_T$ has a cell decomposition, in which the cells are parametrized by certain row-increasing tableaux obtained by permuting the entries in the columns of $T$ and their dimensions are given by the inversion number recently defined by P. Drube for such row-increasing tableaux.
Fractional L-intersecting Families
Authors: Balachandran Niranjan , Mathew Rogers , Mishra Tapas Kumar
Published: January 2020

Let $L = \{\frac{a_1}{b_1}, \ldots , \frac{a_s}{b_s}\}$, where for every $i \in [s]$, $\frac{a_i}{b_i} \in [0,1)$ is an irreducible fraction. Let $\mathcal{F} = \{A_1, \ldots , A_m\}$ be a family of subsets of $[n]$. We say $\mathcal{F}$ is a fractional $L$-intersecting family if for every distinct $i,j \in [m]$, there exists an $\frac{a}{b} \in L$ such that $|A_i \cap A_j| \in \{ \frac{a}{b}|A_i|, \frac{a}{b} |A_j|\}$. In this paper, we introduce and study the notion of fractional $L$-intersecting families.
A New Perspective on the Average Mixing Matrix
Authors: Coutinho Gabriel , Godsil Chris , Guo Krystal , Zhan Hanmeng
Published: January 2020

We consider the continuous-time quantum walk defined on the adjacency matrix of a graph. At each instant, the walk defines a mixing matrix which is doubly-stochastic. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. We show that it is the matrix of transformation of the orthogonal projection onto the commutant algebra of the adjacency matrix, restricted to diagonal matrices. Using this formulation of the average mixing matrix, we find connections between its rank and automorphisms of the graph.
Determinant Expressions for $q$-Harmonic Congruences and Degenerate Bernoulli Numbers
Authors: Dilcher Karl
Published: January 2020

The generalized harmonic numbers $H_n^{(k)}=\sum_{j=1}^n j^{-k}$ satisfy the well-known congruence $H_{p-1}^{(k)}\equiv 0\pmod{p}$ for all primes $p\geq 3$ and integers $k\geq 1$. We derive $q$-analogs of this congruence for two different $q$-analogs of the sum $H_n^{(k)}$. The results can be written in terms of certain determinants of binomial coefficients which have interesting properties in their own right. Furthermore, it is shown that one of the classes of determinants is closely related to degenerate Bernoulli numbers, and new properties of these numbers are obtained as a consequence.
The Chromatic Number of the $q$-Kneser Graph for Large $q$
Authors: Ihringer Ferdinand
Published: January 2020

We obtain a new weak Hilton-Milner type result for intersecting families of $k$-spaces in $\mathbb{F}_q^{2k}$, which improves several known results. In particular the chromatic number of the $q$-Kneser graph $qK_{n:k}$ was previously known for $n > 2k$ (except for $n=2k+1$ and $q=2$) or $k < q \log q - q$. Our result determines the chromatic number of $qK_{2k:k}$ for $q \geqslant 5$, so that the only remaining open cases are $(n, k) = (2k, k)$ with $q \in \{ 2, 3, 4 \}$ and $(n, k) = (2k+1, k)$ with $q = 2$.
Graphs Associated with Codes of Covering Radius 1 and Minimum Distance 2
Authors: Hall Joanne L.
Published: January 2020

The search for codes of covering radius $1$ led Östergård, Quistorff and Wassermann to the OQW method of associating a unique graph to each code. We present results on the structure and existence of OQW-associated graphs. These are used to find an upper bound on the size of a ball of radius $1$ around a code of length $3$ and minimum distance $2$. OQW-associated graphs and non-extendable partial Latin squares are used to catalogue codes of length $3$ over $4$ symbols with covering radius $1$ and minimum distance $2$.
The Weighted Davenport Constant of a Group and a Related Extremal Problem
Authors: Balachandran Niranjan , Mazumdar Eshita
Published: January 2020

For a finite abelian group $G$ written additively, and a non-empty subset $A\subset [1,\exp(G)-1]$ the weighted Davenport Constant of $G$  with respect to the set $A$, denoted $D_A(G)$, is the least positive integer $k$ for which the following holds: Given an arbitrary sequence $(x_1,\ldots,x_k)$ with $x_i\in G$, there exists a non-empty subsequence  $(x_{i_1},\ldots,x_{i_t})$ along with $a_{j}\in A$ such that $\sum_{j=1}^t a_jx_{i_j}=0$. In this paper, we pose and study a natural new extremal problem that arises from the study of $D_A(G)$:  For an integer $k\ge 2$, determine $f^{(D)}_G(k):=\min\{|A|: D_A(G)\le k\}$ (if the problem posed makes sense). It turns out that for $k$ 'not-too-small', this is a well-posed problem and one of the most interesting cases occurs for $G=\mathbb{Z}_p$, the cyclic group of prime order, for which we obtain near optimal bounds for all $k$ (for sufficiently large primes $p$), and asymptotically tight (up to constants) bounds for $k=2,4$.
On the Doubly Refined Enumeration of Alternating Sign Matrices and Totally Symmetric Self - Complementary Plane Partitions
Authors: Fonseca Tiago , Zinn-Justin Paul
Published: January 2020

We prove the equality of doubly refined enumerations of Alternating Sign Matrices and of Totally Symmetric Self-Complementary Plane Partitions using integral formulae originating from certain solutions of the quantum Knizhnik–Zamolodchikov equation.
The Second Eigenvalue of some Normal Cayley Graphs of Highly Transitive Groups
Authors: Huang Xueyi , Huang Qiongxiang , Cioabă Sebastian M.
Published: January 2020

Let $G$ be a finite group acting transitively on $[n]=\{1,2,\ldots,n\}$, and  let $\Gamma=\mathrm{Cay}(G,T)$ be a Cayley graph of $G$. The graph $\Gamma$ is called  normal if $T$ is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph $\Gamma$ in terms of the second eigenvalues of certain subgraphs of $\Gamma$. Using this result, we develop a recursive method to  determine the second eigenvalues of certain  Cayley graphs of $S_n$, and we determine the second eigenvalues  of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $S_n$  with  $\max_{\tau\in T}|\mathrm{supp}(\tau)|\leqslant 5$, where $\mathrm{supp}(\tau)$ is the set of points in $[n]$ non-fixed by $\tau$.
On the Turán Density of $\{1, 3\}$-Hypergraphs
Authors: Bai Shuliang , Lu Linyuan
Published: January 2020

In this paper, we consider the Turán problems on $\{1,3\}$-hypergraphs.  We prove that a $\{1, 3\}$-hypergraph is degenerate if and only if it's $H^{\{1, 3\}}_5$-colorable, where  $H^{\{1, 3\}}_5$ is a hypergraph with vertex set  $V=[5]$ and edge set $E=\{\{2\}, \{3\}, \{1, 2, 4\},\{1, 3, 5\}, \{1, 4, 5\}\}.$ Using this result, we further prove that for any finite set $R$ of distinct positive integers, except the case $R=\{1, 2\}$,  there always exist non-trivial degenerate $R$-graphs. We also compute the Turán densities of some small $\{1,3\}$-hypergraphs.
A Cornucopia of Quasi-Yamanouchi Tableaux
Authors: Wang George
Published: January 2020

Quasi-Yamanouchi tableaux are a subset of semistandard Young tableaux and refine standard Young tableaux. They are closely tied to the descent set of standard Young tableaux and were introduced by Assaf and Searles to tighten Gessel's fundamental quasisymmetric expansion of Schur functions. The descent set and descent statistic of standard Young tableaux repeatedly prove themselves useful to consider, and as a result, quasi-Yamanouchi tableaux make appearances in many ways outside of their original purpose. Some examples, which we present in this paper, include the Schur expansion of Jack polynomials, the decomposition of Foulkes characters, and the bigraded Frobenius image of the coinvariant algebra. While it would be nice to have a product formula enumeration of quasi-Yamanouchi tableaux in the way that semistandard and standard Young tableaux do, it has previously been shown by the author that there is little hope on that front. The goal of this paper is to address a handful of the numerous alternative enumerative approaches. In particular, we present enumerations of quasi-Yamanouchi tableaux using $q$-hit numbers, semistandard Young tableaux, weighted lattice paths, and symmetric polynomials, as well as the fundamental quasisymmetric and monomial quasisymmetric expansions of their Schur generating function.
Enumeration on Row-Increasing Tableaux of Shape $2 \times n$
Authors: Du Rosena R.X. , Fan Xiaojie , Zhao Yue
Published: January 2020

Recently O. Pechenik studied the cyclic sieving of increasing tableaux of shape $2\times n$, and obtained a polynomial on the major index of these tableaux, which is a $q$-analogue of refined small Schröder numbers. We define row-increasing tableaux and study the major index and amajor index of row-increasing tableaux of shape $2 \times n$. The resulting polynomials are both $q$-analogues of refined large Schröder numbers. For both results we give bijective proofs.
Crossings and Nestings in Tangled Diagrams
Authors: Chen William Y. C. , Qin Jing , Reidys Christian M.
Published: January 2020

A tangled diagram on $[n]=\{1,\dots,n\}$ is a labeled graph for which each vertex has degree at most two. The vertices are arranged in increasing order on a horizontal line and the arcs are drawn in the upper halfplane with a particular notion of crossings and nestings. Generalizing the construction of Chen et al., we give a bijection between generalized vacillating tableaux with less than $k$ rows and $k$-noncrossing tangled diagrams. We show that the numbers of $k$-noncrossing and $k$-nonnesting tangled diagrams are equal and we enumerate $k$-noncrossing tangled diagrams. Finally, we show that braids, a special class of tangled diagrams, facilitate a bijection between $2$-regular $k$-noncrossing partitions and $k$-noncrossing enhanced partitions.
Diagrams and Essential Sets for Signed Permutations
Authors: Anderson David
Published: January 2020

We introduce diagrams and essential sets for signed permutations, extending the analogous notions for ordinary permutations.  In particular, we show that the essential set provides a minimal list of rank conditions defining the Schubert variety or degeneracy locus corresponding to a signed permutation.  Our essential set is in bijection with the poset-theoretic version defined by Reiner, Woo, and Yong, and thus gives an explicit, diagrammatic method for computing the latter.
Resolving Two Conjectures on Staircase Encodings and Boundary Grids of $132$ and $123$-avoiding permutations
Authors: Narayanan Shyam Sivasathya
Published: January 2020

This paper analyzes relations between pattern avoidance of certain permutations and graphs on staircase grids and boundary grids, and proves two conjectures posed by Bean, Tannock, and Ulfarsson (2015). More specifically, this paper enumerates a certain family of staircase encodings and proves that the downcore graph, a certain graph established on the boundary grid, is pure if and only if the permutation corresponding to the boundary grid avoids the classical patterns 123 and 2143.
Rigidity for the Hopf Algebra of Quasisymmetric Functions
Authors: Jia Wanwan , Wang Zhengpan , Yu Houyi
Published: January 2020

We investigate the rigidity for the Hopf algebra QSym of quasisymmetric functions with respect to the monomial, the fundamental and the quasisymmetric Schur basis, respectively. By establishing some combinatorial properties of the posets of compositions arising from the analogous Pieri rules for quasisymmetric functions, we show that QSym is rigid as an algebra with respect to the quasisymmetric Schur basis, and rigid as a coalgebra with respect to the monomial and the quasisymmetric Schur basis, respectively. The natural actions of reversal, complement and transpose of the labelling compositions lead to some nontrivial graded (co)algebra automorphisms of QSym. We prove that the linear maps induced by the three actions are precisely the only nontrivial graded algebra automorphisms that take the fundamental basis into itself. Furthermore, the complement map on the labels gives the unique nontrivial graded coalgebra automorphism preserving the fundamental basis, while the reversal map on the labels gives the unique nontrivial graded algebra automorphism preserving the monomial basis. Therefore, QSym is rigid as a Hopf algebra with respect to the monomial and the quasisymmetric Schur basis.
Shell Tableaux: A Set Partition Analog of Vacillating Tableaux
Authors: Ly Megan
Published: January 2020

Schur–Weyl duality is a fundamental framework in combinatorial representation theory. It intimately relates the irreducible representations of a group to the irreducible representations of its centralizer algebra. We investigate the analog of Schur–Weyl duality for the group of unipotent upper triangular matrices over a finite field.  In this case, the character theory of these upper triangular matrices is "wild" or unattainable. Thus we employ a generalization, known as supercharacter theory, that creates a striking variation on the character theory of the symmetric group with combinatorics built from set partitions. In this paper, we present a combinatorial formula for calculating a restriction and induction of supercharacters based on statistics of set partitions and seashell inspired diagrams. We use these formulas to create a graph that encodes the decomposition of a tensor space, and develop an analog of Young tableaux, known as shell tableaux, to index paths in this graph.
The Perimeter and Site-Perimeter of Set Partitions
Authors: Mansour Toufik
Published: January 2020

In this paper, we study the generating function for the number of set partitions of $[n]$ represented as bargraphs according to the perimeter/site-perimeter. In particular, we find explicit formulas  for the total perimeter and the total site-perimeter over all set partitions of $[n]$.
The Largest Complete Bipartite Subgraph in Point-Hyperplane Incidence Graphs
Authors: Do Thao
Published: January 2020

Given $m$ points and $n$ hyperplanes in $\mathbb{R}^d$ ($d\geqslant 3)$, if there are many incidences, we expect to find a big cluster $K_{r,s}$ in their incidence graph. Apfelbaum and Sharir found lower and upper bounds for the largest size of $rs$, which match (up to a constant) only in three dimensions. In this paper we close the gap in four and five dimensions, up to some polylogarithmic factors.
Quartet Compatibility and the Quartet Graph
Authors: Grünewald Stefan , Humphries Peter J. , Semple Charles
Published: January 2020

A collection ${\cal P}$ of phylogenetic trees is compatible if there exists a single phylogenetic tree that displays each of the trees in ${\cal P}$. Despite its computational difficulty, determining the compatibility of ${\cal P}$ is a fundamental task in evolutionary biology. Characterizations in terms of chordal graphs have been previously given for this problem as well as for the closely-related problems of (i) determining if ${\cal P}$ is definitive and (ii) determining if ${\cal P}$ identifies a phylogenetic tree. In this paper, we describe new characterizations of each of these problems in terms of edge colourings. Furthermore, making use of the tools that underlie these new characterizations, we also determine the minimum number of quartets required to identify an arbitrary phylogenetic tree, thus correcting a previously published result.
Ear Decomposition and Balanced Neighborly Simplicial Manifolds
Authors: Zheng Hailun
Published: January 2020

We find the first non-octahedral balanced 2-neighborly 3-sphere and the balanced 2-neighborly triangulation of the lens space $L(3,1)$. Each construction has 16 vertices. We show that there exists a balanced 3-neighborly non-spherical 5-manifold with 18 vertices. We also show that the rank-selected subcomplexes of a balanced simplicial sphere do not necessarily have an ear decomposition.
Domino Tilings for Augmented Aztec Rectangles and Their Chains
Authors: Kim Hyunggi , Lee Sangyop , Oh Seungsang
Published: January 2020

Much work has been done to count the number of domino tilings for Aztec diamonds and augmented Aztec diamonds. Augmented Aztec rectangles and their chains are generalizations of these shapes. In this paper, we use Delannoy paths to count the number of domino tilings for these rectangles and their chains.
Non-Bipartite Distance-Regular Graphs with a Small Smallest Eigenvalue
Authors: Qiao Zhi , Jing Yifan , Koolen Jack
Published: January 2020

In 2017, Qiao and Koolen showed that for any fixed integer $D\geqslant 3$, there are only finitely many such graphs with $\theta_{\min}\leqslant -\alpha k$, where $0<\alpha<1$ is any fixed number. In this paper, we will study non-bipartite distance-regular graphs with relatively small $\theta_{\min}$ compared with $k$. In particular, we will show that if $\theta_{\min}$ is relatively close to $-k$, then the odd girth $g$ must be large. Also we will classify the non-bipartite distance-regular graphs with $\theta_{\min} \leqslant -\frac{D-1}{D}k$ for $D =4,5$.
Multicolour Bipartite Ramsey Number of Paths
Authors: Bucic Matija , Letzter Shoham , Sudakov Benny
Published: January 2020

The k$-colour bipartite Ramsey number of a bipartite graph $H$ is the least integer $N$ for which every $k$-edge-coloured complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. The study of bipartite Ramsey numbers was initiated over 40 years ago by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the $2$-colour bipartite Ramsey number of paths. Recently the $3$-colour Ramsey number of paths and (even) cycles, was essentially determined as well. Improving the results of DeBiasio, Gyárfás, Krueger, Ruszinkó, and Sárközy, in this paper we determine asymptotically the $4$-colour bipartite Ramsey number of paths and cycles. We also provide new upper bounds on the $k$-colour bipartite Ramsey numbers of paths and cycles which are close to being tight.
Variations on the Petersen Colouring Conjecture
Authors: Pirot François , Sereni Jean-Sébastien , Škrekovski Riste
Published: January 2020

The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge e, the set of colours assigned to the edges adjacent to e has cardinality either 2 or 4, but not 3. We prove that every bridgeless cubic graph $G$ admits an edge-colouring with 4 colours such that at most $8/15\cdot|E(G)|$ edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a 4-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.
On Orthogonal Symmetric Chain Decompositions
Authors: Däubel Karl , Jäger Sven , Mütze Torsten , Scheucher Manfred
Published: January 2020

The $n$-cube is the poset obtained by ordering all subsets of $\{1,\ldots,n\}$ by inclusion, and it can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ chains, which is the minimum possible number. Two such decompositions of the $n$-cube are called orthogonal if any two chains of the decompositions share at most a single element. Shearer and Kleitman conjectured in 1979 that the $n$-cube has $\lfloor n/2\rfloor+1$ pairwise orthogonal decompositions into the minimum number of chains, and they constructed two such decompositions. Spink recently improved this by showing that the $n$-cube has three pairwise orthogonal chain decompositions for $n\geq 24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $n$-cube for $n\geq 60$. We also construct five pairwise edge-disjoint symmetric chain decompositions of the $n$-cube for $n\geq 90$, where edge-disjointness is a slightly weaker notion than orthogonality, improving on a recent result by Gregor, Jäger, Mütze, Sawada, and Wille.
2413-Balloon Permutations and the Growth of the Möbius Function
Authors: Marchant David
Published: January 2020

We show that the growth of the principal Möbius function on the permutation poset is at least exponential. This improves on previous work, which has shown that the growth is at least polynomial. We define a method of constructing a permutation from a smaller permutation which we call ``"ballooning". We show that if $\beta$ is a 2413-balloon, and $\pi$ is the 2413-balloon of $\beta$, then $\mu[1,\pi] = 2 \mu[1,\beta]$. This allows us to construct a sequence of permutations $\pi_1, \pi_2, \pi_3\ldots$ with lengths $n, n+4, n+8, \ldots$ such that $\mu[1,\pi_{i+1}] = 2 \mu[1,\pi_{i}]$, and this gives us exponential growth. Further, our construction method gives permutations that lie within a hereditary class with finitely many simple permutations. We also find an expression for the value of $\mu[1,\pi]$, where $\pi$ is a 2413-balloon, with no restriction on the permutation being ballooned.
Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes
Authors: Drmota Michael , Ramos Lander , Requilé Clément , Rué Juanjo
Published: January 2020

The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and series-parallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988].
Superization and $(q,t)$-Specialization in Combinatorial Hopf Algebras
Authors: Novelli Jean-Christophe , Thibon Jean-Yves
Published: January 2020

We extend a classical construction on symmetric functions, the superization process, to several combinatorial Hopf algebras, and obtain analogs of the hook-content formula for the $(q,t)$-specializations of various bases. Exploiting the dendriform structures yields in particular $(q,t)$-analogs of the Björner-Wachs $q$-hook-length formulas for binary trees, and similar formulas for plane trees.
Nonhomogeneous Parking Functions and Noncrossing Partitions
Authors: Armstrong Drew , Eu Sen-Peng
Published: January 2020

For each skew shape we define a nonhomogeneous symmetric function, generalizing a construction of Pak and Postnikov. In two special cases, we show that the coefficients of this function when expanded in the complete homogeneous basis are given in terms of the (reduced) type of $k$-divisible noncrossing partitions. Our work extends Haiman's notion of a parking function symmetric function.
Some Identities Involving Second Kind Stirling Numbers of Types $B$ and $D$
Authors: Bagno Eli , Biagioli Riccardo , Garber David
Published: January 2020

Using Reiner's definition of Stirling numbers of the second kind in types $B$ and $D$, we generalize two well-known identities concerning the classical Stirling numbers of the second kind. The first identity relates them with Eulerian numbers and the second identity interprets them as entries in a transition matrix between the elements of two standard bases of the polynomial ring $\mathbb{R}[x]$. Finally, we generalize these identities to the group of colored permutations $G_{m,n}$.
Jack Deformations of Plancherel Measures and Traceless Gaussian Random Matrices
Authors: Matsumoto Sho
Published: January 2020

We study random partitions $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_d)$ of $n$ whose length is not bigger than a fixed number $d$. Suppose a random partition $\lambda$ is distributed according to the Jack measure, which is a deformation of the Plancherel measure with a positive parameter $\alpha>0$. We prove that for all $\alpha>0$, in the limit as $n \to \infty$, the joint distribution of scaled $\lambda_1,\dots, \lambda_d$ converges to the joint distribution of some random variables from a traceless Gaussian $\beta$-ensemble with $\beta=2/\alpha$. We also give a short proof of Regev's asymptotic theorem for the sum of $\beta$-powers of $f^\lambda$, the number of standard tableaux of shape $\lambda$.
The Maximum Number of Cycles in a Graph with Fixed Number of Edges
Authors: Arman Andrii , Tsaturian Sergei
Published: January 2020

The main problem considered in this paper is maximizing the number of cycles in a graph with given number of edges. In 2009, Király conjectured that there is constant $c$ such that any graph with $m$ edges has at most $c(1.4)^m$ cycles. In this paper, it is shown that for sufficiently large $m$, a graph with $m$ edges has at most $(1.443)^m$ cycles. For sufficiently large $m$, examples of a graph with $m$ edges and $(1.37)^m$ cycles are presented. For a graph with given number of vertices and edges an upper bound on the maximal number of cycles is given. Also, bounds tight up to a constant are presented for the maximum number of cycles in a multigraph with given number of edges, as well as in a multigraph with given number of vertices and edges.
A Continuous Analogue of Lattice Path Enumeration
Authors: Le Quang-Nhat , Robins Sinai , Vignat Christophe , Wakhare Tanay
Published: January 2020

Following the work of Cano and Díaz, we consider a continuous analog of lattice path enumeration. This process allows us to define a continuous version of many discrete objects that count certain types of lattice paths. As an example of this process, we define continuous versions of binomial and multinomial coefficients, and describe some identities and partial differential equations that they satisfy. Finally, as an important byproduct of these continuous analogs, we illustrate a general method to recover discrete combinatorial quantities from their continuous analogs, via an application of the Khovanski-Puklikov discretizing Todd operators.
Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets
Authors: Eisenbrand Friedrich , Pach János , Rothvoß Thomas , Sopher Nir B.
Published: January 2020

Let $P$ and $Q$ be finite sets of points in the plane. In this note we consider the largest cardinality of a subset of the Minkowski sum $S\subseteq P \oplus Q$ which consist of convexly independent points. We show that, if $|P| = m$ and $|Q| = n$ then $|S| = O(m^{2/3} n^{2/3} + m + n)$.
Fractional Decompositions and the Smallest-eigenvalue Separation
Authors: Knox Fiachra , Mohar Bojan
Published: January 2020

A new method is introduced for bounding the separation between the value of $-k$ and the smallest eigenvalue of a non-bipartite $k$-regular graph. The method is based on fractional decompositions of graphs. As a consequence we obtain a very short proof of a generalization and strengthening of a recent result of Qiao, Jing, and Koolen [Electronic J. Combin. 26(2) (2019), #P2.41] about the smallest eigenvalue of non-bipartite distance-regular graphs.
A Combinatorial Proof of Andrews' Smallest Parts Partition Function
Authors: Ji Kathy Qing
Published: January 2020

We give a combinatorial proof of Andrews' smallest parts partition function with the aid of rooted partitions introduced by Chen and the author.
Ramsey Numbers of Berge-Hypergraphs and Related Structures
Authors: Salia Nika , Tompkins Casey , Wang Zhiyu , Zamora Oscar
Published: January 2020

For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists an injection $f: E(G) \to E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. Let the Ramsey number $R^r(BG,BG)$ be the smallest integer $n$ such that for any $2$-edge-coloring of a complete $r$-uniform hypergraph on $n$ vertices, there is a monochromatic Berge-$G$ subhypergraph. In this paper, we show that the 2-color Ramsey number of Berge cliques is linear. In particular, we show that $R^3(BK_s, BK_t) = s+t-3$ for $s,t \geq 4$ and $\max(s,t) \geq 5$ where $BK_n$ is a Berge-$K_n$ hypergraph. For higher uniformity, we show that $R^4(BK_t, BK_t) = t+1$ for $t\geq 6$ and $R^k(BK_t, BK_t)=t$ for $k \geq 5$ and $t$ sufficiently large. We also investigate the Ramsey number of trace hypergraphs, suspension hypergraphs and expansion hypergraphs.
Schur and $e$-Positivity of Trees and Cut Vertices
Authors: Dahlberg Samantha , She Adrian , Van Willigenburg Stephanie
Published: January 2020

We prove that the chromatic symmetric function of any $n$-vertex tree containing a vertex of degree $d\geqslant \log _2n +1$ is not $e$-positive, that is, not a positive linear combination of elementary symmetric functions. Generalizing this, we also prove that the chromatic symmetric function of any $n$-vertex connected graph containing a cut vertex whose deletion disconnects the graph into $d\geqslant\log _2n +1$ connected components is not $e$-positive. Furthermore we prove that any $n$-vertex bipartite graph, including all trees, containing a vertex of degree greater than $\lceil \frac{n}{2}\rceil$ is not Schur-positive, namely not a positive linear combination of Schur functions. In complete generality, we prove that if an $n$-vertex connected graph has no perfect matching (if $n$ is even) or no almost perfect matching (if $n$ is odd), then it is not $e$-positive. We hence deduce that many graphs containing the claw are not $e$-positive.
A Sharp Bound for the Reconstruction of Partitions
Authors: Vatter Vincent
Published: January 2020

Answering a question of Cameron, Pretzel and Siemons proved that every integer partition of $n\ge 2(k+3)(k+1)$ can be reconstructed from its set of $k$-deletions. We describe a new reconstruction algorithm that lowers this bound to $n\ge k^2+2k$ and present examples showing that this bound is best possible.
On the Genus Distribution of $(p,q,n)$-Dipoles
Authors: Visentin Terry I. , Wieler Susana W.
Published: January 2020

There are many applications of the enumeration of maps in surfaces to other areas of mathematics and the physical sciences. In particular, in quantum field theory and string theory, there are many examples of occasions where it is necessary to sum over all the Feynman graphs of a certain type. In a recent paper of Constable et al. on pp-wave string interactions, they must sum over a class of Feynman graphs which are equivalent to what we call $(p,q,n)$-dipoles. In this paper we perform a combinatorial analysis that gives an exact formula for the number of $(p,q,n)$-dipoles in the torus (genus 1) and double torus (genus 2).
Some Properties of Unitary Cayley Graphs
Authors: Klotz Walter , Sander Torsten
Published: January 2020

The unitary Cayley graph $X_n$ has vertex set $Z_n=\{0,1, \ldots ,n-1\}$. Vertices $a, b$ are adjacent, if gcd$(a-b,n)=1$. For $X_n$ the chromatic number, the clique number, the independence number, the diameter and the vertex connectivity are determined. We decide on the perfectness of $X_n$ and show that all nonzero eigenvalues of $X_n$ are integers dividing the value $\varphi(n)$ of the Euler function.
Generating Symplectic and Hermitian Dual Polar Spaces over Arbitrary Fields Nonisomorphic to ${\Bbb F}_2$
Authors: De Bruyn Bart , Pasini Antonio
Published: January 2020

Cooperstein proved that every finite symplectic dual polar space $DW(2n-1,q)$, $q \neq 2$, can be generated by ${2n \choose n} - {2n \choose n-2}$ points and that every finite Hermitian dual polar space $DH(2n-1,q^2)$, $q \neq 2$, can be generated by ${2n \choose n}$ points. In the present paper, we show that these conclusions remain valid for symplectic and Hermitian dual polar spaces over infinite fields. A consequence of this is that every Grassmann-embedding of a symplectic or Hermitian dual polar space is absolutely universal if the (possibly infinite) underlying field has size at least 3.
On Self-Complementary Cyclic Packing of Forests
Authors: Wojda A.Paweł , Woźniak Mariusz , Zioło Irmina A.
Published: January 2020

A graph is self-complementary if it is isomorphic to its complement. In this paper we prove that every forest of order $4p$ and size less than $3p$ is a subgraph of a self-complementary graph of order $4p$ with a cyclic self-complementary permutation. We also discuss some generalization of the main result.
Directed Animals and Gas Models Revisited
Authors: Borgne Yvan Le , Marckert Jean-François
Published: January 2020

In this paper, we revisit the enumeration of directed animals using gas models. We show that there exists a natural construction of random directed animals on any directed graph together with a particles system – a gas model with nearest exclusion – that explains combinatorialy the formal link known between the density of the gas model and the generating function of directed animals counted according to the area. This provides some new methods to compute the generating function of directed animals counted according to area, and leads in the particular case of the square lattice to new combinatorial results and questions. A model of gas related to directed animals counted according to area and perimeter on any directed graph is also exhibited.
TIPOLOGI KLASTER HILIRISASI KARET DI PROVINSI JAMBI
Authors: Erlinda Novita
Published: January 2020

Karet telah menjadi komoditas utama bagi petani pedesaan di Jambi. Ini telah menjadi pondasi utama penghidupan pedesaan bagi masyarakat pedesaan karena menciptakan efek berganda terhadap ekonomi pedesaan. Namun demikian, pendapatan petani karet secara umum masih lebih rendah dibandingkan dengan pekerjaan lain atau bahkan kegiatan pertanian lainnya. Fluktuasi harga karet serta rendahnya kapasitas posisi tawar petani di pasar telah menciptakan lingkaran setan berpenghasilan rendah di petani karet. Situasi ini telah mendorong pemerintah untuk menerapkan hilirisasi produk karet olahan. Hilirisasi adalah salah satu solusi kebijakan yang diharapkan dapat meningkatkan kesejahteraan petani karet. Tulisan ini bertujuan untuk mengidentifikasi tipologi klaster hilir karet di Provinsi Jambi, dan untuk memetakan hubungan antar aktor dalam implementasi kebijakan hilir karet. Penelitian ini fokus pada enam kabupaten yang memiliki perkebunan karet rakyat di Provinsi Jambi, yaitu Merangin, Sarolangun, Bungo, Tebo, Batanghari dan Muaro Jambi. Data yang digunakan berupa data primer dan sekunder. Analisis dilakukan dengan cara analisis prospektif menggunakan alat MACTOR. Hasil analisis menghasilkan tiga tipologi cluster downstreaming, yaitu: 1. HVLV cluster berdasarkan volume tinggi dan volume rendah; 2. Kelompok EMLM berdasarkan pasar ekspor dan lokal, dan 3. Kelompok HMLM berdasarkan mulplier efek tinggi dan rendah. Hubungan antar aktor dalam implementasi kebijakan hilir karet dipetakan berdasarkan peraturan atau kelembagaan dan sistim insentif. Hal ini menunjukkan bahwa petani karet selalu berada pada posisi tawar yang sangat rendah di antara para pelaku lainnya. Pelajaran yang dipetik dan rekomendasi kebijakan untuk meningkatkan posisi tawar petani menjadi sorotan.
PENGARUH PERAN DAN KOMPETENSI PENYULUH PENDAMPING TERHADAP KEBERHASILAN GERAKAN PERCEPATAN PENGANEKARAGAMAN KONSUMSI PANGAN (P2KP) TAHUN 2014 DALAM MENDUKUNG KETAHANAN PANGAN DI KABUPATEN KLATEN
Authors: Sriningsih Fajar
Published: January 2020

Gerakan P2KP merupakan salah satu pilar mempertahankan dan meningkatkan ketahanan pangan serta membudayakan pola konsumsi yang Beragam, Bergizi, Seimbang dan Aman (B2SA), baik jumlah maupun mutunya guna meningkatkan kualitas konsumsi pangan masyarakat. Penelitian ini bertujuan untuk mengetahui pengaruh peran dan kompetensi penyuluh pendamping pada suatu gerakan dikaitkan kontribusinya terhadap ketahanan pangan di Kabupaten Klaten.Penelitian ini menggunakan metode penelitian campuran (mixedmethods) yaitu metode penulisan kuantitatif dan metode penulisan kualitatif. Hasil penelitian menunjukkan bahwa peran dan kompetensi penyuluh pendamping berpengaruh terhadap Gerakan Percepatan Penganekaragaman Konsumsi Pangan terhadap keberhasilan P2KP untuk mendukung Ketahanan Pangan daerah di Kabupaten Klaten
MANAJEMEN PENGENDALIAN DAN KEPEMIMPINAN PEREMPUAN
Authors: Lestari Norma Mugi , Budiharto Agus
Published: January 2020

Salah satu dampak positif dari perhatian khusus terhadap perempuan yaitu meluasnya sektor aktivitas perempuan ke dalam dunia politik. Tulisan ini bermaksud mendeskripsikan manajemen pengendalian dan kepemimpinan perempuan di Bidang Kesejahteraan Rakyat Kantor Kecamatan Trimurjo, Kabupaten Lampung Tengah. Menggunakan pendekatan penelitian kualitatif deskriptif, penelitian ini menyimpulkan pemimpin perempuan telah memiliki standar atau sasaran dan target yang harus dicapai dalam menjalankan fungsi manajemen dengan cara melakukan rapat agar bawahan mengetahui target apa saja yang akan dicapai.
PENGELOLAAN ALOKSI DANA DESA DI KAMPUNG BUMI MAS, KECAMATAN SEPUTIH AGUNG, KABUPATEN LAMPUNG TENGAH DALAM PERSPEKTIF AKUNTABILITAS
Authors: Susanti Meri , Widodo Wahyu
Published: January 2020

Kemampuan aparatur desa dalam pengelolaan dana sangat menentukan keberhasilan penggunaan alokasi dana desa sesuai dengan tujuan pemberdayaan masyarakat yang di prioritaskan pemerintah melalui Alokasi Dana Desa (ADD). Tulisan ini bertujuan menggambarkan akuntabilitas dalam hal perencanaan, pelaksanaan dan pertanggungjawaban. Kesimpulan penelitian ini yaitu pada tahap perencanaan penerapan prinsip partisipatif, responsif, trasparansi; pada tahap pelaksanaan prinsip partisipatif, responsif, transparan; faktor kompetensi sumber daya manusia.
Evaluasi Pilkada Serentak 2015 dan Pemilu 2019: Sebuah Catatan Singkat
Authors: Warganegara Arizka
Published: January 2020

Indikator sebuah negara demokrasi selalu diawali dengan adanya pemilihan umum, baik dilevel nasional maupun lokal. Pelaksaan Pilkada serentak tahun 2015 dan Pemilu tahun 2019 mengindikasi bahwa Indonesia sudah menjadi negara yang bergerak menuju negara dengan demokrasi yang matang. Sejauh ini tidak ditemukan konflik yang mengakar diaras public walaupun perhelatan dua event demokrasi besar tersebit menyisakan beragam evaluasi dimulai dari kritik terhadap sistem pemilu yang terlalu rumit, penyelenggara yang belum sempurna mengejahwantahkan peraturan pemilu di lapangan, kekurangan logistik pemilu dan berbagai pelanggaran pemilu yang ditemukan. Tulisan ini mencoba memberikan catatan terhadap kedua event politik tersebut. Catatan yang paling utama bagi Pilkada serentak adalah potensi kecurangan ternyata bukan terletak pada biaya kampanye formal yang pada Pilkada 2015 ditanggung oleh ‘penyelenggara’,  dalam konteks ini penyelenggara harus mampu menemukan formulasi teknis yang dapat mengurangi sebaran politik uang dan hal itu akan lebih bermanfaat bagi kualitas pemimpin yang terpilih. Sedangkan bagi Pemilu 2019, saya melihat justru persoalan distribusi logistic, pendataan pemilih dan sistem pemilu proporsional terbuka menjadi hal utama yang harus menjadi catatan dalam evaluasi Pemilu 2019.
FAKTOR PENGUAT DALAM IMPLEMENTASI KEBIJAKAN KAWASAN TANPA ROKOK DI INSTANSI PEMERINTAHAN KOTA PALEMBANG
Authors: Iriani Atrika
Published: January 2020

Penelitian ini bertujuan untuk menganalisis Faktor Penguat dalam Implementasi Kebijakan Kawasan Tanpa Rokok di Instansi Pemerintahan Kota Palembang. Jenis penelitian ini merupakan penelitian deksriptif kualitatif dengan fokus penelitian menganalisis Faktor Penguat dalam Implementasi Kebijakan Kawasan Tanpa Rokok di Instansi Pemerintahan Kota Palembang, yang terdiri dari himbauan organisasi, pengawasan internal dan penerapan sanksi. Data dikumpulkan melalui wawancara dengan key informant serta Tim Penegakan Hukum Peraturan Daerah Kawasan Tanpa Rokok (Perda KTR). Analisis data terdiri dari tahap Data Condensation, Data Display dan Conclusion Drawing/ Verifications. Hasil penelitian menunjukan bahwa berdasarkan faktor penguat, pihak Instansi yang melakukan pelanggaran terhadap Perda KTR hanya mendapat SP1 maupun SP2 saja, belum pernah diterapkan sanksi berupa hukum pidana kurungan paling lama tiga bulan atau denda administratif seperti yang tertuang pada Perda Kota Palembang No. 7 Tahun 2009 tentang Kawasan Tanpa Rokok.
STRATEGI PENANGANAN NARKOBA DI POLRES METRO (STUDI IFAS DAN EFAS)
Authors: Destrilia Intan , Atika Dewie Brima , Prihantika Ita
Published: January 2020

Artikel ini bertujuan untuk mengetahui bagaimana kondisi lingkungan nternal dan external dalam strategi penanganan peredaran narkoba di Kota Metro oleh Satuan Narkoba Polres Metro. Tipe penelitian ini merupakan tipe penelitian yang bersifat deskriptif dengan pendekatan kuantitatif. Faktor-faktor strategi lingkungan internal, yang menjadi kekuatan utama, yaitu: adanya kerjasama antara instansi kepolisian oleh stakeholder lainnya, sedangkan yang menjadi kelemahan utama, yaitu: kualitas tenaga pelatih yang masih sangat terbatas dan belum memadai sehingga belum sesuai standar kompetensi.. Faktor-faktor strategi lingkungan eksternal, yang menjadi peluang utama, yaitu: tugas operasional dalam menciptakan keamanan dalam negri melalui strategi Kepolisian semakin meningkat,sehingga menjadi peluang dalam membangun kepercayaan, sedangkan yang menjadi ancaman utama, yaitu: sistem hukum dan peradilan yang tumpang tindih. Belum terakomidasinya strategi sesuai dengan kebutuhan lingkungan karena belum adanya identifikasis lingkungan internal dan lingkungan eksternal tersendiri dari Satuan Narkoba Polres.
INVESTIGATION OF SPECTRUM CURVES FOR A STURM-LIOUVILLE PROBLEM WITH TWO-POINT NONLOCAL BOUNDARY CONDITIONS
Authors: Bingelė Kristina , Bankauskienė Agnė , Štikonas Artūras
Published: January 2020

The article investigates the Sturm–Liouville problem with one classical and another nonlocal two-point boundary condition. We analyze zeroes, poles and critical points of the characteristic function and how the properties of this function depend on parameters in nonlocal boundary condition. Properties of the Spectrum Curves are formulated and illustrated in ﬁgures for various values of parameter ξ.