Search

Given two polynomials $p(x), q(x)$ of degree $d$, we give a combinatorial formula for the finite free cumulants of $p(x)\boxtimes_d q(x)$. We show that this formula admits a topological expansion in terms of non-crossing multi-annular permutations on surfaces of different genera. This topological expansion, on the one hand, deepens the connection between the theories of finite free probability and free probability, and in particular proves that $\boxtimes_d$ converges to $\boxtimes$ as $d$ goes to infinity. On the other hand, borrowing tools from the theory of second order freeness, we use our expansion to study the infinitesimal distribution of certain families of polynomials which include Hermite and Laguerre, and draw some connections with the theory of infinitesimal distributions for real random matrices. Finally, building off our results we give a new short and conceptual proof of a recent result [Steinerberger (2020), Hoskins and Kabluchko (2020)] that connects root distributions of polynomial derivatives with free fractional convolution powers., Comment: 39 pages, 4 figures, 3 apendices

Using Jack polynomials, Goulden and Jackson have introduced a one parameter deformation $\tau_b$ of the generating series of bipartite maps, which generalizes the partition function of $\beta$-ensembles of random matrices. The Matching-Jack conjecture suggests that the coefficients $c^\lambda_{\mu,\nu}$ of the function $\tau_b$ in the power-sum basis are non-negative integer polynomials in the deformation parameter $b$. Do{\l}\k{e}ga and F\'eray have proved in 2016 the "polynomiality" part in the Matching-Jack conjecture, namely that coefficients $c^\lambda_{\mu,\nu}$ are in $\mathbb{Q}[b]$. In this paper, we prove the "integrality" part, i.e that the coefficients $c^\lambda_{\mu,\nu}$ are in $\mathbb{Z}[b]$. The proof is based on a recent work of the author that deduces the Matching-Jack conjecture for marginal sums from an analog result for the $b$-conjecture, established in 2020 by Chapuy and Do{\l}\k{e}ga. A key step in the proof involves a new connection with the graded Farahat-Higman algebra., Comment: 21 pages; v2: minor corrections

The critical exponent E ( u ) E(\mathbf u) of an infinite sequence u \mathbf u over a finite alphabet expresses the maximal repetition of a factor in u \mathbf u . By the famous Dejean’s theorem, E ( u ) ≥ 1 + 1 d − 1 E(\mathbf u) \geq 1+\frac 1{d-1} for every d d -ary sequence u \mathbf u . We define the asymptotic critical exponent E ∗ ( u ) E^*(\mathbf u) as the upper limit of the maximal repetition of factors of length n n . We show that for any d > 1 d>1 there exists a d d -ary sequence u \mathbf u having E ∗ ( u ) E^*(\mathbf u) arbitrarily close to 1 1 . Then we focus on the class of d d -ary balanced sequences. In this class, the values E ∗ ( u ) E^*(\mathbf u) are bounded from below by a threshold strictly bigger than 1. We provide a method which enables us to find a d d -ary balanced sequence with the least asymptotic critical exponent for 2 ≤ d ≤ 10 2\leq d\leq 10 .

Given any graph G G , the spread of G G is the maximum difference between any two eigenvalues of the adjacency matrix of G G . In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers n n , the n n -vertex graph G G that maximizes spread is the join of a clique and an independent set, with ⌊ 2 n / 3 ⌋ \lfloor 2n/3 \rfloor and ⌈ n / 3 ⌉ \lceil n/3 \rceil vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all n n sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over L 2 [ 0 , 1 ] \mathscr {L}^2[0,1] . The second conjecture claims that for any fixed m ≤ n 2 / 4 m \leq n^2/4 , if G G maximizes spread over all n n -vertex graphs with m m edges, then G G is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms.

We show that the number of non-isotopic commutative semifields of odd order $p^{n}$ is exponential in $n$ when $n = 4t$ and $t$ is not a power of $2$. We introduce a new family of commutative semifields and a method for proving isotopy results on commutative semifields that we use to deduce the aforementioned bound. The previous best bound on the number of non-isotopic commutative semifields of odd order was quadratic in $n$ and given by Zhou and Pott [Adv. Math. 234 (2013)]. Similar bounds in the case of even order were given in Kantor [J. Algebra 270 (2003)] and Kantor and Williams [Trans. Amer. Math. Soc. 356 (2004)]., 27 pages. Incorporates reviewer comments. To appear in Transactions of the American Mathematical Society

