bluuebunny/crossref_metadata_2025 huggingface dataset:
Restricting Supercharacters of the Finite Group of Unipotent Uppertriangular Matrices
Authors: Thiem Nathaniel , Venkateswaran Vidya
Published: January 2020

It is well-known that understanding the representation theory of the finite group of unipotent upper-triangular matrices $U_n$ over a finite field is a wild problem. By instead considering approximately irreducible representations (supercharacters), one obtains a rich combinatorial theory analogous to that of the symmetric group, where we replace partition combinatorics with set-partitions. This paper studies the supercharacter theory of a family of subgroups that interpolate between $U_{n-1}$ and $U_n$. We supply several combinatorial indexing sets for the supercharacters, supercharacter formulas for these indexing sets, and a combinatorial rule for restricting supercharacters from one group to another. A consequence of this analysis is a Pieri-like restriction rule from $U_n$ to $U_{n-1}$ that can be described on set-partitions (analogous to the corresponding symmetric group rule on partitions).
Nilpotent Singer Groups
Authors: Gill Nick
Published: January 2020

Let $N$ be a nilpotent group normal in a group $G$. Suppose that $G$ acts transitively upon the points of a finite non-Desarguesian projective plane ${\cal P}$. We prove that, if ${\cal P}$ has square order, then $N$ must act semi-regularly on ${\cal P}$. In addition we prove that if a finite non-Desarguesian projective plane ${\cal P}$ admits more than one nilpotent group which is regular on the points of ${\cal P}$ then ${\cal P}$ has non-square order and the automorphism group of ${\cal P}$ has odd order.
Parity Versions of 2-Connectedness
Authors: Little C. , Vince A.
Published: January 2020

This paper introduces parity versions of familiar graph theoretic results, in particular results related to 2-connectedness. The even and odd circuit connected graphs are characterized. The realizable, even-realizable, alternating-realizable, dual realizable and dual even-realizable graphs are classified.
Movable $(n_{4})$ Configurations
Authors: Berman Leah Wrenn
Published: January 2020

An $(n_{k})$ configuration is a collection of points and straight lines, usually in the Euclidean plane, so that each point lies on $k$ lines and each line passes through $k$ points; such a configuration will be called symmetric if it possesses non-trivial geometric symmetry. Although examples of symmetric $(n_{3})$ configurations with continuous parameters are known, to this point, all known connected infinite families of $(n_{4})$ configurations with non-trivial geometric symmetry had the property that each set of discrete parameters describing the configuration corresponded to a single $(n_{4})$ configuration. This paper presents several new classes of highly symmetric $(n_{4})$ configurations which have at least one continuous parameter; that is, the configurations are movable.
Matchings Avoiding Partial Patterns
Authors: Chen William Y. C. , Mansour Toufik , Yan Sherry H. F.
Published: January 2020

We show that matchings avoiding a certain partial pattern are counted by the $3$-Catalan numbers. We give a characterization of $12312$-avoiding matchings in terms of restrictions on the corresponding oscillating tableaux. We also find a bijection between matchings avoiding both patterns $12312$ and $121323$ and Schröder paths without peaks at level one, which are counted by the super-Catalan numbers or the little Schröder numbers. A refinement of the super-Catalan numbers is derived by fixing the number of crossings in the matchings. In the sense of Wilf-equivalence, we use the method of generating trees to show that the patterns 12132, 12123, 12321, 12231, 12213 are all equivalent to the pattern $12312$.
Chains, Subwords, and Fillings: Strong Equivalence of Three Definitions of the Bruhat Order
Authors: Zara Catalin
Published: January 2020

Let $S_n$ be the group of permutations of $[n]=\{1,\ldots,n\}$. The Bruhat order on $S_n$ is a partial order relation, for which there are several equivalent definitions. Three well-known conditions are based on ascending chains, subwords, and comparison of matrices, respectively. We express the last using fillings of tableaux, and prove that the three equivalent conditions are satisfied in the same number of ways.
On an Identity for the Cycle Indices of Rooted Tree Automorphism Groups
Authors: Wagner Stephan G.
Published: January 2020

This note deals with a formula due to G. Labelle for the summed cycle indices of all rooted trees, which resembles the well-known formula for the cycle index of the symmetric group in some way. An elementary proof is provided as well as some immediate corollaries and applications, in particular a new application to the enumeration of $k$-decomposable trees. A tree is called $k$-decomposable in this context if it has a spanning forest whose components are all of size $k$.
An Ehrhart Series Formula For Reflexive Polytopes
Authors: Braun Benjamin
Published: January 2020

It is well known that for $P$ and $Q$ lattice polytopes, the Ehrhart polynomial of $P\times Q$ satisfies $L_{P\times Q}(t)=L_P(t)L_Q(t)$. We show that there is a similar multiplicative relationship between the Ehrhart series for $P$, for $Q$, and for the free sum $P\oplus Q$ that holds when $P$ is reflexive and $Q$ contains $0$ in its interior.
$h$-Vectors of Small Matroid Complexes
Authors: De Loera Jesús A. , Kemper Yvonne , Klee Steven
Published: January 2020

Stanley conjectured in 1977 that the $h$-vector of a matroid simplicial complex is a pure $O$-sequence.  We give simple constructive proofs that the conjecture is true for matroids of rank less than or equal to 3, and corank 2. We used computers to verify that Stanley's conjecture holds for all matroids on at most nine elements.
Domination Reliability
Authors: Dohmen Klaus , Tittmann Peter
Published: January 2020

In this paper, we propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulæ for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard.
Pandiagonal Sudokus
Authors: Klotz Walter , Sander Torsten
Published: January 2020

