bluuebunny/crossref_metadata_2025 huggingface dataset:
Polynomes de Jacobi Generalises et Integrales de Selberg
Authors: Barsky Daniel , Carpentier Michel
Published: January 2020

G. Anderson a développé une méthode nouvelle pour calculer l'intégrale de Selberg. Nous montrons que cette méthode s'applique aussi pour calculer une généralisation de l'intégrale de Selberg étudiée par J. Kaneko. Le résultat s'exprime à l'aide des polynômes de Jacobi symétriques à plusieurs variables. La preuve utilise les opérateurs de montée et de descente qui leur sont associés.
Counting Forests by Descents and Leaves
Authors: Gessel Ira M.
Published: January 2020

A descent of a rooted tree with totally ordered vertices is a vertex that is greater than at least one of its children. A leaf is a vertex with no children. We show that the number of forests of rooted trees on a given vertex set with $i+1$ leaves and $j$ descents is equal to the number with $j+1$ leaves and $i$ descents. We do this by finding a functional equation for the corresponding exponential generating function that shows that it is symmetric.
Discrete Morse Inequalities on Infinite Graphs
Authors: Ayala Rafael , Fernández Luis M. , Vilches José A.
Published: January 2020

The goal of this paper is to extend to infinite graphs the known Morse inequalities for discrete Morse functions proved by R. Forman in the finite case. In order to get this result we shall use a special kind of infinite subgraphs on which a discrete Morse function is monotonous, namely, decreasing rays. In addition, we shall use this result to characterize infinite graphs by the number of critical elements of discrete Morse functions defined on them.
Proof of the Alternating Sign Matrix Conjecture
Authors: Zeilberger Doron
Published: January 2020

The number of $n \times n$ matrices whose entries are either $-1$, $0$, or $1$, whose row- and column- sums are all $1$, and such that in every row and every column the non-zero entries alternate in sign, is proved to be $$[1!4! \dots (3n-2)!] \over [n!(n+1)! \dots (2n-1)!],$$ as conjectured by Mills, Robbins, and Rumsey.
Schur $q$-functions and Spin Characters of Symmetric Groups I
Authors: Morris Alun , Abdel-Aziz A. A.
Published: January 2020

Inspired by the early work of D.E.Littlewood and A.R.Richardson, Schur functions have been used to give useful combinatorial formulae for determining explicit values for the irreducible characters of the symmetric groups.In this,the first of two papers,we consider how Schur Q-functions can be used to obtain combinatorial formulae for the irreducible spin (projective) characters of symmetric groups.
Ternary Covering Codes
Authors: Habsieger Laurent
Published: January 2020

In [5], we studied binary codes with covering radius one via their characteristic functions. This gave us an easy way of obtaining congruence properties and of deriving interesting linear inequalities. In this paper we extend this approach to ternary covering codes. We improve on lower bounds for ternary $1$-covering codes, the so-called football pool problem, when $3$ does not divide $n-1$. We also give new lower bounds for some covering codes with a covering radius greater than one.
A random walk on the rook placements on a Ferrer's board
Authors: Hanlon Phil
Published: January 2020

Let $B$ be a Ferrers board, i.e., the board obtained by removing the Ferrers diagram of a partition from the top right corner of an $n\times n$ chessboard. We consider a Markov chain on the set $R$ of rook placements on $B$ in which you can move from one placement to any other legal placement obtained by switching the columns in which two rooks sit. We give sharp estimates for the rate of convergence of this Markov chain using spectral methods. As part of this analysis we give a complete combinatorial description of the eigenvalues of the transition matrix for this chain. We show that two extremes cases of this Markov chain correspond to random walks on groups which are analyzed in the literature. Our estimates for rates of convergence interpolate between those two results.
Packing Graphs: The Packing Problem Solved
Authors: Caro Yair , Yuster Raphael
Published: January 2020

For every fixed graph $H$, we determine the $H$-packing number of $K_n$, for all $n > n_0(H)$. We prove that if $h$ is the number of edges of $H$, and $gcd(H)=d$ is the greatest common divisor of the degrees of $H$, then there exists $n_0=n_0(H)$, such that for all $n > n_0$, $$ P(H,K_n)=\lfloor {{dn}\over{2h}} \lfloor {{n-1}\over{d}} \rfloor \rfloor, $$ unless $n = 1 \bmod d$ and $n(n-1)/d = b \bmod (2h/d)$ where $1 \leq b \leq d$, in which case $$ P(H,K_n)=\lfloor {{dn}\over{2h}} \lfloor {{n-1}\over{d}} \rfloor \rfloor - 1. $$ Our main tool in proving this result is the deep decomposition result of Gustavsson.
On Primitive 3-smooth Partitions of $n$
Authors: Avidon Michael
Published: January 2020

A primitive 3-smooth partition of $n$ is a representation of $n$ as the sum of numbers of the form $2^a 3^b$, where no summand divides another. Partial results are obtained in the problem of determining the maximal and average order of the number of such representations. Results are also obtained regarding the size of the terms in such a representation, resolving questions of Erdős and Selfridge.
Disconnected Vertex Sets and Equidistant Code Pairs
Authors: Haemers Willem H.
Published: January 2020

Two disjoint subsets $A$ and $B$ of a vertex set $V$ of a finite graph $G$ are called disconnected if there is no edge between $A$ and $B$. If $V$ is the set of words of length $n$ over an alphabet $\{1,\ldots,q\}$ and if two words are adjacent whenever their Hamming distance is not equal to a fixed $\delta\in\{1,\ldots,n\}$, then a pair of disconnected sets becomes an equidistant code pair. For disconnected sets $A$ and $B$ we will give a bound for $|A|.|B|$ in terms of the eigenvalues of a matrix associated with $G$. In case the complement of $G$ is given by a relation of an association scheme the bound takes an easy form, which applied to the Hamming scheme leads to a bound for equidistant code pairs. The bound turns out to be sharp for some values of $q$, $n$ and $\delta$, and for $q\rightarrow\infty$ for any fixed $n$ and $\delta$. In addition, our bound reproves some old results of Ahlswede and others, such as the maximal value of $|A|.|B|$ for equidistant code pairs $A$ and $B$ in the binary Hamming Scheme.
On the function "sandwiched" between $\alpha(G)$ and $\overline{\chi}(G)$
Authors: Dobrynin V. Y.
Published: January 2020

