bluuebunny/crossref_metadata_2025 huggingface dataset:
The Impact of Neoliberalism and Traditions of the European City on the Transformations of the Major Urban Projects Management in Western European and Post-socialist Cities
Authors: Doleželová Lucie
Published: January 2020

The article compares changes in the management of major urban projects in Western European and post-socialist cities. It examines their project management methods and project objectives and sheds light on the impact of neoliberal policies. Attention is paid to the presence of pro-social; or, more precisely, public interest project measures that demonstrate whether the cities are successful in promoting non-commercial objectives, or whether they are better left to market mechanisms. Although the management of West European projects is criticized as being overly neoliberal, it can be shown, by using the example of European cities, that their social background is still strong. This finding is contrasted with the situation of post-socialist cities whose predominantly liberal urban policies are now becoming more socially oriented.
Pendidikan Agama Islam dan Pembentukan Karakter
Authors: Faizin Faizin
Published: January 2020

Islamic education  is one of the most importances pilar of character education. Character education will build well, if it is started from cultivating religious sense of students, therefore, PAI lesson become one of supporting lesson of character education. Through PAI teaching and learning, the students is taught belief of God as the basic of their religion, taught al Qur’an and Hadits as their way of life, taught fiqih as law signs in doing Islam teaching, taught Islam history as a good life example, and taught ethica as the way of human character.
Maximum Matchings in Regular Graphs of High Girth
Authors: Flaxman Abraham D. , Hoory Shlomo
Published: January 2020

Let $G=(V,E)$ be any $d$-regular graph with girth $g$ on $n$ vertices, for $d \geq 3$. This note shows that $G$ has a maximum matching which includes all but an exponentially small fraction of the vertices, $O((d-1)^{-g/2})$. Specifically, in a maximum matching of $G$, the number of unmatched vertices is at most $n/n_0(d,g)$, where $n_0(d,g)$ is the number of vertices in a ball of radius $\lfloor(g-1)/2\rfloor$ around a vertex, for odd values of $g$, and around an edge, for even values of $g$. This result is tight if $n < 2n_0(d,g)$.
Comultiplication Rules for the Double Schur Functions and Cauchy Identities
Authors: Molev A. I.
Published: January 2020

The double Schur functions form a distinguished basis of the ring $\Lambda(x\!\parallel\!a)$ which is a multiparameter generalization of the ring of symmetric functions $\Lambda(x)$. The canonical comultiplication on $\Lambda(x)$ is extended to $\Lambda(x\!\parallel\!a)$ in a natural way so that the double power sums symmetric functions are primitive elements. We calculate the dual Littlewood–Richardson coefficients in two different ways thus providing comultiplication rules for the double Schur functions. We also prove multiparameter analogues of the Cauchy identity. A new family of Schur type functions plays the role of a dual object in the identities. We describe some properties of these dual Schur functions including a combinatorial presentation and an expansion formula in terms of the ordinary Schur functions. The dual Littlewood–Richardson coefficients provide a multiplication rule for the dual Schur functions.
Regular Spanning Subgraphs of Bipartite Graphs of High Minimum Degree
Authors: Csaba Béla
Published: January 2020

Let $G$ be a simple balanced bipartite graph on $2n$ vertices, $\delta = \delta(G)/n$, and $\rho_0={\delta + \sqrt{2 \delta -1} \over 2}$. If $\delta \ge 1/2$ then $G$ has a $\lfloor \rho_0 n \rfloor$-regular spanning subgraph. The statement is nearly tight.
The Linear Complexity of a Graph
Authors: Neel David L. , Orrison Michael E.
Published: January 2020

The linear complexity of a matrix is a measure of the number of additions, subtractions, and scalar multiplications required to multiply that matrix and an arbitrary vector. In this paper, we define the linear complexity of a graph to be the linear complexity of any one of its associated adjacency matrices. We then compute or give upper bounds for the linear complexity of several classes of graphs.
Rainbow $H$-factors
Authors: Yuster Raphael
Published: January 2020

An $H$-factor of a graph $G$ is a spanning subgraph of $G$ whose connected components are isomorphic to $H$. Given a properly edge-colored graph $G$, a rainbow $H$-subgraph of $G$ is an $H$-subgraph of $G$ whose edges have distinct colors. A rainbow $H$-factor is an $H$-factor whose components are rainbow $H$-subgraphs. The following result is proved. If $H$ is any fixed graph with $h$ vertices then every properly edge-colored graph with $hn$ vertices and minimum degree $(1-1/\chi(H))hn+o(n)$ has a rainbow $H$-factor.
On the Limiting Distribution for the Length of the Longest Alternating Sequence in a Random Permutation
Authors: Widom Harold
Published: January 2020

Recently Richard Stanley initiated a study of the distribution of the length as$_n(w)$ of the longest alternating subsequence in a random permutation $w$ from the symmetric group ${\cal S}_n$. Among other things he found an explicit formula for the generating function (on $n$ and $k$) for Pr$\,$(as$_n(w)\le k)$ and conjectured that the distribution, suitably centered and normalized, tended to a Gaussian with variance 8/45. In this note we present a proof of the conjecture based on the generating function.
Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size
Authors: Gould Ronald , Łuczak Tomasz , Schmitt John
Published: January 2020

A graph $G$ is said to be $C_l$-saturated if $G$ contains no cycle of length $l$, but for any edge in the complement of $G$ the graph $G+e$ does contain a cycle of length $l$. The minimum number of edges of a $C_l$-saturated graph was shown by Barefoot et al. to be between $n+c_1{n\over l}$ and $n+c_2{n\over l}$ for some positive constants $c_1$ and $c_2$. This confirmed a conjecture of Bollobás. Here we improve the value of $c_2$ for $l \geq 8$.
A Matrix Representation of Graphs and its Spectrum as a Graph Invariant
Authors: Emms David , Hancock Edwin R. , Severini Simone , Wilson Richard C.
Published: January 2020