It is shown that a pandiagonal $n^2\times n^2$-Sudoku exists if and only if $n \equiv \pm 1~($mod$~6)$. Also for these $n$ the existence of row-cyclic, pandiagonal $n^2\times n^2$-Sudokus is conjectured and confirmed for $n=5$ and $n=7$.
Generating Trees and Pattern Avoidance in Alternating Permutations
Authors: Lewis Joel Brewster
Published: January 2020

We extend earlier work of the same author to enumerate alternating permutations avoiding the permutation pattern $2143$.  We use a generating tree approach to construct a recursive bijection between the set $A_{2n}(2143)$ of alternating permutations of length $2n$ avoiding $2143$ and the set of standard Young tableaux of shape $\langle n, n, n\rangle$, and between the set $A_{2n + 1}(2143)$ of alternating permutations of length $2n + 1$ avoiding $2143$ and the set of shifted standard Young tableaux of shape $\langle n + 2, n + 1, n\rangle$.  We also give a number of conjectures and open questions on pattern avoidance in alternating permutations and generalizations thereof.
A Note on Random $k$-SAT for Moderately Growing $k$
Authors: Liu Jun , Gao Zongsheng , Xu Ke
Published: January 2020

Consider a random instance $I$ of $k$-SAT with $n$ variables and $m$ clauses. Suppose that $\theta$, $c>0$ are any fixed real numbers. Let $k=k(n)\geq \big(\frac{1}{2}+\theta\big)\log_{2}n$. We prove that \begin{align}\nonumber\lim_{n\rightarrow\infty}Pr(I\ \mbox{is satifiable})=\left\{\begin{array}{cc}1&m\leq\big(1-\frac{c}{\sqrt{n}}\big)2^{k}n\ln 2 \\0&m\geq\big(1+\frac{c}{\sqrt{n}}\big)2^{k}n\ln 2. \\\end{array}\right.\end{align}
Counting distinct zeros of the Riemann zeta-function
Authors: Farmer David W.
Published: January 2020

Bounds on the number of simple zeros of the derivatives of a function are used to give bounds on the number of distinct zeros of the function.
Pebblings
Authors: Eriksson Henrik
Published: January 2020

The analysis of chessboard pebbling by Fan Chung, Ron Graham, John Morrison and Andrew Odlyzko is strengthened and generalized, first to higher dimension and then to arbitrary posets.
Algebraic Matching Theory
Authors: Godsil C. D.
Published: January 2020

The number of vertices missed by a maximum matching in a graph $G$ is the multiplicity of zero as a root of the matchings polynomial $\mu(G,x)$ of $G$, and hence many results in matching theory can be expressed in terms of this multiplicity. Thus, if $\mathrm{mult}(\theta,G)$ denotes the multiplicity of $\theta$ as a zero of $\mu(G,x)$, then Gallai's lemma is equivalent to the assertion that if $\mathrm{mult}(\theta,G\setminus u) < \mathrm{mult}(\theta,G)$ for each vertex $u$ of $G$, then $\mathrm{mult}(\theta,G)=1$. This paper extends a number of results in matching theory to results concerning $\mathrm{mult}(\theta,G)$, where $\theta$ is not necessarily zero. If $P$ is a path in $G$ then $G\setminus P$ denotes the graph got by deleting the vertices of $P$ from $G$. We prove that $\mathrm{mult}(\theta,G\setminus P)\ge\mathrm{mult}(\theta,G)-1$, and we say $P$ is $\theta$-essential when equality holds. We show that if, all paths in $G$ are $\theta$-essential, then $\mathrm{mult}(\theta,G)=1$. We define $G$ to be $\theta$-critical if all vertices in $G$ are $\theta$-essential and $\mathrm{mult}(\theta,G)=1$. We prove that if $\mathrm{mult}(\theta,G)=k$ then there is an induced subgraph $H$ with exactly $k$ $\theta$-critical components, and the vertices in $G\setminus H$ are covered by $k$ disjoint paths.
Some New Optimum Golomb Rectangles
Authors: Shearer James B.
Published: January 2020

We give some new optimum Golomb rectangles found by computer search.
Bijective proofs of the hook formulas for the number of standard Young tableaux, ordinary and shifted
Authors: Krattenthaler C.
Published: January 2020

Bijective proofs of the hook formulas for the number of ordinary standard Young tableaux and for the number of shifted standard Young tableaux are given. They are formulated in a uniform manner, and in fact prove $q$-analogues of the ordinary and shifted hook formulas. The proofs proceed by combining the ordinary, respectively shifted, Hillman–Grassl algorithm and Stanley's $(P,\omega)$-partition theorem with the involution principle of Garsia and Milne.
On the shadow of squashed families of $k$-sets
Authors: Maire Frédéric
Published: January 2020

The shadow of a collection ${\cal A}$ of $k$-sets is defined as the collection of the $(k-1)$-sets which are contained in at least one $k$-set of ${\cal A}$. Given $|{\cal A}|$, the size of the shadow is minimum when ${\cal A}$ is the family of the first $k$-sets in squashed order (by definition, a $k$-set $A$ is smaller than a $k$-set $B$ in the squashed order if the largest element of the symmetric difference of $A$ and $B$ is in $B$). We give a tight upper bound and an asymptotic formula for the size of the shadow of squashed families of $k$-sets.
The Structure of Locally Finite Two-Connected Graphs
Authors: Droms Carl , Servatius Brigitte , Servatius Herman
Published: January 2020

We expand on Tutte's theory of $3$-blocks for $2$-connected graphs, generalizing it to apply to infinite, locally finite graphs, and giving necessary and sufficient conditions for a labeled tree to be the $3$-block tree of a $2$-connected graph.
Matrices connected with Brauer's centralizer algebras
Authors: McKerihan Mark D.
Published: January 2020

In a 1989 paper, Hanlon and Wales showed that the algebra structure of the Brauer Centralizer Algebra $A_f^{(x)}$ is completely determined by the ranks of certain combinatorially defined square matrices $Z^{\lambda / \mu}$, whose entries are polynomials in the parameter $x$. We consider a set of matrices $M^{\lambda / \mu}$ found by Jockusch that have a similar combinatorial description. These new matrices can be obtained from the original matrices by extracting the terms that are of "highest degree" in a certain sense. Furthermore, the $M^{\lambda / \mu}$ have analogues ${\cal M}^{\lambda / \mu}$ that play the same role that the $Z^{\lambda / \mu}$ play in $A_f^{(x)}$, for another algebra that arises naturally in this context. We find very simple formulas for the determinants of the matrices $M^{\lambda/\mu}$ and ${\cal M}^{\lambda / \mu}$, which prove Jockusch's original conjecture that $\det M^{\lambda / \mu}$ has only integer roots. We define a Jeu de Taquin algorithm for standard matchings, and compare this algorithm to the usual Jeu de Taquin algorithm defined by Schützenberger for standard tableaux. The formulas for the determinants of $M^{\lambda/\mu}$ and ${\cal M}^{\lambda / \mu}$ have elegant statements in terms of this new Jeu de Taquin algorithm.
Priority Queues and Multisets
Authors: Atkinson M. D. , Linton S. A. , Walker L. A.
Published: January 2020

A priority queue, a container data structure equipped with the operations insert and delete-minimum, can re-order its input in various ways, depending both on the input and on the sequence of operations used. If a given input $\sigma$ can produce a particular output $\tau$ then $(\sigma,\tau)$ is said to be an allowable pair. It is shown that allowable pairs on a fixed multiset are in one-to-one correspondence with certain k-way trees and, consequently, the allowable pairs can be enumerated. Algorithms are presented for determining the number of allowable pairs with a fixed input component, or with a fixed output component. Finally, generating functions are used to study the maximum number of output components with a fixed input component, and a symmetry result is derived.
The distribution of descents and length in a Coxeter group
Authors: Reiner Victor
Published: January 2020

We give a method for computing the $q$-Eulerian distribution $$ W(t,q)=\sum_{w \in W} t^{{\rm des}(w)} q^{l(w)} $$ as a rational function in $t$ and $q$, where $(W,S)$ is an arbitrary Coxeter system, $l(w)$ is the length function in $W$, and ${\rm des}(w)$ is the number of simple reflections $s \in S$ for which $l(ws) < l(w)$. Using this we compute generating functions encompassing the $q$-Eulerian distributions of the classical infinite families of finite and affine Weyl groups.
Spectral Saturation: Inverting the Spectral Turán Theorem
Authors: Nikiforov Vladimir
Published: January 2020

Let $\mu\left( G\right) $ be the largest eigenvalue of a graph $G$ and $T_{r}\left( n\right) $ be the $r$-partite Turán graph of order $n.$We prove that if $G$ is a graph of order $n$ with $\mu\left( G\right)>\mu\left( T_{r}\left( n\right) \right)$, then $G$ contains various large supergraphs of the complete graph of order $r+1,$ e.g., the complete $r$-partite graph with all parts of size $\log n$ with an edge added to the first part.We also give corresponding stability results.
The Independence Number of Dense Graphs with Large Odd Girth
Authors: Shearer James B.
Published: January 2020

Let $G$ be a graph with $n$ vertices and odd girth $2k+3$. Let the degree of a vertex $v$ of $G$ be $d_1 (v)$. Let $\alpha (G)$ be the independence number of $G$. Then we show $\alpha (G) \geq 2^{-\left({{k-1}\over {k}}\right)} \left[ \displaystyle{\sum_{v\in G}} d_1 (v)^{{{1}\over {k-1}}} \right]^{(k-1)/k}$. This improves and simplifies results proven by Denley.
Latin Squares of Order 10
Authors: McKay Brendan D. , Rogoyski Eric
Published: January 2020

We describe two independent computations of the number of Latin squares of order 10. We also give counts of Latin rectangles with up to 10 columns, and estimates of the number of Latin squares of orders up to 15.
Problems in Algebraic Combinatorics
Authors: Godsil C. D.
Published: January 2020

This is a list of open problems, mainly in graph theory and all with an algebraic flavour. Except for 6.1, 7.1 and 12.2 they are either folklore, or are stolen from other people.
Maximum subsets of (0,1] with no solutions to x+y = kz
Authors: Chung Fan R. K. , Goldwasser John L.
Published: January 2020

If $k$ is a positive real number, we say that a set $S$ of real numbers is $k$-sum-free if there do not exist $x,y,z$ in $S$ such that $x + y = kz$. For $k$ greater than or equal to 4 we find the essentially unique measurable $k$-sum-free subset of $(0,1]$ of maximum size.
On a Class of Constant Weight Codes
Authors: Caragiu Mihai
Published: January 2020

For any odd prime power $q$ we first construct a certain non-linear binary code $C(q,2)$ having $(q^2-q)/2$ codewords of length $q$ and weight $(q-1)/2$ each, for which the Hamming distance between any two distinct codewords is in the range $[q/2-3\sqrt q/2,\ q/2+3\sqrt q/2]$ that is, 'almost constant'. Moreover, we prove that $C(q,2)$ is distance-invariant. Several variations and improvements on this theme are then pursued. Thus, we produce other classes of binary codes $C(q,n)$, $n\geq 3$, of length $q$ that have 'almost constant' weights and distances, and which, for fixed $n$ and big $q$, have asymptotically $q^n/n$ codewords. Then we prove the possibility of extending our codes by adding the complements of their codewords. Also, by using results on Artin $L-$series, it is shown that the distribution ofthe $0$'s and $1$'s in the codewords we constructed is quasi-random. Our construction uses character sums associated with the quadratic character $\chi$ of $F_{q^n}$ in which the range of summation is $F_q$. Relations with the duals of the double error correcting BCH codes and the duals of the Melas codes are also discussed.
A Symmetric Functions Approach to Stockhausen's Problem
Authors: Yen Lily
Published: January 2020

We consider problems in sequence enumeration suggested by Stockhausen's problem, and derive a generating series for the number of sequences of length $k$ on $n$ available symbols such that adjacent symbols are distinct, the terminal symbol occurs exactly $r$ times, and all other symbols occur at most $r-1$ times. The analysis makes extensive use of techniques from the theory of symmetric functions. Each algebraic step is examined to obtain information for formulating a direct combinatorial construction for such sequences.
A Short Proof of the Rook Reciprocity Theorem
Authors: Chow Timothy
Published: January 2020

Rook numbers of complementary boards are related by a reciprocity law. A complicated formula for this law has been known for about fifty years, but recently Gessel and the present author independently obtained a much more elegant formula, as a corollary of more general reciprocity theorems. Here, following a suggestion of Goldman, we provide a direct combinatorial proof of this new formula.
Faster and Faster Convergent Series for $\zeta(3)$
Authors: Amdeberhan Tewodros
Published: January 2020

Using WZ pairs we present accelerated series for computing $\zeta(3)$.
For Which Graphs Does Every Edge Belong to Exactly Two Chordless Cycles?
Authors: Peled Uri N. , Wu Julin
Published: January 2020

A graph is 2-cycled if each edge is contained in exactly two of its chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices. The concept of balance of a $\{0,+1,-1\}$-matrix or a signed bipartite graph has been studied by Truemper and by Conforti et al. The concept of $\alpha$-balance is a generalization introduced by Truemper. Truemper exhibits a family ${\cal F}$ of planar graphs such that a graph $G$ can be signed to be $\alpha$-balanced if and only if each induced subgraph of $G$ in ${\cal F}$ can. We show here that the graphs in ${\cal F}$ are exactly the 2-connected 2-cycled graphs.
Gray Codes for A-Free Strings
Authors: Squire Matthew B.
Published: January 2020

For any $q \geq 2$, let $\Sigma_{q}=\{0,\ldots,q\!-\!1\}$, and fix a string $A$ over $\Sigma_{q}$. The $A$-free strings of length $n$ are the strings in $\Sigma_{q}^n$ which do not contain $A$ as a contiguous substring. In this paper, we investigate the possibility of listing the $A$-free strings of length $n$ so that successive strings differ in only one position, and by $\pm 1$ in that position. Such a listing is a Gray code for the $A$-free strings of length $n$. We identify those $q$ and $A$ such that, for infinitely many $n \geq 0$, a Gray code for the $A$-free strings of length $n$ is prohibited by a parity problem. Our parity argument uses techniques similar to those of Guibas and Odlyzko (Journal of Combinatorial Theory A 30 (1981) pp. 183–208) who enumerated the $A$-free strings of length $n$. When $q$ is even, we also give the complementary positive result: for those $A$ for which an infinite number of parity problems do not exist, we construct a Gray code for the $A$-free strings of length $n$ for all $n \geq 0$.
Symmetry Breaking in Graphs
Authors: Albertson Michael O. , Collins Karen L.
Published: January 2020

A labeling of the vertices of a graph G, $\phi :V(G) \rightarrow \{1,\ldots,r\}$, is said to be $r$-distinguishing provided no automorphism of the graph preserves all of the vertex labels. The distinguishing number of a graph G, denoted by $D(G)$, is the minimum $r$ such that $G$ has an $r$-distinguishing labeling. The distinguishing number of the complete graph on $t$ vertices is $t$. In contrast, we prove (i) given any group $\Gamma$, there is a graph $G$ such that $Aut(G) \cong \Gamma$ and $D(G)= 2$; (ii) $D(G) = O(log(|Aut(G)|))$; (iii) if $Aut(G)$ is abelian, then $D(G) \leq 2$; (iv) if $Aut(G)$ is dihedral, then $D(G) \leq 3$; and (v) If $Aut(G) \cong S_4$, then either $D(G) = 2$ or $D(G) = 4$. Mathematics Subject Classification 05C,20B,20F,68R
Balanced Gray Codes
Authors: Bhat Girish S. , Savage Carla D.
Published: January 2020

It is shown that balanced $n$-bit Gray codes can be constructed for all positive integers $n$. A balanced Gray code is one in which the bit changes are distributed as equally as possible among the bit positions. The strategy used is to prove the existence of a certain subsequence which will allow successful use of the construction proposed by Robinson and Cohn in 1981. Although Wagner and West proved in 1991 that balanced Gray code schemes exist when $n$ is a power of 2, the question for general $n$ has remained open since 1980 when it first attracted attention.
Optimal Betti Numbers of Forest Ideals
Authors: Goff Michael
Published: January 2020

We prove a tight lower bound on the algebraic Betti numbers of tree and forest ideals and an upper bound on certain graded Betti numbers of squarefree monomial ideals.
Flag-symmetric and Locally Rank-symmetric Partially Ordered Sets
Authors: Stanley Richard P.
Published: January 2020

For every finite graded poset $P$ with $\hat{0}$ and $\hat{1}$ we associate a certain formal power series $F_P(x) = F_P(x_1,x_2,\dots)$ which encodes the flag $f$-vector (or flag $h$-vector) of $P$. A relative version $F_{P/\Gamma}$ is also defined, where $\Gamma$ is a subcomplex of the order complex of $P$. We are interested in the situation where $F_P$ or $F_{P/\Gamma}$ is a symmetric function of $x_1,x_2,\dots$. When $F_P$ or $F_{P/\Gamma}$ is symmetric we consider its expansion in terms of various symmetric function bases, especially the Schur functions. For a class of lattices called $q$-primary lattices the Schur function coefficients are just values of Kostka polynomials at the prime power $q$, thus giving in effect a simple new definition of Kostka polynomials in terms of symmetric functions. We extend the theory of lexicographically shellable posets to the relative case in order to show that some examples $(P,\Gamma)$ are relative Cohen-Macaulay complexes. Some connections with the representation theory of the symmetric group and its Hecke algebra are also discussed.
A Bijective Proof of the Hook-content Formula
Authors: Krattenthaler Christian
Published: January 2020

A bijective proof of the product formula for the principal specialization of super Schur functions (also called hook Schur functions) is given using the combinatorial description of super Schur functions in terms of certain tableaux due to Berele and Regev. Our bijective proof is based on the Hillman–Grassl algorithm and a modified version of Schützenberger's jeu de taquin. We then explore the relationship between our modified jeu de taquin and a modified jeu de taquin by Goulden and Greene. We define a common extension and prove an invariance property for it, thus discovering that both modified jeu de taquins are, though different, equivalent.
Grammaire de Ramanujan et Arbres de Cayley
Authors: Dumont Dominique , Ramamonjisoa Armand
Published: January 2020

We study three sequences of polynomials defined as successive derivatives with respect to a differential operator associated with a grammar (one of these sequences was originally introduced by Ramanujan). Combinatorial interpretations for these polynomials are found in terms of rooted trees and graphs of mappings from $[n]$ to $[n]$.
A High-tech Proof of the Mills-Robbins-Rumsey Determinant Formula
Authors: Wilf Herbert S. , Petkovsek Marko
Published: January 2020

We give a computer generated proof of the formula of the title, based on Zeilberger's algorithm and a method of George Andrews.
Colored partitions and a Generalization of the Braid Arrangement
Authors: Welker Volkmar
Published: January 2020

We study the topology and combinatorics of an arrangement of hyperplanes in ${\bf C}^n$ that generalizes the classical braid arrangement. The arrangement plays in important role in the work of Schechtman and Varchenko on Lie algebra homology, where it appears in a generic fiber of a projection of the braid arrangement. The study of the intersection lattice of the arrangement leads to the definition of lattices of colored partitions. A detailed combinatorial analysis then provides algebro-geometric and topological properties of the complement of the arrangement. Using results on the character of $S_n$ on the cohomology of these arrangements we are able to deduce the rational cohomology of certain spaces of polynomials in the complement of the standard discriminant that have no root in the first $s$ integers.
Topological Circles and Euler Tours in Locally Finite Graphs
Authors: Georgakopoulos Agelos
Published: January 2020

We obtain three results concerning topological paths ands circles in the end compactification $|G|$ of a locally finite connected graph $G$. Confirming a conjecture of Diestel we show that through every edge set $E\in {\cal C}$ there is a topological Euler tour, a continuous map from the circle $S^1$ to the end compactification $|G|$ of $G$ that traverses every edge in $E$ exactly once and traverses no other edge. Second, we show that for every sequence $(\tau_i)_{i\in \Bbb N}$ of topological $x$–$y$ paths in $|G|$ there is a topological $x$–$y$ path in $|G|$ all of whose edges lie eventually in every member of some fixed subsequence of $(\tau_i)$. It is pointed out that this simple fact has several applications some of which reach out of the realm of $|G|$. Third, we show that every set of edges not containing a finite odd cut of $G$ extends to an element of $\cal C$.
A $\beta$ Invariant for Greedoids and Antimatroids
Authors: Gordon Gary
Published: January 2020

We extend Crapo's $\beta $ invariant from matroids to greedoids, concentrating especially on antimatroids. Several familiar expansions for $\beta (G)$ have greedoid analogs. We give combinatorial interpretations for $\beta (G)$ for simplicial shelling antimatroids associated with chordal graphs. When $G$ is this antimatroid and $b(G)$ is the number of blocks of the chordal graph $G$, we prove $\beta (G)=1-b(G)$.
A Plethysm Formula for $p_\mu(\underline{x}) \circ h_\lambda(\underline{x})$
Authors: Doran IV William F.
Published: January 2020

This paper gives a new formula for the plethysm of power-sum symmetric functions and complete symmetric functions. The form of the main result is that for $\mu \vdash b$ and $\lambda \vdash a$ with length $t$, then $$p_\mu(\underline{x}) \circ h_\lambda(\underline{x}) = \sum_T \underline{\omega}^{{\rm maj}_{\mu^t} (T)} s_{{\rm sh}(T)}(\underline{x}) $$ where the sum is over semistandard tableaux of weight $\lambda_1^b \lambda_2^b \dots \lambda_t^b$ and $\underline{\omega}^{{\rm maj}_{\mu^t} (T)}$ is a root of unity which depends on $\mu$, $t$, and $T$.
Threshold Functions for the Bipartite Turán Property
Authors: Godbole Anant P. , Lamorte Ben , Sandquist Erik Jonathan
Published: January 2020

Let $G_2(n)$ denote a bipartite graph with $n$ vertices in each color class, and let $z(n,t)$ be the bipartite Turán number, representing the maximum possible number of edges in $G_2(n)$ if it does not contain a copy of the complete bipartite subgraph $K(t,t)$. It is then clear that $\zeta(n,t)=n^2-z(n,t)$ denotes the minimum number of zeros in an $n\times n$ zero-one matrix that does not contain a $t\times t$ submatrix consisting of all ones. We are interested in the behaviour of $z(n,t)$ when both $t$ and $n$ go to infinity. The case $2\le t\ll n^{1/5}$ has been treated elsewhere; here we use a different method to consider the overlapping case $\log n\ll t\ll n^{1/3}$. Fill an $n \times n$ matrix randomly with $z$ ones and $\zeta=n^2-z$ zeros. Then, we prove that the asymptotic probability that there are no $t \times t$ submatrices with all ones is zero or one, according as $z\ge(t/ne)^{2/t}\exp\{a_n/t^2\}$ or $z\le(t/ne)^{2/t}\exp\{(\log t-b_n)/t^2\}$, where $a_n$ tends to infinity at a specified rate, and $b_n\to\infty$ is arbitrary. The proof employs the extended Janson exponential inequalities.
Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees
Authors: Schaeffer Gilles
Published: January 2020

Abstract: We give a bijection between Eulerian planar maps with prescribed vertex degrees, and some plane trees that we call balanced Eulerian trees. To enumerate the latter, we introduce conjugation classes of planted plane trees. In particular, the result answers a question of Bender and Canfield and allows uniform random generation of Eulerian planar maps with restricted vertex degrees. Using a well known correspondence between 4-regular planar maps with n vertices and planar maps with n edges we obtain an algorithm to generate uniformly such maps with complexity O(n). Our bijection is also refined to give a combinatorial interpretation of a parameterization of Arquès of the generating function of planar maps with respect to vertices and faces.
Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra
Authors: Fiol M. A.
Published: January 2020

Given a vertex $u\in V$ of a graph $G=(V,E)$, the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the so-called $u$-local spectrum of $G$. These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for the distance-regular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter. Here some new applications of both, the proper and adjacency polynomials, are derived, such as bounds for the radius of $G$ and the weight $k$-excess of a vertex. Given the integers $k,\mu\geq 0$, let $G_k^\mu(u)$ denote the set of vertices which are at distance at least $k$ from a vertex $u\in V$, and there exist exactly $\mu$ (shortest) $k$-paths from $u$ to each of such vertices. As a main result, an upper bound for the cardinality of $G_k^\mu(u)$ is derived, showing that $|G_k^\mu(u)|$ decreases at least as $O(\mu^{-2})$, and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues, we reobtain a result of Van Dam about 3-class association schemes, and prove some conjectures of Haemers and Van Dam, about the number of vertices at distance three from every vertex of a regular graph with four distinct eigenvalues —setting $k=2$ and $\mu=0$— and, more generally, the number of non-adjacent vertices to every vertex $u\in V$, which have $\mu$ common neighbours with it.
Determinant identities and a generalization of the number of totally symmetric self-complementary plane partitions
Authors: Krattenthaler C.
Published: January 2020

We prove a constant term conjecture of Robbins and Zeilberger (J. Combin. Theory Ser. A 66 (1994), 17–27), by translating the problem into a determinant evaluation problem and evaluating the determinant. This determinant generalizes the determinant that gives the number of all totally symmetric self-complementary plane partitions contained in a $(2n)\times(2n)\times(2n)$ box and that was used by Andrews (J. Combin. Theory Ser. A 66 (1994), 28–39) and Andrews and Burge (Pacific J. Math. 158 (1993), 1–14) to compute this number explicitly. The evaluation of the generalized determinant is independent of Andrews and Burge's computations, and therefore in particular constitutes a new solution to this famous enumeration problem. We also evaluate a related determinant, thus generalizing another determinant identity of Andrews and Burge (loc. cit.). By translating some of our determinant identities into constant term identities, we obtain several new constant term identities.
Evaluations of $k$-fold Euler/Zagier sums: a compendium of results for arbitrary $k$
Authors: Borwein J. M. , Bradley D. M. , Broadhurst D. J.
Published: January 2020

Euler sums (also called Zagier sums) occur within the context of knot theory and quantum field theory. There are various conjectures related to these sums whose incompletion is a sign that both the mathematics and physics communities do not yet completely understand the field. Here, we assemble results for Euler/Zagier sums (also known as multidimensional zeta/harmonic sums) of arbitrary depth, including sign alternations. Many of our results were obtained empirically and are apparently new. By carefully compiling and examining a huge data base of high precision numerical evaluations, we can claim with some confidence that certain classes of results are exhaustive. While many proofs are lacking, we have sketched derivations of all results that have so far been proved.
Upper Bounds on the Order of Cages
Authors: Lazebnik F. , Ustimenko V. A. , Woldar A. J.
Published: January 2020

Let $ { k\ge 2}$ and $ {g\ge3}$ be integers. A $ {(k,g)}$-graph is a $ {k}$-regular graph with girth (length of a smallest cycle) exactly $ {g}$. A $ {(k,g)}$-cage is a $ {(k,g)}$-graph of minimum order. Let $ {v(k,g)}$ be the order of a $ {(k,g)}$-cage. The problem of determining $ {v(k,g)}$ is unsolved for most pairs $ {(k,g)}$ and is extremely hard in the general case. It is easy to establish the following lower bounds for $ {v(k,g)}$: $ {v(k,g)\ge} {{k(k-1)^{(g-1)/2}-2}\over {k-2}}$ for $ {g}$ odd, and $ {v(k,g)\ge} { {2(k-1)^{g/2}-2}\over {k-2}}$ for $ {g}$ even. The best known upper bounds are roughly the squares of the lower bounds. In this paper we establish general upper bounds on $ {v(k,g)}$ which are roughly the 3/2 power of the lower bounds, and we provide explicit constructions for such $ {(k,g)}$-graphs.
Rate of Convergence of the Short Cycle Distribution in Random Regular Graphs Generated by Pegging
Authors: Gao Pu , Wormald Nicholas
Published: January 2020

The pegging algorithm is a method of generating large random regular graphs beginning with small ones. The $\epsilon$-mixing time of the distribution of short cycle counts of these random regular graphs is the time at which the distribution reaches and maintains total variation distance at most $\epsilon$ from its limiting distribution. We show that this $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound $O(\epsilon^{-1})$ proved recently by the authors is essentially tight.
When can the sum of $(1/p)$th of the binomial coefficients have closed form?
Authors: Petkovšek Marko , Wilf Herbert S.
Published: January 2020

We find all nonnegative integer $r,s,p$ for which the sum $\sum_{k=rn}^{sn}{pn\choose k}$ has closed form.
A Binomial Coefficient Identity Associated to a Conjecture of Beukers
Authors: Ahlgren Scott , Ekhad Shalosh B. , Ono Ken , Zeilberger Doron
Published: January 2020

Using the WZ method, a binomial coefficient identity is proved. This identity is noteworthy since its truth is known to imply a conjecture of Beukers.
Asymptotics of the Number of $k$-words With An $\ell$-descent
Authors: Regev Amitai
Published: January 2020

The number of words $w = w_1\cdots w_n$, $1 \leq w_i \leq k$, for which there are $1 \leq i_1 < \cdots < i_{\ell} \leq n$ and $w_{i_1} > \cdots > w_{i_{\ell}}$, is given, by the Schensted-Knuth correspondence, in terms of standard and semi-standard Young tableaux. When $n \to \infty$, the asymptotics of the number of such words is calculated.
Minimal Cycle Bases of Outerplanar Graphs
Authors: Leydold Josef , Stadler Peter F.
Published: January 2020

2-connected outerplanar graphs have a unique minimal cycle basis with length $2\vert E\vert-\vert V\vert$. They are the only Hamiltonian graphs with a cycle basis of this length.
Affine Weyl Groups as Infinite Permutations
Authors: Eriksson Henrik , Eriksson Kimmo
Published: January 2020

We present a unified theory for permutation models of all the infinite families of finite and affine Weyl groups, including interpretations of the length function and the weak order. We also give new combinatorial proofs of Bott's formula (in the refined version of Macdonald) for the Poincaré series of these affine Weyl groups.
A 2-Coloring of $[1,N]$ can have $(1/22)N^2+O(N)$ Monochromatic Schur Triples, but not less!
Authors: Robertson Aaron , Zeilberger Doron
Published: January 2020

We prove the statement of the title, thereby solving a $100 problem of Ron Graham. This was solved independently by Tomasz Schoen.
Multi-Statistic Enumeration of Two-Stack Sortable Permutations
Authors: Bousquet-Mélou Mireille
Published: January 2020

Using Zeilberger's factorization of two-stack-sortable permutations, we write a functional equation — of a strange sort — that defines their generating function according to five statistics: length, number of descents, number of right-to-left and left-to-right maxima, and a fifth statistic that is closely linked to the factorization. Then, we show how one can translate this functional equation into a polynomial one. We thus prove that our five-variable generating function for two-stack-sortable permutations is algebraic of degree 20.
On $k$-Walk-Regular Graphs
Authors: Dalfó C. , Fiol M. A. , Garriga E.
Published: January 2020

Considering a connected graph $G$ with diameter $D$, we say that it is $k$-walk-regular, for a given integer $k$ $(0\leq k \leq D)$, if the number of walks of length $\ell$ between any pair of vertices only depends on the distance between them, provided that this distance does not exceed $k$. Thus, for $k=0$, this definition coincides with that of walk-regular graph, where the number of cycles of length $\ell$ rooted at a given vertex is a constant through all the graph. In the other extreme, for $k=D$, we get one of the possible definitions for a graph to be distance-regular. In this paper we show some algebraic characterizations of $k$-walk-regularity, which are based on the so-called local spectrum and predistance polynomials of $G$.
A Note on the Asymptotics and Computational Complexity of Graph Distinguishability
Authors: Russell Alexander , Sundaram Ravi
Published: January 2020

A graph $G$ is said to be $d$-distinguishable if there is a $d$-coloring of $G$ which no non-trivial automorphism preserves. That is, $\exists \chi: G \rightarrow \{1, \ldots, d\},$ $$ \forall \phi \in \mathrm{Aut}(G) \setminus \{\mathbf{id}\}, \exists v, \chi(v) \neq \chi(\phi(v)). $$ It was conjectured that if $|G| > |\mathrm{Aut}(G)|$ and the $\mathrm{Aut}(G)$ action on $G$ has no singleton orbits, then $G$ is 2-distinguishable. We give an example where this fails. We partially repair the conjecture by showing that when "enough motion occurs," the distinguishing number does indeed decay. Specifically, defining $$ {\mathrm{m} }(G) = \min_{{\phi \in \mathrm{Aut}(G)} \atop {\phi \neq \mathbf{id}}} |\{v \in G \;:\;\phi(v) \neq v\}|, $$ we show that when ${\mathrm{m}}(G) > 2\log_2 |\mathrm{Aut}(G)|$, $G$ is 2-distinguishable. In general, we show that if $ {\mathrm{m}}(G)\ln d > 2\ln |\mathrm{Aut}(G)|$ then $G$ is $d$-distinguishable. There has been considerable interest in the computational complexity of the $d$-distinguishability problem. Specifically, there has been much musing on the computational complexity of the language $$ \{(G, d)\; : \; G \text{ is $d$-distinguishable}\}. $$ We show that this language lies in AM $\subset \Sigma_2^P \cap \Pi_2^P$. We use this to conclude that if Dist is $\mathbf{coNP}$-hard then the polynomial hierarchy collapses.
Short Score Certificates for Upset Tournaments
Authors: Poet Jeffrey L. , Shader Bryan L.
Published: January 2020

A score certificate for a tournament, $T$, is a collection of arcs of $T$ which can be uniquely completed to a tournament with the same score-list as $T$'s, and the score certificate number of $T$ is the least number of arcs in a score certificate of $T$. Upper bounds on the score certificate number of upset tournaments are derived. The upset tournaments on $n$ vertices are in one–to–one correspondence with the ordered partitions of $n-3$, and are "almost" transitive tournaments. For each upset tournament on $n$ vertices a general construction of a score certificate with at most $2n-3$ arcs is given. Also, for the upset tournament, $T_{\lambda}$, corresponding to the ordered partition $\lambda$, a score certificate with at most $n+2k+3$ arcs is constructed, where $k$ is the number of parts of $\lambda$ of size at least 2. Lower bounds on the score certificate number of $T_{\lambda}$ in the case that each part is sufficiently large are derived. In particular, the score certificate number of the so-called nearly transitive tournament on $n$ vertices is shown to be $n+3$, for $n\geq 10$.
A Bijective Proof of Garsia's $q$-Lagrange Inversion Theorem
Authors: Singer Dan W.
Published: January 2020

A $q$-Lagrange inversion theorem due to A. M. Garsia is proved by means of two sign-reversing, weight-preserving involutions on Catalan trees.
On Minimal Words With Given Subword Complexity
Authors: Wang Ming-wei , Shallit Jeffrey
Published: January 2020

We prove that the minimal length of a word $S_n$ having the property that it contains exactly $F_{m+2}$ distinct subwords of length $m$ for $1 \leq m \leq n$ is $F_n + F_{n+2}$. Here $F_n$ is the $n$th Fibonacci number defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. We also give an algorithm that generates a minimal word $S_n$ for each $n \geq 1$.
Inclusion-Exclusion and Network Reliability
Authors: Dohmen Klaus
Published: January 2020

Based on a recent improvement of the inclusion-exclusion principle, we present a new approach to network reliability problems. In particular, we give a new proof of a result of Shier, which expresses the reliability of a network as an alternating sum over chains in a semilattice, and a new proof of a result of Provan and Ball, which provides an algorithm for computing network reliability in pseudopolynomial time. Moreover, some results on $k$-out-of-$n$ systems are established.
Semifields in Class ${\cal F}_4^{(a)}$
Authors: Ebert Gary , Marino Giuseppe , Polverino Olga , Trombetti Rocco
Published: January 2020

The semifields of order $q^6$ which are two-dimensional over their left nucleus and six-dimensional over their center have been geometrically partitioned into six classes by using the associated linear sets in $PG(3,q^3)$. One of these classes has been partitioned further (again geometrically) into three subclasses. In this paper algebraic curves are used to construct two infinite families of odd order semifields belonging to one of these subclasses, the first such families shown to exist in this subclass. Moreover, using similar techniques it is shown that these are the only semifields in this subclass which have the right or middle nucleus which is two-dimensional over the center. This work is a non-trivial step towards the classification of all semifields that are six-dimensional over their center and two-dimensional over their left nucleus.
The Maximum of the Maximum Rectilinear Crossing Numbers of $d$-Regular Graphs of Order $n$
Authors: Alpert Matthew , Feder Elie , Harborth Heiko
Published: January 2020

We extend known results regarding the maximum rectilinear crossing number of the cycle graph ($C_n$) and the complete graph ($K_n$) to the class of general $d$-regular graphs $R_{n,d}$. We present the generalized star drawings of the $d$-regular graphs $S_{n,d}$ of order $n$ where $n+d\equiv 1 \pmod 2 $ and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of $S_{n,d}$ for $n \equiv d \equiv 0 \pmod 2$ is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by Furry and Kleitman as partial results in the direction of this conjecture.
Scheduling Partial Round Robin Tournaments Subject to Home Away Pattern Sets
Authors: Kashiwabara Kenji
Published: January 2020

We consider the following sports scheduling problem. Consider $2n$ teams in a sport league. Each pair of teams must play exactly one match in $2n-1$ days. That is, $n$ games are held simultaneously in a day. We want to make a schedule which has $n(2n-1)$ games for $2n-1$ days. When we make a schedule, the schedule must satisfy a constraint according to the HAP set, which designates a home game or an away game for each team and each date. Two teams cannot play against each other unless one team is assigned to a home game and the other team is assigned to an away game. Recently, D. Briskorn proposed a necessary condition for an HAP set to have a proper schedule. And he proposed a conjecture that such a condition is also sufficient. That is, if a solution to the linear inequalities exists, they must have an integral solution. In this paper, we rewrite his conjecture by using perfect matchings. We consider a monoid in the affine space generated by perfect matchings. In terms of the Hilbert basis of such a monoid, the problem is naturally generalized to a scheduling problem for not all pairs of teams described by a regular graph. In this paper, we show a regular graph such that the corresponding linear inequalities have a solution but do not have any integral solution. Moreover we discuss for which regular graphs the statement generalizing the conjecture holds.
Discrepancy of Matrices of Zeros and Ones
Authors: Brualdi R. A. , Shen J.
Published: January 2020

Let $m$ and $n$ be positive integers, and let $R=(r_1,\ldots, r_m)$ and $ S=(s_1,\ldots, s_n)$ be non-negative integral vectors. Let ${\cal A} (R,S)$ be the set of all $m \times n$ $(0,1)$-matrices with row sum vector $R$ and column vector $S$, and let $\bar A$ be the $m \times n$ $(0,1)$-matrix where for each $i$, $1\le i \le m$, row $i$ consists of $r_i$ $1$'s followed by $n-r_i$ $0$'s. If $S$ is monotone, the discrepancy $d(A)$ of $A$ is the number of positions in which $\bar A$ has a $1$ and $A$ has a $0$. It equals the number of $1$'s in $\bar A$ which have to be shifted in rows to obtain $A$. In this paper, we study the minimum and maximum $d(A)$ among all matrices $A \in {\cal A} (R,S)$. We completely solve the minimum discrepancy problem by giving an explicit formula in terms of $R$ and $S$ for it. On the other hand, the problem of finding an explicit formula for the maximum discrepancy turns out to be very difficult. Instead, we find an algorithm to compute the maximum discrepancy.