A new function of a graph $G$ is presented. Say that a matrix $B$ that is indexed by vertices of $G$ is feasible for $G$ if it is real, symmetric and $I \le B \le I + A(G),$ where $I$ is the identity matrix and $A(G)$ is the adjacency matrix of $G$. Let $\cal B(G)$ be the set of all feasible matrices for $G$, and let $\overline{\chi}(G)$ be the smallest number of cliques that cover the vertices of $G$. We show that $$ \alpha(G) \le \min \{ {\rm rank }(B)\ \vert B \in \cal B(G)\} \le \overline{\chi}(G) $$ and that $\alpha(G)= \min \{\ {\rm rank }(B)\ \vert B \in \cal B(G)\}$ implies $ \alpha(G)=\overline{\chi}(G).$
Asymptotics of Young Diagrams and Hook Numbers
Authors: Regev Amitai , Vershik Anatoly
Published: January 2020

Asymptotic calculations are applied to study the degrees of certain sequences of characters of symmetric groups. Starting with a given partition $\mu$, we deduce several skew diagrams which are related to $\mu$. To each such skew diagram there corresponds the product of its hook numbers. By asymptotic methods we obtain some unexpected arithmetic properties between these products. The authors do not know "finite", nonasymptotic proofs of these results. The problem appeared in the study of the hook formula for various kinds of Young diagrams. The proofs are based on properties of shifted Schur functions, due to Okounkov and Olshanski. The theory of these functions arose from the asymptotic theory of Vershik and Kerov of the representations of the symmetric groups.
Frankl-Füredi Type Inequalities for Polynomial Semi-lattices
Authors: Qian Jin , Ray-Chaudhuri Dijen K.
Published: January 2020

Let $X$ be an $n$-set and $L$ a set of nonnegative integers. ${\cal F}$, a set of subsets of $X$, is said to be an $L$ -intersection family if and only if for all $E \neq F \in {\cal F}, \, |E \cap F | \in L$. A special case of a conjecture of Frankl and Füredi states that if $ L = \{1, 2, \dots,k\}$,$ k$ a positive integer, then $|{\cal F}| \leq\sum_{i=0}^{k}{n-1\choose i}$. Here $|{\cal F}|$ denotes the number of elements in ${\cal F}$. Recently Ramanan proved this conjecture. We extend his method to polynomial semi-lattices and we also study some special $L$-intersection families on polynomial semi-lattices. Finally we prove two modular versions of Ray-Chaudhuri-Wilson inequality for polynomial semi-lattices.
A Purely Combinatorial Proof of the Hadwiger Debrunner $(p,q)$ Conjecture
Authors: Alon N. , Kleitman D. J.
Published: January 2020

A family of sets has the $(p,q)$ property if among any $p$ members of the family some $q$ have a nonempty intersection. The authors have proved that for every $p \geq q \geq d+1$ there is a $c=c(p,q,d) < \infty$ such that for every family ${\cal F}$ of compact, convex sets in $R^d$ which has the $(p,q)$ property there is a set of at most $c$ points in $R^d$ that intersects each member of ${\cal F}$, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result.
Calcul Basique des Permutations Signées, II: Analogues Finis des Fonctions de BesseL
Authors: Foata Dominique , Han Guo-Niu
Published: January 2020

The traditional basic calculus on permutation statistic distributions is extended to the case of signed permutations. This provides with a combinatorial interpretation of the basic Bessel functions and their finite analogues. Le calcul basique classique sur les distributions des statistiques des permutations est prolongé au cas des permutations signées. Ce calcul permet ainsi de donner une interprétation combinatoire aux fonctions basiques de Bessel et à leurs analogues finis.
Monotonic subsequences in dimensions higher than one.
Authors: Odlyzko A. , Shearer J. B. , Siders R.
Published: January 2020

The 1935 result of Erdos and Szekeres that any sequence of at least $n^{2}+1$ real numbers contains a monotonic subsequence of at least $n+1$ terms has stimulated extensive furher research, including a paper of J.B.Kruskal that defined an extension of monotonicity for higher dimensions. This paper provides a proof of a weakened form of Kruskal's conjecture for 2 dimensional Euclidean space by showing that there exists a sequence of n points in the plane for which the longest monotonic subsequences have length $n^{2}+2$ or less.. Weaker results are also obtained for higher dimensions. The average length of the longest increasing monotonic subsequence is shown to be $\sim 2n^{1/2}$ as $n\rightarrow\infty$ for each dimension.
The Last Digit of ${2n \choose n}$ and $\sum {n \choose i}{2n-2i \choose n-i}$
Authors: Shur Walter
Published: January 2020

Let $f_{n}= \sum_{i=0}^n {n \choose i}{ 2n-2i\choose n-i}$, $g_{n}= \sum_{i=1}^n {n\choose i}{2n-2i \choose n-i}$. Let $\{a_k\}_{k=1}$ be the set of all positive integers n, in increasing order, for which ${2n \choose n}$ is not divisible by 5, and let $\{b_k\}_{k=1}$ be the set of all positive integers n, in increasing order, for which $g_n$ is not divisible by 5. This note finds simple formulas for $a_k$, $b_k$, ${2n \choose n}$ mod 10, $ f_{n}$ mod 10, and $ g_{n}$ mod 10.
Parking Functions and Noncrossing Partitions
Authors: Stanley Richard P.
Published: January 2020