We use the line digraph construction to associate an orthogonal matrix with each graph. From this orthogonal matrix, we derive two further matrices. The spectrum of each of these three matrices is considered as a graph invariant. For the first two cases, we compute the spectrum explicitly and show that it is determined by the spectrum of the adjacency matrix of the original graph. We then show by computation that the isomorphism classes of many known families of strongly regular graphs (up to 64 vertices) are characterized by the spectrum of this matrix. We conjecture that this is always the case for strongly regular graphs and we show that the conjecture is not valid for general graphs. We verify that the smallest regular graphs which are not distinguished with our method are on 14 vertices.
Kernels of Directed Graph Laplacians
Authors: Caughman J. S. , Veerman J. J. P.
Published: January 2020

Let $G$ denote a directed graph with adjacency matrix $Q$ and in-degree matrix $D$. We consider the Kirchhoff matrix $L=D-Q$, sometimes referred to as the directed Laplacian. A classical result of Kirchhoff asserts that when $G$ is undirected, the multiplicity of the eigenvalue 0 equals the number of connected components of $G$. This fact has a meaningful generalization to directed graphs, as was recently observed by Chebotarev and Agaev in 2005. Since this result has many important applications in the sciences, we offer an independent and self-contained proof of their theorem, showing in this paper that the algebraic and geometric multiplicities of 0 are equal, and that a graph-theoretic property determines the dimension of this eigenspace – namely, the number of reaches of the directed graph. We also extend their results by deriving a natural basis for the corresponding eigenspace. The results are proved in the general context of stochastic matrices, and apply equally well to directed graphs with non-negative edge weights.
Equitable Matroids
Authors: Mayhew Dillon
Published: January 2020

One way to choose a basis of a matroid at random is to choose an ordering of the ground set uniformly at random and then use the greedy algorithm to find a basis. We investigate the class of matroids having the property that this procedure yields a basis uniformly at random. We show how this class is related to some other naturally-defined families of matroids and consider how it behaves under well-known matroid operations.
A New Statistic on Linear and Circular $r$-Mino Arrangements
Authors: Shattuck Mark A. , Wagner Carl G.
Published: January 2020

We introduce a new statistic on linear and circular $r$-mino arrangements which leads to interesting polynomial generalizations of the $r$-Fibonacci and $r$-Lucas sequences. By studying special values of these polynomials, we derive periodicity and parity theorems for this statistic.
Bounding the Number of Edges in Permutation Graphs
Authors: Keevash Peter , Loh Po-Shen , Sudakov Benny
Published: January 2020

Given an integer $s\geq 0$ and a permutation $\pi \in S_n$, let $\Gamma_{\pi,s}$ be the graph on $n$ vertices $\{1, \ldots, n\}$ where two vertices $i < j$ are adjacent if the permutation flips their order and there are at most $s$ integers $k$, $i < k < j$, such that $\pi=[\ldots j \ldots k \ldots i\ldots]$. In this short paper we determine the maximum number of edges in $\Gamma_{\pi,s}$ for all $s\geq 1$ and characterize all permutations $\pi$ which achieve this maximum. This answers an open question of Adin and Roichman, who studied the case $s=0$. We also consider another (closely related) permutation graph, defined by Adin and Roichman, and obtain asymptotically tight bounds on the maximum number of edges in it.
The Polytope of Degree Partitions
Authors: Bhattacharya Amitava , Sivasubramanian S. , Srinivasan Murali K.
Published: January 2020

The degree partition of a simple graph is its degree sequence rearranged in weakly decreasing order. The polytope of degree partitions (respectively, degree sequences) is the convex hull of degree partitions (respectively, degree sequences) of all simple graphs on the vertex set $[n]$. The polytope of degree sequences has been very well studied. In this paper we study the polytope of degree partitions. We show that adding the inequalities $x_1\geq x_2 \geq \cdots \geq x_n$ to a linear inequality description of the degree sequence polytope yields a linear inequality description of the degree partition polytope and we show that the extreme points of the degree partition polytope are the $2^{n-1}$ threshold partitions (these are precisely those extreme points of the degree sequence polytope that have weakly decreasing coordinates). We also show that the degree partition polytope has $2^{n-2}(2n-3)$ edges and $(n^2 -3n + 12)/2$ facets, for $n\geq 4$. Our main tool is an averaging transformation on real sequences defined by repeatedly averaging over the ascending runs.
Tilings of the Sphere with Right Triangles I: The Asymptotically Right Families
Authors: Dawson Robert J. MacG. , Doyle Blair
Published: January 2020

Sommerville and Davies classified the spherical triangles that can tile the sphere in an edge-to-edge fashion. Relaxing this condition yields other triangles, which tile the sphere but have some tiles intersecting in partial edges. This paper determines which right spherical triangles within certain families can tile the sphere.
$3$-Designs from PGL$(2,q)$
Authors: Cameron P. J. , Omidi G. R. , Tayfeh-Rezaie B.
Published: January 2020

The group PGL$(2,q)$, $q=p^n$, $p$ an odd prime, is $3$-transitive on the projective line and therefore it can be used to construct $3$-designs. In this paper, we determine the sizes of orbits from the action of PGL$(2,q)$ on the $k$-subsets of the projective line when $k$ is not congruent to $0$ and 1 modulo $p$. Consequently, we find all values of $\lambda$ for which there exist $3$-$(q+1,k,\lambda)$ designs admitting PGL$(2,q)$ as automorphism group. In the case $p\equiv 3$ mod 4, the results and some previously known facts are used to classify 3-designs from PSL$(2,p)$ up to isomorphism.
Three-Letter-Pattern Avoiding Permutations and Functional Equations
Authors: Firro Ghassan , Mansour Toufik
Published: January 2020

We present an algorithm for finding a system of recurrence relations for the number of permutations of length $n$ that satisfy a certain set of conditions. A rewriting of these relations automatically gives a system of functional equations satisfied by the multivariate generating function that counts permutations by their length and the indices of the corresponding recurrence relations. We propose an approach to describing such equations. In several interesting cases the algorithm recovers and refines, in a unified way, results on $\tau$-avoiding permutations and permutations containing $\tau$ exactly once, where $\tau$ is any classical, generalized, and distanced pattern of length three.
Permutation Reconstruction from Minors
Authors: Raykova Mariana
Published: January 2020