We continue to study the rank functions of tropical matrices. In this paper, we explain how to reduce the computation of ranks for matrices over the `supertropical semifield' to the standard tropical case. Using a counting approach, we prove the existence of a $01$-matrix with many ones and without large all-one submatrices, and we put our results together and construct an $n\times n$ matrix with tropical rank $o(n^{0.5+\varepsilon})$ and Kapranov rank $n-o(n)$., Comment: 9 pages

We show that every $r$-uniform hypergraph on $n$ vertices which does not contain a tight cycle has at most $O(n^{r-1} (\log n)^5)$ edges. This is an improvement on the previously best-known bound, of $n^{r-1} e^{O(\sqrt{\log n})}$, due to Sudakov and Tomon, and our proof builds up on their work. A recent construction of B. Janzer implies that our bound is tight up to an $O((\log n)^4 \log \log n)$ factor., Comment: 9 pages; corrected typos

We consider the notion of discrete Ricci curvature for graphs defined by Schmuckenschl{\"a}ger \cite{shmuck} and compute its value for Bruhat graphs associated to finite Coxeter groups. To do so we work with the geometric realization of a finite Coxeter group and a classical result obtained by Dyer in \cite{Dyer}. As an application we obtain a bound for the spectral gap of the Bruhat graph of any finite Coxeter group and an isoperimetric inequality for them. Our proofs are case-free., Comment: 12 pages. arXiv admin note: text overlap with arXiv:2102.10134

We introduce toric promotion as a cyclic analogue of Sch\"utzenberger's promotion operator. Toric promotion acts on the set of labelings of a graph $G$. We discuss connections between toric promotion and previously-studied notions such as toric posets and friends-and-strangers graphs. Our main theorem provides a surprisingly simple description of the orbit structure of toric promotion when $G$ is a forest., Comment: 10 pages, 5 figures, to be published in Proceedings of the AMS

Starting from an integrable rank-$n$ vertex model, we construct an explicit family of partition functions indexed by compositions $\mu = (\mu_1,\dots,\mu_n)$. Using the Yang-Baxter algebra of the model and a certain rotation operation that acts on our partition functions, we show that they are eigenfunctions of the Cherednik-Dunkl operators $Y_i$ for all $1 \leq i \leq n$, and are thus equal to nonsymmetric Macdonald polynomials $E_{\mu}$. Our partition functions have the combinatorial interpretation of ensembles of coloured lattice paths which traverse a cylinder. Applying a simple bijection to such path ensembles, we show how to recover the well-known combinatorial formula for $E_{\mu}$ due to Haglund-Haiman-Loehr., Comment: 36 pages

In this paper, we perform a systematic study of permutation statistics and bijective maps on permutations in which we identify and prove 122 instances of the homomesy phenomenon. Homomesy occurs when the average value of a statistic is the same on each orbit of a given map. The maps we investigate include the Lehmer code rotation, the reverse, the complement, the Foata bijection, and the Kreweras complement. The statistics studied relate to familiar notions such as inversions, descents, and permutation patterns, and also more obscure constructs. Beside the many new homomesy results, we discuss our research method, in which we used SageMath to search the FindStat combinatorial statistics database to identify potential homomesies.

Motivated by questions asked by Erdos, we prove that any set $A\subset{\mathbb N}$ with positive upper density contains, for any $k\in{\mathbb N}$, a sumset $B_1+\cdots+B_k$, where $B_1,\dots,B_k\subset{\mathbb N}$ are infinite. Our proof uses ergodic theory and relies on structural results for measure preserving systems. Our techniques are new, even for the previously known case of $k=2$., Comment: 49 Pages

The notion of better quasi order ($\mathsf{BQO}$), due to Nash-Williams, is very fruitful mathematically and intriguing from the standpoint of logic, due to several long-standing open problems. In the present paper, we make a significant step towards one of these: Let $\mathbf 3$ be the discrete order with three elements. We show that arithmetical recursion along the natural numbers ($\mathsf{ACA}_0^+$) follows from $\mathbf 3$ being $\mathsf{BQO}$, over the base theory $\mathsf{RCA_0}$ from reverse mathematics. Also over the latter, we deduce arithmetical transfinite recursion ($\mathsf{ATR}_0$) from the assumption that $\mathbf 3$ is $\Delta^0_2\text{-}\mathsf{BQO}$, which plays a role in work of Montalb\'an., Comment: The results in the current version are significantly stronger than those in the previous one, and the title has been changed

Given a fixed hypergraph H H , let wsat ⁡ ( n , H ) \operatorname {wsat}(n,H) denote the smallest number of edges in an n n -vertex hypergraph G G , with the property that one can sequentially add the edges missing from G G , so that whenever an edge is added, a new copy of H H is created. The study of wsat ⁡ ( n , H ) \operatorname {wsat}(n,H) was introduced by Bollobás in 1968, and turned out to be one of the most influential topics in extremal combinatorics. While for most H H very little is known regarding wsat ⁡ ( n , H ) \operatorname {wsat}(n,H) , Alon proved in 1985 that for every graph H H there is a limiting constant C H C_H so that wsat ⁡ ( n , H ) = ( C H + o ( 1 ) ) n \operatorname {wsat}(n,H)=(C_H+o(1))n . Tuza conjectured in 1992 that Alon’s theorem can be (appropriately) extended to arbitrary r r -uniform hypergraphs. In this paper we prove this conjecture.

A recent conjecture of Di Francesco states that the number of domino tilings of a certain family of regions on the square lattice is given by a product formula reminiscent of the one giving the number of alternating sign matrices. These regions, denoted ${\mathcal T}_n$, are obtained by starting with a square of side-length $2n$, cutting it in two along a diagonal by a zigzag path with step length two, and gluing to one of the resulting regions half of an Aztec diamond of order $n-1$. Inspired by the regions ${\mathcal T}_n$, we construct a family $C_{m,n}^{a,b,c,d}$ of cruciform regions generalizing the Aztec diamonds and we prove that their number of domino tilings is given by a simple product formula. Since (as it follows from our results) the number of domino tilings of ${\mathcal T}_n$ is a divisor of the number of tilings of the cruciform region $C_{2n-1,2n-1}^{n-1,n,n,n-2}$, the special case of our formula corresponding to the latter can be viewed as partial progress towards proving Di Francesco's conjecture., 14 pages

We study the category whose objects are graphs of fixed genus and whose morphisms are contractions. We show that the corresponding contravariant module categories are Noetherian and we study two families of modules over these categories. The first takes a graph to a graded piece of the homology of its unordered configuration space and the second takes a graph to an intersection homology group whose dimension is given by a Kazhdan-Lusztig coefficient; in both cases we prove that the module is finitely generated. This allows us to draw conclusions about torsion in the homology groups of graph configuration spaces, and about the growth of Betti numbers of graph configuration spaces and Kazhdan-Lusztig coefficients of graphical matroids. We also explore the relationship between our category and outer space, which is used in the study of outer automorphisms of free groups., Comment: arXiv admin note: text overlap with arXiv:1903.10592

In 2007, Grytczuk conjectured that for any sequence ( ℓ i ) i ≥ 1 (\ell _i)_{i\ge 1} of alphabets of size 3 3 there exists a square-free infinite word w w such that for all i i , the i i -th letter of w w belongs to ℓ i \ell _i . The result of Thue from 1906 implies that there is an infinite square-free word if all the ℓ i \ell _i are identical. On the other hand, Grytczuk, Przybyło and Zhu showed in 2011 that it also holds if the ℓ i \ell _i are of size 4 4 instead of 3 3 . In this article, we first show that if the lists are of size 4 4 , the number of square-free words is at least 2.45 n 2.45^n (the previous similar bound was 2 n 2^n ). We then show our main result: we can construct such a square-free word if the lists are subsets of size 3 3 of the same alphabet of size 4 4 . Our proof also implies that there are at least 1.25 n 1.25^n square-free words of length n n for any such list assignment. This proof relies on the existence of a set of coefficients verified with a computer. We suspect that the full conjecture could be resolved by this method with a much more powerful computer (but we might need to wait a few decades for such a computer to be available).

Part of the work was done while the authors were visiting the South China University of Science and Technology (SUSTech), Shenzhen, in 2018, and we are grateful (in particular to Professor Cai Heng Li) for the hospitality that we received.The authors would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme Groups, representations and applications: new perspectives (supported by EPSRC grant no.EP/R014604/1), where further work on this paper was undertaken. In particular we acknowledge a Simons Fellowship (Cameron) and a Kirk Distinguished Visiting Fellowship (Praeger) during this programme. Schneider thanks the Centre for the Mathematics of Symmetry and Computation of The University of Western Australia and Australian Research Council Discovery Grant DP160102323 for hosting his visit in 2017 and acknowledges the support of the CNPq projects Produtividade em Pesquisa (project no.: 308212/2019-3) and Universal (project no.:421624/2018-3). Diagonal groups are one of the classes of finite primitive permutation groups occurring in the conclusion of the O'Nan-Scott theorem. Several of the other classes have been described as the automorphism groups of geometric or combinatorial structures such as affine spaces or Cartesian decompositions, but such structures for diagonal groups have not been studied in general. The main purpose of this paper is to describe and characterise such structures, which we call diagonal semilattices. Unlike the diagonal groups in the O'Nan-Scott theorem, which are defined over finite characteristically simple groups, our construction works over arbitrary groups, finite or infinite. A diagonal semilattice depends on a dimension m and a group T. For m=2, it is a Latin square, the Cayley table of T, though in fact any Latin square satisfies our combinatorial axioms. However, for m≥3, the group T emerges naturally and uniquely from the axioms. (The situation somewhat resembles projective geometry, where projective planes exist in great profusion but higher-dimensional structures are coordinatised by an algebraic object, a division ring.) A diagonal semilattice is contained in the partition lattice on a set Ω, and we provide an introduction to the calculus of partitions. Many of the concepts and constructions come from experimental design in statistics. We also determine when a diagonal group can be primitive, or quasiprimitive (these conditions turn out to be equivalent for diagonal groups). Associated with the diagonal semilattice is a graph, the diagonal graph, which has the same automorphism group as the diagonal semilattice except in four small cases with m

For any $n\in\mathbb{N}=\{0,1,2,\ldots\}$ and $b,c\in\mathbb{Z}$, the generalized central trinomial coefficient $T_n(b,c)$ denotes the coefficient of $x^n$ in the expansion of $(x^2+bx+c)^n$. Let $p$ be an odd prime. In this paper, we determine the summation $\sum_{k=0}^{p-1}T_k(b,c)^2/m^k$ modulo $p^2$ for integers $m$ with certain restrictions. As applications, we confirm some conjectural congruences of Sun [Sci. China Math. 57 (2014), 1375--1400]., 13 pages. This is a preliminary manuscript

The paper presents conditions on entry permutations that induce asymptotic freeness when acting on Gaussian random matrices. The class of permutations described includes the matrix transpose, as well as entry permutations relevant in Quantum Information Theory and Quantum Physics., Comment: Second version, some errors corrected, less pages, more results

The Frobenius characteristic of $Lie_n,$ the representation of the symmetric group $S_n$ afforded by the multilinear component of the free Lie algebra, is known to satisfy many interesting plethystic identities. In this paper we prove a conjecture of Richard Stanley establishing the plethystic inverse of the sum $\sum_{n\geq 0} Lie_{2n+1}$ of the odd Lie characteristics. We obtain an apparently new plethystic decomposition of the regular representation of $S_n$ in terms of irreducibles indexed by hooks, and the Lie representations. We determine the plethystic inverse of the alternating sum of the odd Lie characteristics., Comment: 12 pages; Section 3 reorganised per referee comments; added Lemma 3.2 and Proposition 3.9. To appear in Proceedings of the American Mathematical Society

Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope $P$ is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which $P$ can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension $d$, the extension complexity of a random $d$-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic $n$-vertex polygon (whose vertices lie on a circle) has extension complexity at most $24\sqrt n$. This bound is tight up to the constant factor $24$. Finally, we show that there exists an $n^{o(1)}$-dimensional polytope with at most $n$ vertices and extension complexity $n^{1-o(1)}$. Our theorems are proved with a range of different techniques, which we hope will be of further interest., Comment: 32 pages, 5 figures

A small polygon is a polygon of unit diameter. The maximal width of an equilateral small polygon with n = 2 s n=2^s vertices is not known when s ≥ 3 s \ge 3 . This paper solves the first open case and finds the optimal equilateral small octagon. Its width is approximately 3.24 3.24% larger than the width of the regular octagon: cos ⁡ ( π / 8 ) \cos (\pi /8) . In addition, the paper proposes a family of equilateral small n n -gons, for n = 2 s n=2^s with s ≥ 4 s\ge 4 , whose widths are within O ( 1 / n 4 ) O(1/n^4) of the maximal width.

We study the diameter of the graph $G(w)$ of reduced words of an element $w$ in a Coxeter group $W$ whose edges correspond to applications of the Coxeter relations. We resolve conjectures of Reiner--Roichman and Dahlberg--Kim by proving a tight lower bound on this diameter when $W=S_n$ is the symmetric group and by characterizing the equality cases. We also give partial results in other classical types which illustrate the limits of current techniques., 14 pages, comments welcome

Let $M_n$ be drawn uniformly from all $\pm 1$ symmetric $n \times n$ matrices. We show that the probability that $M_n$ is singular is at most $\exp(-c(n\log n)^{1/2})$, which represents a natural barrier in recent approaches to this problem. In addition to improving on the best-known previous bound of Campos, Mattos, Morris and Morrison of $\exp(-c n^{1/2})$ on the singularity probability, our method is different and considerably simpler., 12 pages

Let Δ = Δ 1 × … × Δ d ⊆ R n \Delta =\Delta _1\times \ldots \times \Delta _d\subseteq \mathbb {R}^n , where R n = R n 1 × ⋯ × R n d \mathbb {R}^n=\mathbb {R}^{n_1}\times \cdots \times \mathbb {R}^{n_d} with each Δ i ⊆ R n i \Delta _i\subseteq \mathbb {R}^{n_i} a non-degenerate simplex of n i n_i points. We prove that any set S ⊆ R n S\subseteq \mathbb {R}^n , with n = n 1 + ⋯ + n d n=n_1+\cdots +n_d of positive upper Banach density necessarily contains an isometric copy of all sufficiently large dilates of the configuration Δ \Delta . In particular any such set S ⊆ R 2 d S\subseteq \mathbb {R}^{2d} contains a d d -dimensional cube of side length λ \lambda , for all λ ≥ λ 0 ( S ) \lambda \geq \lambda _0(S) . We also prove analogous results with the underlying space being the integer lattice. The proof is based on a weak hypergraph regularity lemma and an associated counting lemma developed in the context of Euclidean spaces and the integer lattice.

We prove that large classes of algebras in the framework of root of unity quantum cluster algebras have the structures of maximal orders in central simple algebras and Cayley-Hamilton algebras in the sense of Procesi. We show that every root of unity upper quantum cluster algebra is a maximal order and obtain an explicit formula for its reduced trace. Under mild assumptions, inside each such algebra we construct a canonical central subalgebra isomorphic to the underlying upper cluster algebra, such that the pair is a Cayley-Hamilton algebra; its fully Azumaya locus is shown to contain a copy of the underlying cluster $\mathcal{A}$-variety. Both results are proved in the wider generality of intersections of mixed quantum tori over subcollections of seeds. Furthermore, we prove that all monomial subalgebras of root of unity quantum tori are Cayley-Hamilton algebras and classify those ones that are maximal orders. Arbitrary intersections of those over subsets of seeds are also proved to be Cayley-Hamilton algebras. Previous approaches to constructing maximal orders relied on filtration and homological methods. We use new methods based on cluster algebras.

In 1975, Erd\H{o}s asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders., Comment: 10 pages, 2 figures

In this work we present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations.\ud This approach provides a unified view on many known results and allows us to prove many new ones.\ud In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element set by adjacent transpositions; the binary reflected Gray code to generate all $n$-bit strings by flipping a single bit in each step; the Gray code for generating all $n$-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an $n$-element ground set by element exchanges due to Kaye.\ud \ud We present two distinct applications for our new framework:\ud The first main application is the generation of pattern-avoiding permutations, yielding new Gray codes for different families of permutations that are characterized by the avoidance of certain classical patterns, (bi)vincular patterns, barred patterns, boxed patterns, Bruhat-restricted patterns, mesh patterns, monotone and geometric grid classes, and many others.\ud We also obtain new Gray codes for all the combinatorial objects that are in bijection to these permutations, in particular for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into $n$ rectangles subject to certain restrictions.\ud \ud The second main application of our framework are lattice congruences of the weak order on the symmetric group~$S_n$.\ud Recently, Pilaud and Santos realized all those lattice congruences as $(n-1)$-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc.\ud Our algorithm generates the equivalence classes of each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian.\ud We thus also obtain a provable notion of optimality for the Gray codes obtained from our framework: They translate into walks along the edges of a polytope.

We investigate when a Borel graph admits a (Borel or measurable) orientation with outdegree bounded by k k for various cardinals k k . We show that for a probability measure preserving (p.m.p) graph G G , a measurable orientation can be found when k k is larger than the normalized cost of the restriction of G G to any positive measure subset. Using an idea of Conley and Tamuz, we can also find Borel orientations of graphs with subexponential growth; however, for every k k we also find graphs which admit measurable orientations with outdegree bounded by k k but no such Borel orientations. Finally, for special values of k k we bound the projective complexity of Borel k k -orientability for graphs and graphings of equivalence relations. It follows from these bounds that the set of equivalence relations admitting a Borel selector is Σ 2 1 \mathbf {\Sigma }_{2}^{1} in the codes, in stark contrast to the case of smooth relations.

A special case of a fundamental result of Loewner and Horn [Trans. Amer. Math. Soc. 1969] says that given an integer $n \geq 1$, if the entrywise application of a smooth function $f : (0,\infty) \to \mathbb{R}$ preserves the set of $n \times n$ positive semidefinite matrices with positive entries, then $f$ and its first $n-1$ derivatives are non-negative on $(0,\infty)$. In a recent joint work with Belton-Guillot-Putinar [J. Eur. Math. Soc., in press], we proved a stronger version, and used it to strengthen the Schoenberg-Rudin characterization of dimension-free positivity preservers [Duke Math. J. 1942, 1959]. In recent works with Belton-Guillot-Putinar [Adv. Math. 2016] and with Tao [Amer. J. Math., in press] we used local, real-analytic versions at the origin of the Horn-Loewner condition, and discovered unexpected connections between entrywise polynomials preserving positivity and Schur polynomials. In this paper, we unify these two stories via a Master Theorem (Theorem A) which (i) simultaneously unifies and extends all of the aforementioned variants; and (ii) proves the positivity of the first $n$ nonzero Taylor coefficients at individual points rather than on all of $(0,\infty)$. A key step in the proof is a new determinantal / symmetric function calculation (Theorem B), which shows that Schur polynomials arise naturally from considering arbitrary entrywise maps that are sufficiently differentiable. Of independent interest may be the following application to symmetric function theory: we extend the Schur function expansion of Cauchy's (1841) determinant (whose matrix entries are geometric series $1 / (1 - u_j v_k)$), as well as of a determinant of Frobenius [J. reine angew. Math. 1882] (whose matrix entries are a sum of two geometric series), to arbitrary power series, and over all commutative rings., Comment: Final version, to appear in Transactions of the American Mathematical Society. 19 pages, no figures

We prove that if G = ( V , E ) G=(V,E) is an ω \omega -stable (respectively, superstable) graph with χ ( G ) > ℵ 0 \chi (G)>\aleph _0 (respectively, 2 ℵ 0 2^{\aleph _0} ) then G G contains all the finite subgraphs of the shift graph S h n ( ω ) \mathrm {Sh}_n(\omega ) for some n n . We prove a variant of this theorem for graphs interpretable in stationary stable theories. Furthermore, if G G is ω \omega -stable with U ⁡ ( G ) ≤ 2 \operatorname {U}(G)\leq 2 we prove that n ≤ 2 n\leq 2 suffices.

We introduce shortcut graphs and groups. Shortcut graphs are graphs in which cycles cannot embed without metric distortion. Shortcut groups are groups which act properly and cocompactly on shortcut graphs. These notions unify a surprisingly broad family of graphs and groups of interest in geometric group theory and metric graph theory, including: the 1-skeletons of systolic and quadric complexes (in particular finitely presented C(6) and C(4)-T(4) small cancellation groups), 1-skeletons of finite dimensional CAT(0) cube complexes, hyperbolic graphs, standard Cayley graphs of finitely generated Coxeter groups and the standard Cayley graph of the Baumslag-Solitar group BS(1,2). Most of these examples satisfy a strong form of the shortcut property. The shortcut properties also have important geometric group theoretic consequences. We show that shortcut groups are finitely presented and have exponential isoperimetric and isodiametric functions. We show that groups satisfying the strong form of the shortcut property have polynomial isoperimetric and isodiametric functions., Comment: 42 pages

We investigate criteria for circle packing(CP) types of disk triangulation graphs embedded into simply connected domains in $ \mathbb{C}$. In particular, by studying combinatorial curvature and the combinatorial Gauss-Bonnet theorem involving boundary turns, we show that a disk triangulation graph is CP parabolic if \[ \sum_{n=1}^\infty \frac{1}{\sum_{j=0}^{n-1} (k_j +6)} = \infty, \] where $k_n$ is the degree excess sequence defined by \[ k_n = \sum_{v \in B_n} (\mbox{deg}\, v - 6) \] for combinatorial balls $B_n$ of radius $n$ and centered at a fixed vertex. It is also shown that the simple random walk on a disk triangulation graph is recurrent if \[ \sum_{n=1}^\infty \frac{1}{\sum_{j=0}^{n-1} (k_j +6)+\sum_{j=0}^{n} (k_j +6)} = \infty. \] These criteria are sharp, and generalize a conjecture by He and Schramm in their paper from 1995, which was later proved by Repp in 2001. We also give several criteria for CP hyperbolicity, one of which generalizes a theorem of He and Schramm, and present a necessary and sufficient condition for CP types of layered circle packings generalizing and confirming a criterion given by Siders in 1998., Comment: 45 pages, 19 figures; to appear in TAMS

In this paper we present a variety of problems in the interface between combinatorics and geometry around the theorems of Helly, Radon, Carathéodory, and Tverberg. Through these problems we describe the fascinating area of Helly-type theorems and explain some of their main themes and goals.

A graph $X$ is defined inductively to be $(a_0,\dots,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,\dots,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular (HR) of level $n$ if $a_{n-1}\neq 0$. Chapman, Linial and Peled studied HR-graphs of level 2 and provided several methods to construct families of graphs which are expanders "globally and locally". They ask whether such HR-graphs of level 3 exist. In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can lead to such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $\mathcal{P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $\mathcal{P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$. This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled., Comment: 22 pages, 2 tables. Dedicated to the memory of John Conway and Ernest Vinberg

We study gaps in the spectra of the adjacency matrices of large finite cubic graphs. It is known that the gap intervals ( 2 2 , 3 ) (2 \sqrt {2},3) and [ − 3 , − 2 ) [-3,-2) achieved in cubic Ramanujan graphs and line graphs are maximal. We give constraints on spectra in [ − 3 , 3 ] [-3,3] which are maximally gapped and construct examples which achieve these bounds. These graphs yield new instances of maximally gapped intervals. We also show that every point in [ − 3 , 3 ) [-3,3) can be gapped by planar cubic graphs. Our results show that the study of spectra of cubic, and even planar cubic, graphs is subtle and very rich.

Given an elliptic curve $E$ defined over $\mathbb{C}$, let $E^{\times}$ be an open subset of $E$ obtained by removing a point. In this paper, we show that the $i$-th Betti number of the unordered configuration space $\mathrm{Conf}^{n}(E^{\times})$ of $n$ points on $E^{\times}$ appears as a coefficient of an explicit rational function in two variables. We also compute its Hodge numbers as coefficients of another explicit rational function in four variables. Our result is interesting because these rational functions resemble the generating function of the $\mathbb{F}_{q}$-point counts of $\mathrm{Conf}^{n}(E^{\times})$, which can be obtained from the zeta function of $E$ over a finite field $\mathbb{F}_{q}$. We show that the mixed Hodge structure of the $i$-th singular cohomology group $H^{i}(\mathrm{Conf}^{n}(E^{\times}))$ with complex coefficients is pure of weight $w(i)$, an explicit integer we provide in this paper. This purity statement implies our main result about the Betti numbers and the Hodge numbers. Our proof uses Totaro's spectral sequence computation that describes the weight filtration of the mixed Hodge structure on $H^{i}(\mathrm{Conf}^{n}(E^{\times}))$., Comment: 19 pages

We show that the asymptotic dimension of a geodesic space that is homeomorphic to a subset in the plane is at most three. In particular, the asymptotic dimension of the plane and any planar graph is at most three., Comment: Definitions of M-fat theta curve and M-coarse cactus are slightly changed. The proof of Theorem 3.2 (it used to be Theorem 3.1) is changed and now simpler. Some references are added, in particular [16] by Jorgensen and Lang

We construct new "standard modules" for the representations of general linear groups over a local non-archimedean field. The construction uses a modified Robinson-Schensted-Knuth correspondence for Zelevinsky's multisegments. Typically, the new class categorifies the basis of Doubilet, Rota, and Stein for matrix polynomial rings, indexed by bitableaux. Hence, our main result provides a link between the dual canonical basis (coming from quantum groups) and the DRS basis., Comment: With an appendix by Mark Shimozono

An identity is derived expressing Schur functions as sums over products of pairs of Schur $Q$-functions, generalizing previously known special cases. This is shown to follow from their representations as vacuum expectation values (VEV's) of products of either charged or neutral fermionic creation and annihilation operators, Wick's theorem and a factorization identity for VEV's of products of two mutually anticommuting sets of neutral fermionic operators., 17 pages. Typos corrected. Title word order changed. References updated

We prove that the i th i^\text {th} graded pieces of the Orlik–Solomon algebras or Cordovil algebras of resonance arrangements form a finitely generated FS o p \operatorname {FS}^{\mathrm {op}} -module, thus obtaining information about the growth of their dimensions and restrictions on the irreducible representations of symmetric groups that they contain.

We prove that if $P$ is a set of $n$ points in $\mathbb{C}^2$, then either the points in $P$ determine $\Omega(n^{1-\epsilon})$ complex distances, or $P$ is contained in a line with slope $\pm i$. If the latter occurs then each pair of points in $P$ have complex distance 0., Comment: 41 pages, 0 figures

Let $\mathcal{S}_n$ be the set of all $n$-by-$n$ symmetric real matrices, and let $\mathcal{C}_n$ be the copositive cone, that is, the set of all matrices $a\in\mathcal{S}_n$ that fulfill the condition $u^\top a u\geqslant0$ for all $n$-vectors $u$ with nonnegative entries. We prove that a linear mapping $\varphi:\mathcal{S}_n\to \mathcal{S}_n$ satisfies $\varphi(\mathcal{C}_n)=\mathcal{C}_n$ if and only if $$\varphi(x)=m^\top xm$$ for a fixed monomial matrix $m$ with nonnegative entries., Comment: 5 pages

A correspondence functor is a functor from the category of finite sets and correspondences to the category of k k -modules, where k k is a commutative ring. We determine exactly which simple correspondence functors are projective. We also determine which simple modules are projective for the algebra of all relations on a finite set. Moreover, we analyze the occurrence of such simple projective functors inside the correspondence functor F F associated with a finite lattice and we deduce a direct sum decomposition of F F .

Let $f_n(z) = \sum_{k = 0}^n \varepsilon_k z^k$ be a random polynomial where $\varepsilon_0,\ldots,\varepsilon_n$ are i.i.d. random variables with $\mathbb{E} \varepsilon_1 = 0$ and $\mathbb{E} \varepsilon_1^2 = 1$. Letting $r_1, r_2,\ldots, r_k$ denote the real roots of $f_n$, we show that the point process defined by $\{|r_1| - 1,\ldots, |r_k| - 1 \}$ converges to a non-Poissonian limit on the scale of $n^{-1}$ as $n \to \infty$. Further, we show that for each $\delta > 0$, $f_n$ has a real root within $\Theta_{\delta}(1/n)$ of the unit circle with probability at least $1 - \delta$. This resolves a conjecture of Shepp and Vanderbei from 1995 by confirming its weakest form and refuting its strongest form., Comment: 19 pages

A recent breakthrough of Conlon and Ferber yielded an exponential improvement on the lower bounds for multicolor diagonal Ramsey numbers. In this note, we modify their construction and obtain improved bounds for more than three colors., 4 pages; minor edits from v1

We study indecomposable involutive set-theoretic solutions of the Yang-Baxter equation with cyclic permutation groups (cocyclic solutions). In particular, we show that there is no one-to-one correspondence between indecomposable cocyclic solutions and cocyclic braces which contradicts recent results in \cite{Rump21}.

In this note we generalise some of the work of Klarner on free semigroups of affine maps acting on the real line by using a classical approach from geometric group theory (the Ping-Pong lemma). We also investigate the boundaries within which Klarner's necessary condition for a semigroup to be related is applicable., 7 pages, 1 figure

For a nonnegative weakly irreducible tensor, its spectral radius is an eigenvalue corresponding to a unique positive eigenvector up to a scalar called the Perron vector. But including the Perron vector, it may have more than one eigenvector corresponding to the spectral radius. The projective eigenvariety associated with the spectral radius is the set of the eigenvectors corresponding to the spectral radius considered in the complex projective space. In this paper we prove that the dimension of the above projective eigenvariety is zero, i.e. there are finite many eigenvectors associated with the spectral radius up to a scalar. For a general nonnegative tensor, we characterize the nonnegative combinatorially symmetric tensor for which the dimension of projective eigenvariety associated with spectral radius is greater than zero. Finally we apply those results to the adjacency tensors of uniform hypergraphs., Comment: arXiv admin note: text overlap with arXiv:1707.07414