A parking function is a sequence $(a_1,\dots,a_n)$ of positive integers such that, if $b_1\leq b_2\leq \cdots\leq b_n$ is the increasing rearrangement of the sequence $(a_1,\dots, a_n),$ then $b_i\leq i$. A noncrossing partition of the set $[n]=\{1,2,\dots,n\}$ is a partition $\pi$ of the set $[n]$ with the property that if $a < b < c < d$ and some block $B$ of $\pi$ contains both $a$ and $c$, while some block $B'$ of $\pi$ contains both $b$ and $d$, then $B=B'$. We establish some connections between parking functions and noncrossing partitions. A generating function for the flag $f$-vector of the lattice NC$_{n+1}$ of noncrossing partitions of $[{\scriptstyle n+1}]$ is shown to coincide (up to the involution $\omega$ on symmetric function) with Haiman's parking function symmetric function. We construct an edge labeling of NC$_{n+1}$ whose chain labels are the set of all parking functions of length $n$. This leads to a local action of the symmetric group ${S}_n$ on NC$_{n+1}$.
Crossings, Colorings, and Cliques
Authors: Albertson Michael O. , Cranston Daniel W. , Fox Jacob
Published: January 2020

Albertson conjectured that if graph $G$ has chromatic number $r$, then the crossing number of $G$ is at least that of the complete graph $K_r$. This conjecture in the case $r=5$ is equivalent to the four color theorem. It was verified for $r=6$ by Oporowski and Zhao. In this paper, we prove the conjecture for $7 \leq r \leq 12$ using results of Dirac; Gallai; and Kostochka and Stiebitz that give lower bounds on the number of edges in critical graphs, together with lower bounds by Pach et al. on the crossing number of graphs in terms of the number of edges and vertices.
Periodic Sorting Using Minimum Delay, Recursively Constructed Merging Networks
Authors: Bender Edward A. , Williamson S. Gill
Published: January 2020

Let $\alpha$ and $\beta$ be a partition of $\{1,\ldots,n\}$ into two blocks. A merging network is a network of comparators which allows as input arbitrary real numbers and has the property that, whenever the input sequence $x_1,x_2,\ldots,x_n$ is such that the subsequence in the positions $\alpha$ and the subsequence in the positions $\beta$ are each sorted, the output sequence will be sorted. We study the class of "recursively constructed" merging networks and characterize those with delay $\lceil\log_2 n\rceil$ (the best possible delay for all merging networks). When $n$ is a power of 2, we show that at least $3^{n/2-1}$ of these nets are log-periodic sorters; that is, they sort any input sequence after $\log_2n$ passes through the net. (Two of these have appeared previously in the literature.)
All Ramsey numbers $r(K_{3},G)$ for connected graphs of order 9
Authors: Brandt Stephan , Brinkmann Gunnar , Harmuth Thomas
Published: January 2020

We determine the Ramsey numbers $r(K_3,G)$ for all $261080$ connected graphs of order $9$ and further Ramsey numbers of this type for some graphs of order up to $12$. Almost all of them were determined by computer programs which are based on a program for generating maximal triangle-free graphs.
Finite Vector Spaces and Certain Lattices
Authors: Cusick Thomas W.
Published: January 2020

The Galois number $G_n(q)$ is defined to be the number of subspaces of the $n$-dimensional vector space over the finite field $GF(q)$. When $q$ is prime, we prove that $G_n(q)$ is equal to the number $L_n(q)$ of $n$-dimensional mod $q$ lattices, which are defined to be lattices (that is, discrete additive subgroups of n-space) contained in the integer lattice ${\bf Z}^n$ and having the property that given any point $P$ in the lattice, all points of ${\bf Z}^n$ which are congruent to $P$ mod $q$ are also in the lattice. For each $n$, we prove that $L_n(q)$ is a multiplicative function of $q$.
Recognizing Circulant Graphs of Prime Order in Polynomial Time
Authors: Muzychuk Mikhail E. , Tinhofer Gottfried
Published: January 2020

A circulant graph $G$ of order $n$ is a Cayley graph over the cyclic group ${\bf Z}_n.$ Equivalently, $G$ is circulant iff its vertices can be ordered such that the corresponding adjacency matrix becomes a circulant matrix. To each circulant graph we may associate a coherent configuration ${\cal A}$ and, in particular, a Schur ring ${\cal S}$ isomorphic to ${\cal A}$. ${\cal A}$ can be associated without knowing $G$ to be circulant. If $n$ is prime, then by investigating the structure of ${\cal A}$ either we are able to find an appropriate ordering of the vertices proving that $G$ is circulant or we are able to prove that a certain necessary condition for $G$ being circulant is violated. The algorithm we propose in this paper is a recognition algorithm for cyclic association schemes. It runs in time polynomial in $n$.
The Permutation Classes Equinumerous to the Smooth Class
Authors: Bóna Miklós
Published: January 2020

We determine all permutation classes defined by pattern avoidance which are equinumerous to the class of permutations whose Schubert variety is smooth. We also provide a lattice path interpretation for the numbers of such permutations.
Durfee Polynomials
Authors: Canfield E. Rodney , Corteel Sylvie , Savage Carla D.
Published: January 2020