We consider the problem of permutation reconstruction, which is a variant of graph reconstruction. Given a permutation $p$ of length $n$, we delete $k$ of its entries in each possible way to obtain ${n \choose k}$ subsequences. We renumber the sequences from $1$ to $n-k$ preserving the relative size of the elements to form $(n-k)$-minors. These minors form a multiset $M_k(p)$ with an underlying set $M_k'(p)$. We study the question of when we can reconstruct $p$ from its multiset or its set of minors. We prove there exists an $N_k$ for every $k$ such that any permutation with length at least $N_k$ is reconstructible from its multiset of $(n-k)$-minors. We find the bounds $N_k > k+\log_2 k$ and $N_k < {k^2\over4} + 2k + 4$. For the number $N_k'$, giving the minimal length for permutations to be reconstructible from their sets of $(n-k)$-minors, we have the bound $N_k' > 2k$. We work towards analogous bounds in the case when we restrict ourselves to layered permutations.
Permutations Generated by a Stack of Depth 2 and an Infinite Stack in Series
Authors: Elder Murray
Published: January 2020

We prove that the set of permutations generated by a stack of depth two and an infinite stack in series has a basis (defining set of forbidden patterns) consisting of 20 permutations of length 5, 6, 7 and 8. We prove this via a "canonical" generating algorithm.
Bounding the Partition Function of Spin-Systems
Authors: Galvin David J.
Published: January 2020

With a graph $G=(V,E)$ we associate a collection of non-negative real weights $\bigcup_{v\in V}\{\lambda_{i,v}:1\leq i \leq m\} \cup \bigcup_{uv \in E} \{\lambda_{ij,uv}:1\leq i \leq j \leq m\}.$ We consider the probability distribution on $\{f:V\rightarrow\{1,\ldots,m\}\}$ in which each $f$ occurs with probability proportional to $\prod_{v \in V}\lambda_{f(v),v}\prod_{uv \in E}\lambda_{f(u)f(v),uv}$. Many well-known statistical physics models, including the Ising model with an external field and the hard-core model with non-uniform activities, can be framed as such a distribution. We obtain an upper bound, independent of $G$, for the partition function (the normalizing constant which turns the assignment of weights on $\{f:V\rightarrow\{1,\ldots,m\}\}$ into a probability distribution) in the case when $G$ is a regular bipartite graph. This generalizes a bound obtained by Galvin and Tetali who considered the simpler weight collection $\{\lambda_i:1 \leq i \leq m\} \cup \{\lambda_{ij}:1 \leq i \leq j \leq m\}$ with each $\lambda_{ij}$ either $0$ or $1$ and with each $f$ chosen with probability proportional to $\prod_{v \in V}\lambda_{f(v)}\prod_{uv \in E}\lambda_{f(u)f(v)}$. Our main tools are a generalization to list homomorphisms of a result of Galvin and Tetali on graph homomorphisms and a straightforward second-moment computation.
The $\{4, 5\}$ Isogonal Sponges on the Cubic Lattice
Authors: Gillispie Steven B. , Grünbaum Branko
Published: January 2020

Isogonal polyhedra are those polyhedra having the property of being vertex-transitive. By this we mean that every vertex can be mapped to any other vertex via a symmetry of the whole polyhedron; in a sense, every vertex looks exactly like any other. The Platonic solids are examples, but these are bounded polyhedra and our focus here is on infinite polyhedra. When the polygons of an infinite isogonal polyhedron are all planar and regular, the polyhedra are also known as sponges, pseudopolyhedra, or infinite skew polyhedra. These have been studied over the years, but many have been missed by previous researchers. We first introduce a notation for labeling three-dimensional isogonal polyhedra and then show how this notation can be combinatorially used to find all of the isogonal polyhedra that can be created given a specific vertex star configuration. As an example, we apply our methods to the $\{4, 5\}$ vertex star of five squares aligned along the planes of a cubic lattice and prove that there are exactly 15 such unlabeled sponges and 35 labeled ones. Previous efforts had found only 8 of the 15 shapes.
Weighted Zeta Functions of Graph Coverings
Authors: Sato Iwao
Published: January 2020

We present a decomposition formula for the weighted zeta function of an irregular covering of a graph by its weighted $L$-functions. Moreover, we give a factorization of the weighted zeta function of an (irregular or regular) covering of a graph by equivalence classes of prime, reduced cycles of the base graph. As an application, we discuss the structure of balanced coverings of signed graphs.
From Well-Quasi-Ordered Sets to Better-Quasi-Ordered Sets
Authors: Pouzet Maurice , Sauer Norbert
Published: January 2020

We consider conditions which force a well-quasi-ordered poset (wqo) to be better-quasi-ordered (bqo). In particular we obtain that if a poset $P$ is wqo and the set $S_{\omega}(P)$ of strictly increasing sequences of elements of $P$ is bqo under domination, then $P$ is bqo. As a consequence, we get the same conclusion if $S_{\omega} (P)$ is replaced by ${\cal J}^{\neg \downarrow\hskip -2pt }(P)$, the collection of non-principal ideals of $P$, or by $AM(P)$, the collection of maximal antichains of $P$ ordered by domination. It then follows that an interval order which is wqo is in fact bqo.
On Lengths of Rainbow Cycles
Authors: Alexeev Boris
Published: January 2020

We prove several results regarding edge-colored complete graphs and rainbow cycles, cycles with no color appearing on more than one edge. We settle a question posed by Ball, Pultr and Vojtěchovský by showing that if such a coloring does not contain a rainbow cycle of length $n$, where $n$ is odd, then it also does not contain a rainbow cycle of length $m$ for all $m$ greater than $2n^2$. In addition, we present two examples which demonstrate that a similar result does not hold for even $n$. Finally, we state several open problems in the area.
A Combinatorial Derivation of the PASEP Stationary State
Authors: Brak Richard , Corteel Sylvie , Essam John , Parviainen Robert , Rechnitzer Andrew
Published: January 2020

