Search for: All records

ABSTRACT If is a list assignment of colors to each vertex of an ‐vertex graph , then anequitable‐coloringof is a proper coloring of vertices of from their lists such that no color is used more than times. A graph isequitably‐choosableif it has an equitable ‐coloring for every ‐list assignment . In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer every graph with maximum degree at most is equitably ‐choosable. The main result of this paper is that for each and each planar graph , a stronger statement holds: if the maximum degree of is at most , then is equitably ‐choosable. In fact, we prove the result for a broader class of graphs—the class of the graphs in which each bipartite subgraph with has at most edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in , in particular, for all planar graphs. We also introduce the new stronger notion ofstrongly equitable(SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE ‐choosable, then it is both equitably ‐choosable and equitably ‐colorable, while neither of being equitably ‐choosable and equitably ‐colorable implies the other. 

Abstract We give a description of the Hallnäs–Ruijsenaars eigenfunctions of the 2-particle hyperbolic Ruijsenaars system as matrix coefficients for the order 4 element$$S\in SL(2,{\mathbb {Z}})$$ $S\in SL(2,Z)$acting on the Hilbert space ofGL(2) quantum Teichmüller theory on the punctured torus. TheGL(2) Macdonald polynomials are then obtained as special values of the analytic continuation of these matrix coefficients. The main tool used in the proof is the cluster structure on the moduli space of framedGL(2)-local systems on the punctured torus, and an$$SL(2,{\mathbb {Z}})$$ $SL(2,Z)$-equivariant embedding of theGL(2) spherical DAHA into the quantized coordinate ring of the corresponding cluster Poisson variety. 

Abstract We study the minimum number of maximum matchings in a bipartite multigraph with parts and under various conditions, refining the well‐known lower bound due to M. Hall. When , every vertex in has degree at least , and every vertex in has at least distinct neighbors, the minimum is when and is when . When every vertex has at least two neighbors and , the minimum is , where . We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions. 

Abstract We study theT-system of type $A_{\mathrm{\infty }}$, also known as the octahedron recurrence/equation, viewed as a $2+1$-dimensional discrete evolution equation. Generalizing earlier work on arctic curves for the Aztec Diamond obtained from solutions of the octahedron recurrence with ‘flat’ initial data, we consider initial data along parallel ‘slanted’ planes perpendicular to an arbitrary admissible direction $(r,s,t)\in {\mathbb{Z}}_{+}^3$. The corresponding solutions of theT-system are interpreted as partition functions of dimer models on some suitable ‘pinecone’ graphs introduced by Bousquet–Mélou, Propp, and West in 2009. TheT-system formulation and some exact solutions in uniform or periodic cases allow us to explore the thermodynamic limit of the corresponding dimer models and to derive exact arctic curves separating the various phases of the system. This direct approach bypasses the standard general theory of dimers using the Kasteleyn matrix approach and uses instead the theory of Analytic Combinatorics in Several Variables, by focusing on a linear system obeyed by the dimer density generating function. 

Abstract A minimal presentation of the cohomology ring of the flag manifold was given in A. Borel (1953). This presentation was extended by E. Akyildiz–A. Lascoux–P. Pragacz (1992) to a nonminimal one for all Schubert varieties. Work of V. Gasharov–V. Reiner (2002) gave a short, that is, polynomial‐size, presentation for a subclass of Schubert varieties that includes the smooth ones. In V. Reiner–A. Woo–A. Yong (2011), a general shortening was found; it implies an exponential upper bound of on the number of generators required. That work states a minimality conjecture whose significance would be an exponential lower bound of on the number of generators needed in worst case, giving the first obstructions to short presentations. We prove the minimality conjecture. Our proof uses the Hopf algebra structure of the ring of symmetric functions. 

Abstract The ‐deckof an ‐vertex graph is the multiset of subgraphs obtained from it by deleting vertices. A family of ‐vertex graphs is ‐recognizableif every graph having the same ‐deck as a graph in the family is also in the family. We prove that the family of ‐vertex graphs with no cycles is ‐recognizable when (except for ). As a consequence, the family of ‐vertex trees is ‐recognizable when and . It is known that this fails when . 

Abstract In this note we examine the following random graph model: for an arbitrary graph , with quadratic many edges, construct a graph by randomly adding edges to and randomly coloring the edges of with colors. We show that for a large enough constant and , every pair of vertices in are joined by a rainbow path, that is, israinbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for and resolved the case when and is a function of . 

We prove a sharp lower bound on the number of terms in an element of the reduced Gröbner basis of a Schubert determinantal ideal $I_w$under the term order of Knutson–Miller [Ann. of Math. (2) 161 (2005), pp. 1245–1318]. We give three applications. First, we give a pattern-avoidance characterization of the matrix Schubert varieties whose defining ideals are binomial. This complements a result of Escobar–Mészáros [Proc. Amer. Math. Soc. 144 (2016), pp. 5081–5096] on matrix Schubert varieties that are toric with respect to their natural torus action. Second, we give a combinatorial proof that the recent formulas of Rajchgot–Robichaux–Weigandt [J. Algebra 617 (2023), pp. 160–191] and Almousa–Dochtermann–Smith [Preprint, arXiv:2209.09851, 2022] computing the Castelnuovo–Mumford regularity of vexillary $I_w$and toric edge ideals of bipartite graphs respectively agree for binomial $I_w$. Third, we demonstrate that the Gröbner basis for $I_w$given by the minimal generators of Gao–Yong [J. Commut. Algebra 16 (2024), pp. 267–273] is reduced if and only if the defining permutation $w$is vexillary.