Let ${\bf F}(n)$ be a family of partitions of $n$ and let ${\bf F}(n,d)$ denote the set of partitions in ${\bf F}(n)$ with Durfee square of size $d$. We define the Durfee polynomial of ${\bf F}(n)$ to be the polynomial $P_{{\bf F},n}= \sum |{\bf F}(n,d)|y^d$, where $ 0 \leq d \leq \lfloor \sqrt{n} \rfloor.$ The work in this paper is motivated by empirical evidence which suggests that for several families ${\bf F}$, all roots of the Durfee polynomial are real. Such a result would imply that the corresponding sequence of coefficients $\{|{\bf F}(n,d)|\}$ is log-concave and unimodal and that, over all partitions in ${\bf F}(n)$ for fixed $n$, the average size of the Durfee square, $a_{{\bf F}}(n)$, and the most likely size of the Durfee square, $m_{{\bf F}}(n)$, differ by less than 1. In this paper, we prove results in support of the conjecture that for the family of ordinary partitions, ${\bf P}(n)$, the Durfee polynomial has all roots real. Specifically, we find an asymptotic formula for $|{\bf P}(n,d)|$, deriving in the process a simple upper bound on the number of partitions of $n$ with at most $k$ parts which generalizes the upper bound of Erdös for $|{\bf P}(n)|$. We show that as $n$ tends to infinity, the sequence $\{|{\bf P}(n,d)|\},\ 1 \leq d \leq \sqrt{n},$ is asymptotically normal, unimodal, and log concave; in addition, formulas are found for $a_{{\bf P}}(n)$ and $m_{{\bf P}}(n)$ which differ asymptotically by at most 1. Experimental evidence also suggests that for several families ${\bf F}(n)$ which satisfy a recurrence of a certain form, $m_{{\bf F}}(n)$ grows as $c \sqrt{n}$, for an appropriate constant $c=c_{{\bf F}}$. We prove this under an assumption about the asymptotic form of $|{\bf F}(n,d)|$ and show how to produce, from recurrences for the $|{\bf F}(n,d)|$, analytical expressions for the constants $c_{{\bf F}}$ which agree numerically with the observed values.
Another Infinite Sequence of Dense Triangle-Free Graphs
Authors: Brandt Stephan , Pisanski Tomaž
Published: January 2020

The core is the unique homorphically minimal subgraph of a graph. A triangle-free graph with minimum degree $\delta > n/3$ is called dense. It was observed by many authors that dense triangle-free graphs share strong structural properties and that the natural way to describe the structure of these graphs is in terms of graph homomorphisms. One infinite sequence of cores of dense maximal triangle-free graphs was known. All graphs in this sequence are 3-colourable. Only two additional cores with chromatic number 4 were known. We show that the additional graphs are the initial terms of a second infinite sequence of cores.
Constructions for Cubic Graphs with Large Girth
Authors: Biggs Norman
Published: January 2020

The aim of this paper is to give a coherent account of the problem of constructing cubic graphs with large girth. There is a well-defined integer $\mu_0(g)$, the smallest number of vertices for which a cubic graph with girth at least $g$ exists, and furthermore, the minimum value $\mu_0(g)$ is attained by a graph whose girth is exactly $g$. The values of $\mu_0(g)$ when $3 \le g \le 8$ have been known for over thirty years. For these values of $g$ each minimal graph is unique and, apart from the case $g=7$, a simple lower bound is attained. This paper is mainly concerned with what happens when $g \ge 9$, where the situation is quite different. Here it is known that the simple lower bound is attained if and only if $g=12$. A number of techniques are described, with emphasis on the construction of families of graphs $\{ G_i\}$ for which the number of vertices $n_i$ and the girth $g_i$ are such that $n_i\le 2^{cg_i}$ for some finite constant $c$. The optimum value of $c$ is known to lie between $0.5$ and $0.75$. At the end of the paper there is a selection of open questions, several of them containing suggestions which might lead to improvements in the known results. There are also some historical notes on the current-best graphs for girth up to 36.
Flattening Antichains with Respect to the Volume
Authors: Brankovic Ljiljana , Lieby Paulette , Miller Mirka
Published: January 2020

We say that an antichain $\cal A$ in the boolean lattice $B_n$ is flat if there exists an integer $k\geq 0$ such that every set in $\cal A$ has cardinality either $k$ or $k+1$. Define the volume of $\cal A$ to be $\sum_{A\in{\cal A}}|A|$. We prove that for every antichain $\cal A$ in $B_n$ there exist an antichain which is flat and has the same volume as $\cal A$.
The Asymptotic Number of Set Partitions with Unequal Block Sizes
Authors: Knopfmacher A. , Odlyzko A. M. , Pittel B. , Richmond L. B. , Stark D. , Szekeres G. , Wormald N. C.
Published: January 2020

The asymptotic behavior of the number of set partitions of an $n$-element set into blocks of distinct sizes is determined. This behavior is more complicated than is typical for set partition problems. Although there is a simple generating function, the usual analytic methods for estimating coefficients fail in the direct approach, and elementary approaches combined with some analytic methods are used to obtain most of the results. Simultaneously, we obtain results on the shape of a random partition of an $n$-element set into blocks of distinct sizes.
Longest Increasing Subsequences of Random Colored Permutations
Authors: Borodin Alexei
Published: January 2020

We compute the limit distribution for the (centered and scaled) length of the longest increasing subsequence of random colored permutations. The limit distribution function is a power of that for usual random permutations computed recently by Baik, Deift, and Johansson (math.CO/9810105). In the two–colored case our method provides a different proof of a similar result by Tracy and Widom about the longest increasing subsequences of signed permutations (math.CO/9811154). Our main idea is to reduce the 'colored' problem to the case of usual random permutations using certain combinatorial results and elementary probabilistic arguments.
$2$-adic Behavior of Numbers of Domino Tilings
Authors: Cohn Henry
Published: January 2020

We study the $2$-adic behavior of the number of domino tilings of a $2n \times 2n$ square as $n$ varies. It was previously known that this number was of the form $2^nf(n)^2$, where $f(n)$ is an odd, positive integer. We show that the function $f$ is uniformly continuous under the $2$-adic metric, and thus extends to a function on all of $Z$. The extension satisfies the functional equation $f(-1-n) = \pm f(n)$, where the sign is positive iff $n \equiv 0,3 \pmod{4}$.
Reconstructing Subsets of Reals
Authors: Radcliffe A. J. , Scott A. D.
Published: January 2020

We consider the problem of reconstructing a set of real numbers up to translation from the multiset of its subsets of fixed size, given up to translation. This is impossible in general: for instance almost all subsets of $\mathbb{Z}$ contain infinitely many translates of every finite subset of $\mathbb{Z}$. We therefore restrict our attention to subsets of $\mathbb{R}$ which are locally finite; those which contain only finitely many translates of any given finite set of size at least 2. We prove that every locally finite subset of $\mathbb{R}$ is reconstructible from the multiset of its 3-subsets, given up to translation.
Almost all graphs with $2.522 n$ edges are not 3-colorable
Authors: Achlioptas Dimitris , Molloy Michael
Published: January 2020