We give a combinatorial derivation and interpretation of the weights associated with the stationary distribution of the partially asymmetric exclusion process. We define a set of weight equations, which the stationary distribution satisfies. These allow us to find explicit expressions for the stationary distribution and normalisation using both recurrences and path models. To show that the stationary distribution satisfies the weight equations, we construct a Markov chain on a larger set of generalised configurations. A bijection on this new set of configurations allows us to find the stationary distribution of the new chain. We then show that a subset of the generalised configurations is equivalent to the original process and that the stationary distribution on this subset is simply related to that of the original chain. We also provide a direct proof of the validity of the weight equations.
Permutations, Cycles and the Pattern 2–13
Authors: Parviainen Robert
Published: January 2020

We count the number of occurrences of restricted patterns of length 3 in permutations with respect to length and the number of cycles. The main tool is a bijection between permutations in standard cycle form and weighted Motzkin paths.
The Diameter and Laplacian Eigenvalues of Directed Graphs
Authors: Chung Fan
Published: January 2020

For undirected graphs it has been known for some time that one can bound the diameter using the eigenvalues. In this note we give a similar result for the diameter of strongly connected directed graphs $G$, namely $$ D(G) \leq \bigg \lfloor {2\min_x \log (1/\phi(x))\over \log{2\over 2-\lambda}} \bigg\rfloor +1 $$ where $\lambda$ is the first non-trivial eigenvalue of the Laplacian and $\phi$ is the Perron vector of the transition probability matrix of a random walk on $G$.
On the Number of Possible Row and Column Sums of 0,1-Matrices
Authors: Goldstein Daniel , Stong Richard
Published: January 2020

For $n$ a positive integer, we show that the number of of $2n$-tuples of integers that are the row and column sums of some $n\times n$ matrix with entries in $\{0,1\}$ is evenly divisible by $n+1$. This confirms a conjecture of Benton, Snow, and Wallach. We also consider a $q$-analogue for $m\times n$ matrices. We give an efficient recursion formula for this analogue. We prove a divisibility result in this context that implies the $n+1$ divisibility result.
An Addition Theorem on the Cyclic Group ${\Bbb Z}_{p^\alpha q^\beta}$
Authors: Cao Hui-Qin
Published: January 2020

Let $n>1$ be a positive integer and $p$ be the smallest prime divisor of $n$. Let $S$ be a sequence of elements from ${\Bbb Z}_n={\Bbb Z}/n{\Bbb Z}$ of length $n+k$ where $k\geq {n\over p}-1$. If every element of ${\Bbb Z}_n$ appears in $S$ at most $k$ times, we prove that there must be a subsequence of $S$ of length $n$ whose sum is zero when $n$ has only two distinct prime divisors.
The Absence of Efficient Dual Pairs of Spanning Trees in Planar Graphs
Authors: Riley T. R. , Thurston W. P.
Published: January 2020

A spanning tree $T$ in a finite planar connected graph $G$ determines a dual spanning tree $T^*$ in the dual graph $G^*$ such that $T$ and $T^*$ do not intersect. We show that it is not always possible to find $T$ in $G$ such that the diameters of $T$ and $T^*$ are both within a uniform multiplicative constant (independent of $G$) of the diameters of their ambient graphs.
BG-Ranks and 2-Cores
Authors: Chen William Y. C. , Ji Kathy Q. , Wilf Herbert S.
Published: January 2020

We find the number of partitions of $n$ whose BG-rank is $j$, in terms of $pp(n)$, the number of pairs of partitions whose total number of cells is $n$, giving both bijective and generating function proofs. Next we find congruences mod 5 for $pp(n)$, and then we use these to give a new proof of a refined system of congruences for $p(n)$ that was found by Berkovich and Garvan.
Parameter Augmentation for Two Formulas
Authors: Zhang Caihuan
Published: January 2020

In this paper, by using the q-exponential operator technique on the $q$-integral form of the Sears transformation formula and a Gasper $q$-integral formula, we obtain their generalizations.
A Note on Exponents vs Root Heights for Complex Simple Lie Algebras
Authors: Viswanath Sankaran
Published: January 2020

We give an elementary combinatorial proof of a special case of a result due to Bazlov and Ion concerning the Fourier coefficients of the Cherednik kernel. This can be used to give yet another proof of the classical fact that for a complex simple Lie algebra $\mathfrak{ g}$, the partition formed by the exponents of $\mathfrak{ g}$ is dual to that formed by the numbers of positive roots at each height.
A Survey on Packing and Covering Problems in the Hamming Permutation Space
Authors: Quistorff Jörn
Published: January 2020

Consider the symmetric group $S_n$ equipped with the Hamming metric $d_H$. Packing and covering problems in the finite metric space $(S_n,d_H)$ are surveyed, including a combination of both.
Rainbow Connection Number and Connectivity
Authors: Li Xueliang , Liu Sujuan , Chandran L. Sunil , Mathew Rogers , Rajendraprasad Deepak
Published: January 2020

The rainbow connection number, $rc(G)$, of a connected graph $G$ is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that $rc(G)\leq \lceil\frac{n}{2}\rceil$ for any 2-connected graph with at least three vertices. We conjecture that $rc(G)\leq n/\kappa+C$ for a $\kappa$-connected graph $G$ of order $n$, where $C$ is a constant, and prove the conjecture for certain classes of graphs. We also prove that $rc(G)\leq(2+\varepsilon)n/\kappa+23/\varepsilon^2$ for any $\varepsilon>0$.
Sequences of Integers Avoiding 3-term Arithmetic Progressions
Authors: Sharma Arun
Published: January 2020