We prove that for $c \geq 2.522$ a random graph with $n$ vertices and $m=cn$ edges is not 3-colorable with probability $1-o(1)$. Similar bounds for non-$k$-colorability are given for $k>3$.
On the Twin Designs with the Ionin–type Parameters
Authors: Kharaghani H.
Published: January 2020

Let $4n^2$ be the order of a Bush-type Hadamard matrix with $q=(2n-1)^2$ a prime power. It is shown that there is a weighing matrix $$ W(4(q^m+q^{m-1}+\cdots+q+1)n^2,4q^mn^2) $$ which includes two symmetric designs with the Ionin–type parameters $$ \nu=4(q^m+q^{m-1}+\cdots+q+1)n^2,\;\;\; \kappa=q^m(2n^2-n), \;\;\; \lambda=q^m(n^2-n) $$ for every positive integer $m$. Noting that Bush–type Hadamard matrices of order $16n^2$ exist for all $n$ for which an Hadamard matrix of order $4n$ exist, this provides a new class of symmetric designs.
Resolving Triple Systems into Regular Configurations
Authors: Mendelsohn E. , Quattrocchi G.
Published: January 2020

A $\lambda-Triple\ System(v)$, or a $\lambda $–$TS(V,\cal{B})$, is a pair (V, $\cal{B}$) where V is a set and $\cal{B}$ is a subset of the 3-subsets of V so that every pair is in exactly $\lambda$ elements of $\cal{B}$. A $regular\ configuration$ on p points with regularity $\rho$ on $l$ blocks is a pair (P,${\cal L}$) where $\cal{L}$ is a collection of 3-subsets of a (usually small) set P so that every p in P is in exactly $\rho$ elements of ${\cal L}$, and $|{\cal L}|=l$. The Pasch configuration $(\{0,1,2,3,4,5\},\{ 012,035,245,134\})$ has p=6, $l$=4, and $\rho$=2. A $\lambda$–$TS(V,\cal{B})$, is resolvable into a regular configuration ${\Bbb C}$=(P,${\cal L}$), or ${\Bbb C}$–resolvable, if ${\cal B}$ can be partitioned into sets $\Pi_{i}$ so that for each i, (V,$\Pi_{i}$) is isomorphic to a set of vertex disjoint copies of (P,${\cal L}$). If the configuration is a single block on three points this corresponds to ordinary resolvability of a Triple System. In this paper we examine all regular configurations ${\Bbb C}$ on 6 or fewer blocks and construct ${\Bbb C}$–resolvable $\lambda$–Triple Systems of order v for many values of v and $\lambda$. These conditions are also sufficient for each ${\Bbb C}$ having 4 blocks or fewer. For example for the Pasch configuration $\lambda \equiv 0 \pmod{4}$ and $v \equiv 0 \pmod{6}$ are necessary and sufficient.
A Note on Sparse Random Graphs and Cover Graphs
Authors: Bohman Tom , Frieze Alan , Ruszinkó Miklós , Thoma Lubos
Published: January 2020

It is shown in this note that with high probability it is enough to destroy all triangles in order to get a cover graph from a random graph $G_{n,p}$ with $p\le \kappa \log n/n$ for any constant $\kappa < 2/3$. On the other hand, this is not true for somewhat higher densities: If $p\ge \lambda (\log n)^3 / (n\log\log n)$ with $\lambda > 1/8$ then with high probability we need to delete more edges than one from every triangle. Our result has a natural algorithmic interpretation.
Composition sum identities related to the distribution of coordinate values in a discrete simplex
Authors: Milson R.
Published: January 2020

Utilizing spectral residues of parameterized, recursively defined sequences, we develop a general method for generating identities of composition sums. Specific results are obtained by focusing on coefficient sequences of solutions of first and second order, ordinary, linear differential equations. Regarding the first class, the corresponding identities amount to a proof of the exponential formula of labelled counting. The identities in the second class can be used to establish certain geometric properties of the simplex of bounded, ordered, integer tuples. We present three theorems that support the conclusion that the inner dimensions of such an order simplex are, in a certain sense, more ample than the outer dimensions. As well, we give an algebraic proof of a bijection between two families of subsets in the order simplex, and inquire as to the possibility of establishing this bijection by combinatorial, rather than by algebraic methods.
Multipartite Separability of Laplacian Matrices of Graphs
Authors: Wu Chai Wah
Published: January 2020

Recently, Braunstein et al. introduced normalized Laplacian matrices of graphs as density matrices in quantum mechanics and studied the relationships between quantum physical properties and graph theoretical properties of the underlying graphs. We provide further results on the multipartite separability of Laplacian matrices of graphs. In particular, we identify complete bipartite graphs whose normalized Laplacian matrix is multipartite entangled under any vertex labeling. Furthermore, we give conditions on the vertex degrees such that there is a vertex labeling under which the normalized Laplacian matrix is entangled. These results address an open question raised in Braunstein et al. Finally, we show that the Laplacian matrix of any product of graphs (strong, Cartesian, tensor, lexicographical, etc.) is multipartite separable, extending analogous results for bipartite and tripartite separability.
The Action of the Symmetric Group on a Generalized Partition Semilattice
Authors: Gill Robert
Published: January 2020

Given an integer $n\geq 2$, and a non-negative integer $k$, consider all affine hyperplanes in ${\bf R}^n$ of the form $x_i=x_j +r$ for $i,j\in[n]$ and a non-negative integer $r\leq k$. Let $\Pi_{n,k}$ be the poset whose elements are all nonempty intersections of these affine hyperplanes, ordered by reverse inclusion. It is noted that $\Pi_{n,0}$ is isomorphic to the well-known partition lattice $\Pi_n$, and in this paper, we extend some of the results of $\Pi_n$ by Hanlon and Stanley to $\Pi_{n,k}$. Just as there is an action of the symmetric group ${S}_n$ on $\Pi_n$, there is also an action on $\Pi_{n,k}$ which permutes the coordinates of each element. We consider the subposet $\Pi_{n,k}^\sigma$ of elements that are fixed by some $\sigma\in {S}_n$, and find its Möbius function $\mu_\sigma$, using the characteristic polynomial. This generalizes what Hanlon did in the case $k=0$. It then follows that $(-1)^{n-1}\mu_\sigma(\Pi_{n,k}^\sigma)$, as a function of $\sigma$, is the character of the action of ${S}_n$ on the homology of $\Pi_{n,k}$. Let $\Psi_{n,k}$ be this character times the sign character. For ${C}_n$, the cyclic group generated by an $n$-cycle $\sigma $ of ${S}_n$, we take its irreducible characters and induce them up to ${S}_n$. Stanley showed that $\Psi_{n,0}$ is just the induced character $\chi\uparrow_{{C}_n}^{{S}_n}$ where $\chi(\sigma)=e^{2\pi i/n}$. We generalize this by showing that for $k>0$, there exists a non-negative integer combination of the induced characters described here that equals $\Psi_{n,k}$, and we find explicit formulas. In addition, we show another way to prove that $\Psi_{n,k}$ is a character, without using homology, by proving that the derived coefficients of certain induced characters of ${S}_n$ are non-negative integers.
Bijections for hook pair identities
Authors: Krattenthaler C.
Published: January 2020

Short, bijective proofs of identities for multisets of 'hook pairs' (arm-leg pairs) of the cells of certain diagrams are given. These hook pair identities were originally found by Regev.
Counting Lattice Paths by Narayana Polynomials
Authors: Sulanke Robert A.
Published: January 2020

Let $d(n)$ count the lattice paths from $(0,0)$ to $(n,n)$ using the steps (0,1), (1,0), and (1,1). Let $e(n)$ count the lattice paths from $(0,0)$ to $(n,n)$ with permitted steps from the step set ${\bf N} \times {\bf N} - \{(0,0)\}$, where ${\bf N}$ denotes the nonnegative integers. We give a bijective proof of the identity $e(n) = 2^{n-1} d(n)$ for $n \ge 1$. In giving perspective for our proof, we consider bijections between sets of lattice paths defined on various sets of permitted steps which yield path counts related to the Narayana polynomials.
Linear Discrepancy of Basic Totally Unimodular Matrices
Authors: Doerr Benjamin
Published: January 2020

We show that the linear discrepancy of a basic totally unimodular matrix $A \in R^{m \times n}$ is at most $1- {1\over {n+1}}$. This extends a result of Peng and Yan.
Franklin's Argument Proves an Identity of Zagier
Authors: Chapman Robin
Published: January 2020

Recently Zagier proved a remarkable $q$-series identity. We show that this identity can also be proved by modifying Franklin's classical proof of Euler's pentagonal number theorem.
Small Forbidden Configurations II
Authors: Anstee Richard , Ferguson Ron , Sali Attila
Published: January 2020

The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. In the notation of (0,1)-matrices, we consider a (0,1)-matrix $F$ (the forbidden configuration), an $m\times n$ (0,1)-matrix $A$ with no repeated columns which has no submatrix which is a row and column permutation of $F$, and seek bounds on $n$ in terms of $m$ and $F$. We give new exact bounds for some $2\times l$ forbidden configurations and some asymptotically exact bounds for some other $2\times l$ forbidden configurations. We frequently employ graph theory and in one case develop a new vertex ordering for directed graphs that generalizes Rédei's Theorem for Tournaments. One can now imagine that exact bounds could be available for all $2\times l$ forbidden configurations. Some progress is reported for $3\times l$ forbidden configurations. These bounds are improvements of the general bounds obtained by Sauer, Perles and Shelah, Vapnik and Chervonenkis.
On the Upper and Lower Chromatic Numbers of BSQSs(16)
Authors: Faro Giovanni Lo , Milazzo Lorenzo , Tripodi Antoinette
Published: January 2020

A mixed hypergraph is characterized by the fact that it possesses ${\cal C}$-edges as well as ${\cal D}$-edges. In a colouring of a mixed hypergraph, every ${\cal C}$-edge has at least two vertices of the same colour and every ${\cal D}$-edge has at least two vertices coloured differently. The upper and lower chromatic numbers $\bar{\chi}$, $\chi$ are the maximum and minimum numbers of colours for which there exists a colouring using all the colours. The concepts of mixed hypergraph, upper and lower chromatic numbers are applied to $SQSs$. In fact a BSQS is an SQS where all the blocks are at the same time ${\cal C}$-edges and ${\cal D}$-edges. In this paper we prove that any $BSQS(16)$ is colourable with the upper chromatic number $\bar{\chi}=3$ and we give new information about the chromatic spectrum of BSQSs($16$).
Dumont's Statistic on Words
Authors: Skandera Mark
Published: January 2020

We define Dumont's statistic on the symmetric group $S_n$ to be the function dmc: $S_n \rightarrow {\bf N}$ which maps a permutation $\sigma$ to the number of distinct nonzero letters in code$( \sigma )$. Dumont showed that this statistic is Eulerian. Naturally extending Dumont's statistic to the rearrangement classes of arbitrary words, we create a generalized statistic which is again Eulerian. As a consequence, we show that for each distributive lattice $J(P)$ which is a product of chains, there is a poset $Q$ such that the $f$-vector of $Q$ is the $h$-vector of $J(P)$. This strengthens for products of chains a result of Stanley concerning the flag $h$-vectors of Cohen-Macaulay complexes. We conjecture that the result holds for all finite distributive lattices.
Bijective proofs for Schur function identities which imply Dodgson's condensation formula and Plücker relations
Authors: Fulmek Markus , Kleber Michael
Published: January 2020