The optimal length $r(n)$ of a sequence in $[1, n]$ containing no $3$-term arithmetic progression is determined for several new values of $n$ and some results relating to the subadditivity of $r$ are obtained.  We also prove a particular case of a conjecture of Szekeres.
How Many Squares Must a Binary Sequence Contain?
Authors: Fraenkel Aviezri S. , Simpson R. Jamie
Published: January 2020

Let $g(n)$ be the length of a longest binary string containing at most $n$ distinct squares (two identical adjacent substrings). Then $g(0)=3$ (010 is such a string), $g(1)=7$ (0001000) and $g(2)=18$ (010011000111001101). How does the sequence $\{g(n)\}$ behave? We give a complete answer.
The Prism of the Acyclic Orientation Graph is Hamiltonian
Authors: Pruesse Gara , Ruskey Frank
Published: January 2020

Every connected simple graph $G$ has an acyclic orientation. Define a graph ${AO}(G)$ whose vertices are the acyclic orientations of $G$ and whose edges join orientations that differ by reversing the direction of a single edge. It was known previously that ${AO}(G)$ is connected but not necessarily Hamiltonian. However, Squire proved that the square ${AO}(G)^2$ is Hamiltonian. We prove the slightly stronger result that the prism ${AO}(G) \times e$ is Hamiltonian. If $G$ is a mixed graph (some edges directed, but not necessarily all), then ${AO}(G)$ can be defined as before. The graph ${AO}(G)$ is again connected but we give examples showing that the prism is not necessarily Hamiltonian.
On 2-ranks of Steiner triple systems
Authors: Assmus Jr. E. F.
Published: January 2020

Our main result is an existence and uniqueness theorem for Steiner triple systems which associates to every such system a binary code — called the "carrier" — which depends only on the order of the system and its 2-rank. When the Steiner triple system is of 2-rank less than the number of points of the system, the carrier organizes all the information necessary to construct directly all systems of the given order and $2$-rank from Steiner triple systems of a specified smaller order. The carriers are an easily understood, two-parameter family of binary codes related to the Hamming codes. We also discuss Steiner quadruple systems and prove an analogous existence and uniqueness theorem; in this case the binary code (corresponding to the carrier in the triple system case) is the dual of the code obtained from a first-order Reed-Muller code by repeating it a certain specified number of times. Some particularly intriguing possible enumerations and some general open problems are discussed. We also present applications of this coding-theoretic classification to the theory of triple and quadruple systems giving, for example, a direct proof of the fact that all triple systems are derived provided those of full 2-rank are and showing that whenever there are resolvable quadruple systems on $u$ and on $v$ points there is a resolvable quadruple system on $uv$ points. The methods used in both the classification and the applications make it abundantly clear why the number of triple and quadruple systems grows in such a staggering way and why a triple system that extends to a quadruple system has, generally, many such extensions.
Yet Another Distance Regular Graph Related to a Golay Code
Authors: Soicher Leonard H.
Published: January 2020

We describe a new distance-regular, but not distance-transitive, graph. This graph has intersection array $\{110,81,12;1,18,90\}$, and automorphism group $M_{22}\colon 2$.
The Number of Solutions of $X^2=0$ in Triangular Matrices Over $GF(q)$
Authors: Ekhad Shalosh B. , Zeilberger Doron
Published: January 2020

We prove an explicit formula for the number of $n \times n$ upper triangular matrices, over $GF(q)$, whose square is the zero matrix. This formula was recently conjectured by Sasha Kirillov and Anna Melnikov.
On Extremal Graphs With No Long Paths
Authors: Ali Asad Ali , Staton William
Published: January 2020

Connected graphs with minimum degree $\delta$ and at least $2\delta + 1$ vertices have paths with at least $2\delta + 1$ vertices. We provide a characterization of all such graphs which have no longer paths.
Local equivalence of transversals in matroids
Authors: Fon-Der-Flaass D.
Published: January 2020

Given any system of $n$ subsets in a matroid $M$, a transversal of this system is an $n$-tuple of elements of $M$, one from each set, which is independent. Two transversals differing by exactly one element are adjacent, and two transversals connected by a sequence of adjacencies are locally equivalent, the distance between them being the minimum number of adjacencies in such a sequence. We give two sufficient conditions for all transversals of a set system to be locally equivalent. Also we propose a conjecture that the distance between any two locally equivalent transversals can be bounded by a function of $n$ only, and provide an example showing that such function, if it exists, must grow at least exponentially.
Overlapping Pfaffians
Authors: Knuth Donald E.
Published: January 2020

A combinatorial construction proves an identity for the product of the Pfaffian of a skew-symmetric matrix by the Pfaffian of one of its submatrices. Several applications of this identity are followed by a brief history of Pfaffians.
A Short WZ-style Proof of Abel's Identity
Authors: Ekhad Shalosh B. , Majewicz J. E.
Published: January 2020

Using a certification procedure for Abel-type sums, we present a computerized proof of Abel's identity.
Some Natural Bigraded $S_n$-Modules
Authors: Garsia A. M. , Haiman M.
Published: January 2020