We present a "method" for bijective proofs for determinant identities, which is based on translating determinants to Schur functions by the Jacobi–Trudi identity. We illustrate this "method" by generalizing a bijective construction (which was first used by Goulden) to a class of Schur function identities, from which we shall obtain bijective proofs for Dodgson's condensation formula, Plücker relations and a recent identity of the second author.
On a Multiplicative Partition Function
Authors: Yang Yifan
Published: January 2020

Let $D(s)=\sum^\infty_{m=1}a_mm^{-s}$ be the Dirichlet series generated by the infinite product $\prod^\infty_{k=2}(1-k^{-s})$. The value of $a_m$ for squarefree integers $m$ with $n$ prime factors depends only on the number $n$, and we let $f(n)$ denote this value. We prove an asymptotic estimate for $f(n)$ which allows us to solve several problems raised in a recent paper by M. V. Subbarao and A. Verma.
On Coset Coverings of Solutions of Homogeneous Cubic Equations over Finite Fields
Authors: Aleksanyan Ara , Papikian Mihran
Published: January 2020

Given a cubic equation $x_1y_1z_1+x_2y_2z_2+\cdots +x_ny_nz_n=b$ over a finite field, it is necessary to determine the minimal number of systems of linear equations over the same field such that the union of their solutions exactly coincides with the set of solutions of the initial equation. The problem is solved for arbitrary size of the field. A covering with almost minimum complexity is constructed.
Weakly Self-Avoiding Words and a Construction of Friedman
Authors: Shallit Jeffrey , Wang Ming-wei
Published: January 2020

H. Friedman obtained remarkable results about the longest finite sequence $x$ over a finite alphabet such that for all $i \ne j$ the word $x[i..2i]$ is not a subsequence of $x[j..2j]$. In this note we consider what happens when "subsequence" is replaced by "subword"; we call such a sequence a "weakly self-avoiding word". We prove that over an alphabet of size $1$ or $2$, there is an upper bound on the length of weakly self-avoiding words, while if the alphabet is of size $3$ or more, there exists an infinite weakly self-avoiding word.
Chromatic Number for a Generalization of Cartesian Product Graphs
Authors: Král' Daniel , West Douglas B.
Published: January 2020

Let ${\cal G}$ be a class of graphs. A $d$-fold grid over ${\cal G}$ is a graph obtained from a $d$-dimensional rectangular grid of vertices by placing a graph from ${\cal G}$ on each of the lines parallel to one of the axes. Thus each vertex belongs to $d$ of these subgraphs. The class of $d$-fold grids over ${\cal G}$ is denoted by ${\cal G}^d$. Let $f({\cal G};d)=\max_{G\in{\cal G}^d}\chi(G)$. If each graph in ${\cal G}$ is $k$-colorable, then $f({\cal G};d)\le k^d$. We show that this bound is best possible by proving that $f({\cal G};d)=k^d$ when ${\cal G}$ is the class of all $k$-colorable graphs. We also show that $f({\cal G};d)\ge{\left\lfloor\sqrt{{d\over 6\log d}}\right\rfloor}$ when ${\cal G}$ is the class of graphs with at most one edge, and $f({\cal G};d)\ge {\left\lfloor{d\over 6\log d}\right\rfloor}$ when ${\cal G}$ is the class of graphs with maximum degree $1$.
Computing Evolutionary Chains in Musical Sequences
Authors: Crochemore Maxime , Iliopoulos Costas S. , Pinzon Yoan J.
Published: January 2020

Musical patterns that recur in approximate, rather than identical, form within the body of a musical work are considered to be of considerable importance in music analysis. Here we consider the "evolutionary chain problem": this is the problem of computing a chain of all "motif" recurrences, each of which is a transformation of ("similar" to) the original motif, but each of which may be progressively further from the original. Here we consider several variants of the evolutionary chain problem and we present efficient algorithms and implementations for solving them.
A Simple Card Guessing Game Revisited
Authors: Knopfmacher Arnold , Prodinger Helmut
Published: January 2020

A deck of cards consisting of $m$ red and $n$ black cards is given. A guess is made as to the colour of the top card, after which it is revealed and discarded. To maximise the number of correct guesses one chooses the colour corresponding to the majority of cards remaining in the deck. We determine the expected number of correct guesses with this strategy, as well as the probability of beating an opponent who uses the naive stategy of random guessing.
Sumsets of Finite Beatty Sequences
Authors: Pitman Jane
Published: January 2020

An investigation of the size of $S+S$ for a finite Beatty sequence $S=(s_i)=(\lfloor i\alpha+\gamma \rfloor)$, where $\lfloor \hphantom{x} \rfloor$ denotes "floor", $\alpha$, $\gamma$ are real with $\alpha\ge 1$, and $0\le i \le k-1$ and $k\ge 3$. For $\alpha>2$, it is shown that $|S+S|$ depends on the number of "centres" of the Sturmian word $\Delta S=(s_i-s_{i-1})$, and hence that $3(k-1)\le |S+S|\le 4k-6$ if $S$ is not an arithmetic progression. A formula is obtained for the number of centres of certain finite periodic Sturmian words, and this leads to further information about $|S+S|$ in terms of finite nearest integer continued fractions.
On the Orbits of Singer Groups and Their Subgroups
Authors: Drudge Keldon
Published: January 2020

We study the action of Singer groups of projective geometries (and their subgroups) on $(d-1)$-flats for arbitrary $d$. The possibilities which can occur are determined, and a formula for the number of orbits of each possible size is given. Motivated by an old problem of J.R. Isbell on the existence of certain permutation groups we pose the problem of determining, for given $q$ and $h$, the maximum co-dimension $f_q(n, h)$ of a flat of $PG(n-1, q)$ whose orbit under a subgroup of index $h$ of some Singer group covers all points of $PG(n-1, q)$. It is clear that $f_q (n, h) < n - \log_q (h)$; on the other hand we show that $f_q(n, h) \geq n - 1 - 2 \log _q (h)$.
The Directed Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Directed Graphs of Odd Order
Authors: Stevens Brett
Published: January 2020

The directed anti-Oberwolfach problem asks for a 2-factorization (each factor has in-degree 1 and out-degree 1 for a total degree of two) of $K_{2n+1}$, not with consistent cycle components in each 2-factor like the Oberwolfach problem, but such that every admissible cycle size appears at least once in some 2-factor. The solution takes advantage of both Piotrowski's decomposition techniques used to solve Oberwolfach problems and the techniques used by the author to solve the undirected anti-Oberwolfach problem.
A 'Nice' Bijection for a Content Formula for Skew Semistandard Young Tableaux
Authors: Rubey Martin
Published: January 2020

Based on Schützenberger's evacuation and a modification of jeu de taquin, we give a bijective proof of an identity connecting the generating function of reverse semistandard Young tableaux with bounded entries with the generating function of all semistandard Young tableaux. This solves Exercise 7.102 b of Richard Stanley's book 'Enumerative Combinatorics 2'.
On Recursively Directed Hypercubes
Authors: Domshlak Carmel
Published: January 2020

In this paper we introduce the recursively directed hypercubes, and analyze some of their structural properties. We show that every recursively directed hypercube is acyclic, and has a unique pair of source and sink nodes. The main contribution of the paper is an analysis of distances between the nodes in such a graph. We show that the distance from the source node to any other node, and from any node to the sink node is bounded by $n+1$, where $n$ is the dimension of the hypercube, but the diameter of a recursively directed hypercube may be exponential in $n$.
Bitableaux Bases for some Garsia-Haiman Modules and Other Related Modules
Authors: Allen E. E.
Published: January 2020

For certain subsets $S$ and $T$ of $${\cal A} =\bigl\{\cdots, (0,2), (0,1), (0,0), (1,0), (2,0), \cdots \bigr\}$$ and factor spaces ${\bf C}_{S}[X,Y]$, ${\bf C}^{+}_{S,T}[X,Y,Z,W]$ and ${\bf C}^{-}_{S,T}[X,Y,Z,W]$, bitableaux bases are constructed that are indexed by pairs of standard tableaux and sequences in the collections $\Upsilon_{\psi_S}$ and $\Upsilon_{\psi_T}$. These bases give combinatorial interpretations to the appropriate Hilbert series of these spaces as well as the graded character of ${\bf C}_{S}[X,Y]$. The factor space ${\bf C}_{S}[X,Y]$ is an analogue of the coinvariant ring of a polynomial ring in two sets of variables. ${\bf C}^{+}_{S,T}[X,Y,Z,W]$ and ${\bf C}^{-}_{S,T}[X,Y,Z,W]$ are analogues of coinvariant spaces in symmetric and skew-symmetric polynomial settings, respectively. The elements of the bitableaux bases are appropriately defined images in the polynomial spaces of bipermanents. The combinatorial interpretations of the respective Hilbert series and graded characters are given by statistics based on cocharge tableaux. Additionally, it is shown that the Hilbert series and graded characters factor nicely. One of these factors gives the Hilbert series of a collection of Schur functions $s_{\lambda/\mu}$ where $\mu$ varies in an appropriately defined $\lambda$.
Mr. Paint and Mrs. Correct
Authors: Schauz Uwe
Published: January 2020

We introduce a coloring game on graphs, in which each vertex $v$ of a graph $G$ owns a stack of $\ell_v{-}1$ erasers. In each round of this game the first player Mr. Paint takes an unused color, and colors some of the uncolored vertices. He might color adjacent vertices with this color – something which is considered "incorrect". However, Mrs. Correct is positioned next to him, and corrects his incorrect coloring, i.e., she uses up some of the erasers – while stocks (stacks) last – to partially undo his assignment of the new color. If she has a winning strategy, i.e., she is able to enforce a correct and complete final graph coloring, then we say that $G$ is $\ell$-paintable. Our game provides an adequate game-theoretic approach to list coloring problems. The new concept is actually more general than the common setting with lists of available colors. It could have applications in time scheduling, when the available time slots are not known in advance. We give an example that shows that the two notions are not equivalent; $\ell$-paintability is stronger than $\ell$-list colorability. Nevertheless, many deep theorems about list colorability remain true in the context of paintability. We demonstrate this fact by proving strengthened versions of classical list coloring theorems. Among the obtained extensions are paintability versions of Thomassen's, Galvin's and Shannon's Theorems.
A Density Result for Random Sparse Oriented Graphs and its Relation to a Conjecture of Woodall
Authors: Donadelli Jair , Kohayakawa Yoshiharu
Published: January 2020

We prove that for all $\ell \ge 3$ and $\beta >0$ there exists a sparse oriented graph of arbitrarily large order with oriented girth $\ell$ and such that any $1/2 + \beta$ proportion of its arcs induces an oriented cycle of length $\ell$. As a corollary we get that there exist infinitely many oriented graphs with vanishing density of oriented girth $\ell$ such that deleting any $1/\ell$-fraction of their edges does not destroy all their oriented cycles. The proof is probabilistic.
On Growth Rates of Closed Permutation Classes
Authors: Kaiser Tomáš , Klazar Martin
Published: January 2020

A class of permutations $\Pi$ is called closed if $\pi\subset\sigma\in\Pi$ implies $\pi\in\Pi$, where the relation $\subset$ is the natural containment of permutations. Let $\Pi_n$ be the set of all permutations of $1,2,\dots,n$ belonging to $\Pi$. We investigate the counting functions $n\mapsto|\Pi_n|$ of closed classes. Our main result says that if $|\Pi_n| < 2^{n-1}$ for at least one $n\ge 1$, then there is a unique $k\ge 1$ such that $F_{n,k}\le |\Pi_n|\le F_{n,k}\cdot n^c$ holds for all $n\ge 1$ with a constant $c>0$. Here $F_{n,k}$ are the generalized Fibonacci numbers which grow like powers of the largest positive root of $x^k-x^{k-1}-\cdots-1$. We characterize also the constant and the polynomial growth of closed permutation classes and give two more results on these.