We construct for each $\mu\vdash n $ a bigraded $S_n$-module $\mathbf{H}_\mu$ and conjecture that its Frobenius characteristic $C_{\mu}(x;q,t)$ yields the Macdonald coefficients $K_{\lambda\mu}(q,t)$. To be precise, we conjecture that the expansion of $C_{\mu}(x;q,t)$ in terms of the Schur basis yields coefficients $C_{\lambda\mu}(q,t)$ which are related to the $K_{\lambda\mu}(q,t)$ by the identity $C_{\lambda\mu}(q,t)=K_{\lambda\mu}(q,1/t)t^{n(\mu )}$. The validity of this would give a representation theoretical setting for the Macdonald basis $\{ P_\mu(x;q,t)\}_\mu$ and establish the Macdonald conjecture that the $K_{\lambda\mu}(q,t)$ are polynomials with positive integer coefficients. The space $\mathbf{H}_\mu$ is defined as the linear span of derivatives of a certain bihomogeneous polynomial $\Delta_\mu(x,y)$ in the variables $x_1,x_2,\ldots ,x_n$, $y_1,y_2,\ldots ,y_n$. On the validity of our conjecture $\mathbf{H}_\mu$ would necessarily have $n!$ dimension. We refer to the latter assertion as the $n!$-conjecture. Several equivalent forms of this conjecture will be discussed here together with some of their consequences. In particular, we derive that the polynomials $C_{\lambda\mu}(q,t)$ have a number of basic properties in common with the coefficients $\tilde{K}_{\lambda\mu}(q,t)=K_{\lambda\mu}(q,1/t)t^{n(\mu )}$. For instance, we show that $C_{\lambda\mu}(0,t)=\tilde{K}_{\lambda\mu}(0,t)$, $C_{\lambda\mu}(q,0)=\tilde{K}_{\lambda\mu}(q,0)$ and show that on the $n!$ conjecture we must also have the equalities $C_{\lambda\mu}(1,t)=\tilde{K}_{\lambda\mu}(1,t)$ and $C_{\lambda\mu}(q,1)=\tilde{K}_{\lambda\mu}(q,1)$. The conjectured equality $C_{\lambda\mu}(q,t)=K_{\lambda\mu}(q,1/t)t^{n(\mu )}$ will be shown here to hold true when $\lambda$ or $\mu$ is a hook. It has also been shown (see [9]) when $\mu$ is a $2$-row or $2$-column partition and in [18] when $\mu$ is an augmented hook.
Le problème du premier chiffre décimal
Authors: Fuchs Aimé , Letta Giorgio
Published: January 2020

Pour une large classe de parties de N$^*$ (à laquelle appartient notamment l'ensemble qui intervient dans le problème du premier chiffre décimal) on démontre que les densités arithmétiques inférieure et supérieure, ainsi que la densité logarithmique, coïncident avec les "densités conditionnelles" correspondantes, obtenues en conditionnant par rapport à l'ensemble P des nombres premiers.
Treillis et bases des groupes de Coxeter
Authors: Lascoux Alain , Schützenberger Marcel-Paul
Published: January 2020

Finite lattices possess a basis, as well as a cobasis, from which the elements of the lattice can be recovered by sup or inf. We extend this construction to finite ordered sets, and then apply it to Coxeter groups, considered as ordered sets (Bruhat order). This amounts to embedding Coxeter groups into their enveloping lattices. These lattices are distributive in the cases of types An and Bn.
A Basis of Finite and Infinite Sets with Small Representation Function
Authors: Dubickas Artūras
Published: January 2020

Let $A$ be a subset of the set of nonnegative integers $\mathbb{N}\cup\{0\}$, and let $r_A(n)$ be the number of representations of $n\geq 0$ by the sum $a+b$ with $a,b \in A$. Then $\big(\sum_{a \in A}x^a\big)^2=\sum_{n=0}^{\infty} r_A(n)x^n$. We show that an old result of Erdős asserting that there is a basis $A$ of $\mathbb{N}\cup \{0\}$, i.e., $r_A(n) \geq 1$ for $n \geq 0$, whose representation function $r_A(n)$ satisfies  $r_A(n) < (2e+\epsilon)\log n$ for each sufficiently large integer $n$. Towards a polynomial version of the Erdős-Turán conjecture we prove that for each $\epsilon>0$ and each sufficiently large integer $n$ there is a set $A \subseteq \{0,1,\dots,n\}$ such that the square of the corresponding Newman polynomial $f(x):=\sum_{a \in A} x^a$ of degree $n$ has all of its $2n+1$ coefficients in the interval $[1, (1+\epsilon)(4/\pi)(\log n)^2]$. Finally, it is shown that the correct order of growth for $H(f^2)$ of those reciprocal Newman polynomials $f$ of degree $n$ whose squares $f^2$ have all their $2n+1$ coefficients positive is $\sqrt{n}$. More precisely, if the Newman polynomial $f(x)=\sum_{a \in A} x^a$ of degree $n$ is reciprocal, i.e., $A=n-A$, then $A+A=\{0,1,\dots,2n\}$ implies that the coefficient for $x^n$ in $f(x)^2$ is at least $2\sqrt{n}-3$. In the opposite direction, we explicitly construct a reciprocal Newman polynomial $f(x)$ of degree $n$ such that the coefficients of its square $f(x)^2$ all belong to the interval $[1, 2\sqrt{2n}+4]$.
An Eigenvalue Characterization of Antipodal Distance-Regular Graphs
Authors: Fiol M. A.
Published: January 2020

Let $G$ be a regular (connected) graph with $n$ vertices and $d+1$ distinct eigenvalues. As a main result, it is shown that $G$ is an $r$-antipodal distance-regular graph if and only if the distance graph $G_d$ is constituted by disjoint copies of the complete graph $K_r$, with $r$ satisfying an expression in terms of $n$ and the distinct eigenvalues.
Ramanujan's Method in q-Series Congruences
Authors: Andrews George E.
Published: January 2020

We show that the method that was developed by Ramanujan to prove $5|p (5n + 4)$ and $7|p (7n + 5)$ may, in fact, be extended to a wide variety of $q$-series and products including some with free parameters.
A note on major sequences and external activity in trees
Authors: Beissinger Janet S. , Peled Uri N.
Published: January 2020

A bijection is given from major sequences of length $n$ (a variant of parking functions) to trees on $\{0,\ldots,n\}$ that maps a sequence with sum ${{n+1}\choose 2} + k$ to a tree with external activity $k$.
From Recursions to Asymptotics: On Szekeres' Formula for the Number of Partitions
Authors: Canfield E. Rodney
Published: January 2020

We give a new proof of Szekeres' formula for $P(n,k)$, the number of partitions of the integer $n$ having $k$ or fewer parts. Our proof is based on the recursion formula satisfied by $P(n,k)$ and Taylor's formula. We make no use of the Cauchy integral formula or complex variables. The derivation is presented as a step-by-step procedure, to facilitate its applicationin other situations. As corollaries we obtain the main term of the Hardy-Ramanujan formulas for $p(n)=$ the number of unrestricted partitions of $n$ and for $q(n)=$ the number of partitions of $n$ into distinct parts.
Random walks on generating sets for finite groups
Authors: Chung F. R. K. , Graham R. L.
Published: January 2020

We analyze a certain random walk on the cartesian product $G^n$ of a finite group $G$ which is often used for generating random elements from $G$. In particular, we show that the mixing time of the walk is at most $c_r n^2 \log n$ where the constant $c_r$ depends only on the order $r$ of $G$.
Escher's Combinatorial Patterns
Authors: Schattschneider Doris
Published: January 2020

It is a little-known fact that M.C. Escher posed and answered some combinatorial questions about patterns produced in an algorithmic way. We report on his explorations, indicate how close he came to the correct solutions, and pose an analagous problem in 3 dimensions.
Some geometric probability problems involving the Eulerian numbers
Authors: Schmidt Frank , Simion Rodica
Published: January 2020

We present several problems involving geometric probability. Each is related to the division of a simplex or cube by a family of hyperplanes. Both the classical Eulerian numbers and their analogue for the hyperoctahedral group arise in the solutions.
Permutations which are the union of an increasing and a decreasing subsequence
Authors: Atkinson M. D.
Published: January 2020

It is shown that there are ${2n\choose n}-\sum_{m=0}^{n-1}2^{n-m-1}{2m\choose m}$ permutations which are the union of an increasing sequence and a decreasing sequence.
Maximising the Permanent of (0,1)-Matrices and the Number of Extensions of Latin Rectangles
Authors: McKay B. D. , Wanless I. M.
Published: January 2020

Let $k\geq2$, $m\geq5$ and $n=mk$ be integers. By finding bounds for certain rook polynomials, we identify the $k\times n$ Latin rectangles with the most extensions to $(k+1)\times n$ Latin rectangles. Equivalently, we find the $(n-k)$-regular subgraphs of $K_{n,n}$ which have the greatest number of perfect matchings, and the $(0,1)$-matrices with exactly $k$ zeroes in every row and column which maximise the permanent. Without the restriction on $n$ being a multiple of $k$ we solve the above problem (and the corresponding minimisation problem) for $k=2$. We also provide some computational results for small values of $n$ and $k$. Our results partially settle two open problems of Minc and conjectures by Merriell, and Godsil and McKay.
Lattice Tilings by Cubes: Whole, Notched and Extended
Authors: Kolountzakis Mihail
Published: January 2020

We discuss some problems of lattice tiling via Harmonic Analysis methods. We consider lattice tilings of ${\bf R}^d$ by the unit cube in relation to the Minkowski Conjecture (now a theorem of Hajós) and give a new equivalent form of Hajós's theorem. We also consider "notched cubes" (a cube from which a rectangle has been removed from one of the corners) and show that they admit lattice tilings. This has also been been proved by S. Stein by a direct geometric method. Finally, we exhibit a new class of simple shapes that admit lattice tilings, the "extended cubes", which are unions of two axis-aligned rectangles that share a vertex and have intersection of odd codimension. In our approach we consider the Fourier Transform of the indicator function of the tile and try to exhibit a lattice of appropriate volume in its zero-set.
Proof of the Alon-Tarsi Conjecture for $n=2^rp$
Authors: Drisko Arthur A.
Published: January 2020

The Alon-Tarsi conjecture states that for even $n$, the number of even latin squares of order $n$ differs from the number of odd latin squares of order $n$. Zappa found a generalization of this conjecture which makes sense for odd orders. In this note we prove this extended Alon-Tarsi conjecture for prime orders $p$. By results of Drisko and Zappa, this implies that both conjectures are true for any $n$ of the form $2^rp$ with $p$ prime.
New Bounds for Union-free Families of Sets
Authors: Coppersmith Don , Shearer James B.
Published: January 2020

Following Frankl and Füredi we say a family, $F$, of subsets of an $n$-set is weakly union-free if $F$ does not contain four distinct sets $A$, $B$, $C$, $D$ with $A \cup B = C \cup D$. If in addition $A \cup B = A \cup C$ implies $B=C$ we say $F$ is strongly union-free. Let $f(n)$ ($g(n)$) be the maximum size of strongly (weakly) union-free families. In this paper we prove the following new bounds on $f$ and $g$: $$2^{[0.31349+o(1)]n} \leq f(n) \leq 2^{[0.4998+o(1)]n}$$ and $$g(n) \leq 2^{[0.5+o(1)]n}.$$
Counting Simplexes in $R^3$
Authors: Laflamme Claude , Szalkai István
Published: January 2020

A finite set of vectors ${\cal S} \subseteq {R}^n$ is called a simplex iff ${\cal S}$ is linearly dependent but all its proper subsets are independent. This concept arises in particular from stoichiometry. We are interested in this paper in the number of simplexes contained in some ${\cal H} \subseteq R^n$, which we denote by $simp({\cal H})$. This investigation is particularly interesting for ${\cal H}$ spanning $R^n$ and containing no collinear vectors. Our main result shows that for any ${\cal H} \subseteq R^3$ of fixed size not equal to 3, 4 or 7 and such that ${\cal H}$ spans $R^3$ and contains no collinear vectors, $simp({\cal H})$ is minimal if and only if ${\cal H}$ is contained in two planes intersecting in ${\cal H}$, and one of which is of size exactly 3. The minimal configurations for $|{\cal H}|=3,4,7$ are also completely described. The general problem for $R^n$ remains open.
The Number of Elements in the Mutation Class of a Quiver of Type $D_n$
Authors: Buan Aslak Bakke , Torkildsen Hermund André
Published: January 2020

We show that the number of quivers in the mutation class of a quiver of Dynkin type $D_n$ is given by $\sum_{d|n}\phi(n/d){2d\choose d}/(2n)$ for $n \geq 5$. To obtain this formula, we give a correspondence between the quivers in the mutation class and certain rooted trees.
Pfaffian Orientation and Enumeration of Perfect Matchings for some Cartesian Products of Graphs
Authors: Lin Feng-Gen , Zhang Lian-Zhu
Published: January 2020

The importance of Pfaffian orientations stems from the fact that if a graph $G$ is Pfaffian, then the number of perfect matchings of $G$ (as well as other related problems) can be computed in polynomial time. Although there are many equivalent conditions for the existence of a Pfaffian orientation of a graph, this property is not well-characterized. The problem is that no polynomial algorithm is known for checking whether or not a given orientation of a graph is Pfaffian. Similarly, we do not know whether this property of an undirected graph that it has a Pfaffian orientation is in NP. It is well known that the enumeration problem of perfect matchings for general graphs is NP-hard. L. Lovász pointed out that it makes sense not only to seek good upper and lower bounds of the number of perfect matchings for general graphs, but also to seek special classes for which the problem can be solved exactly. For a simple graph $G$ and a cycle $C_n$ with $n$ vertices (or a path $P_n$ with $n$ vertices), we define $C_n$ (or $P_n)\times G$ as the Cartesian product of graphs $C_n$ (or $P_n$) and $G$. In the present paper, we construct Pfaffian orientations of graphs $C_4\times G$, $P_4\times G$ and $P_3\times G$, where $G$ is a non bipartite graph with a unique cycle, and obtain the explicit formulas in terms of eigenvalues of the skew adjacency matrix of $\overrightarrow{G}$ to enumerate their perfect matchings by Pfaffian approach, where $\overrightarrow{G}$ is an arbitrary orientation of $G$.
New Lower Bounds for Some Multicolored Ramsey Numbers
Authors: Robertson Aaron
Published: January 2020

In this article we use two different methods to find new lower bounds for some multicolored Ramsey numbers. In the first part we use the finite field method used by Greenwood and Gleason [GG] to show that $R(5,5,5) \geq 242$ and $R(6,6,6) \geq 692$. In the second part we extend Fan Chung's result in [C] to show that, $$ R(3,3,3,k_1,k_2,\dots,k_r) \geq 3 R(3,3,k_1,k_2,\dots,k_r) + R(k_1,k_2,\dots,k_r) - 3 $$ holds for any natural number $r$ and for any $k_i\geq 3$, $i=1,2,\dots r$. This general result, along with known results, imply the following nontrivial bounds: $R(3,3,3,4) \geq 91$, $R(3,3,3,5) \geq 137$, $R(3,3,3,6) \geq 165$, $R(3,3,3,7) \geq 220$, $R(3,3,3,9) \geq 336$, and $R(3,3,3,11) \geq 422$.
A $[k,k+1]$-Factor Containing A Given Hamiltonian Cycle
Authors: Mao-cheng Cai , Li Yanjun , Kano Mikio
Published: January 2020

We prove the following best possible result. Let $k\ge 2$ be an integer and $G$ be a graph of order $n$ with minimum degree at least $k$. Assume $n \ge 8k-16$ for even $n$ and $n \ge 6k-13$ for odd $n$. If the degree sum of each pair of nonadjacent vertices of $G$ is at least $n$, then for any given Hamiltonian cycle $C$ of $G$, $G$ has a $[k,\,k+1]$-factor containing $C$.
Orthogonal Colorings of Graphs
Authors: Caro Yair , Yuster Raphael
Published: January 2020

An orthogonal coloring of a graph $G$ is a pair $\{c_1,c_2\}$ of proper colorings of $G$, having the property that if two vertices are colored with the same color in $c_1$, then they must have distinct colors in $c_2$. The notion of orthogonal colorings is strongly related to the notion of orthogonal Latin squares. The orthogonal chromatic number of $G$, denoted by $O\chi(G)$, is the minimum possible number of colors used in an orthogonal coloring of $G$. If $G$ has $n$ vertices, then the definition implies that $\left\lceil \sqrt{n} \, \right\rceil \leq O\chi(G) \leq n$. $G$ is said to have an optimal orthogonal coloring if $O\chi(G) = \left\lceil \sqrt{n} \, \right\rceil$. If, in addition, $n$ is an integer square, then we say that $G$ has a perfect orthogonal coloring, since for any two colors $x$ and $y$, there is exactly one vertex colored by $x$ in $c_1$ and by $y$ in $c_2$. The purpose of this paper is to study the parameter $O\chi(G)$ and supply upper bounds to it which depend on other graph parameters such as the maximum degree and the chromatic number. We also study the structure of graphs having an optimal or perfect orthogonal coloring, and show that several classes of graphs always have an optimal or perfect orthogonal coloring. We also consider the strong version of orthogonal colorings, where no vertex may receive the same color in both colorings.
Perfect Factorisations of Bipartite Graphs and Latin Squares Without Proper Subrectangles
Authors: Wanless I. M.
Published: January 2020

A Latin square is pan-Hamiltonian if every pair of rows forms a single cycle. Such squares are related to perfect 1-factorisations of the complete bipartite graph. A square is atomic if every conjugate is pan-Hamiltonian. These squares are indivisible in a strong sense – they have no proper subrectangles. We give some existence results and a catalogue for small orders. In the process we identify all the perfect 1-factorisations of $K_{n,n}$ for $n\leq 9$, and count the Latin squares of order $9$ without proper subsquares.
Coverings, Heat Kernels and Spanning Trees
Authors: Chung Fan , Yau S.-T.
Published: January 2020

We consider a graph $G$ and a covering $\tilde{G}$ of $G$ and we study the relations of their eigenvalues and heat kernels. We evaluate the heat kernel for an infinite $k$-regular tree and we examine the heat kernels for general $k$-regular graphs. In particular, we show that a $k$-regular graph on $n$ vertices has at most $$ (1+o(1)) {{2\log n}\over {kn \log k}} \left( {{ (k-1)^{k-1}}\over {(k^2-2k)^{k/2-1}}}\right)^n $$ spanning trees, which is best possible within a constant factor.