More Like this

1. Counting and Enumerating Optimum Cut Sets for Hypergraph k -Partitioning Problems for Fixed k

   https://doi.org/10.1287/moor.2022.0259  

   Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang (December 2023, Mathematics of Operations Research)

   We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems, namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph [Formula: see text] with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k nonempty parts [Formula: see text]—known as a k-partition—so as to minimize an objective of interest. (1) If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. (2) If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an [Formula: see text]-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known [Formula: see text]-time deterministic algorithm, in which n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs). Funding: All authors were supported by NSF AF 1814613 and 1907937. 

   more » « less
2. The Euclidean k -Supplier Problem

   https://doi.org/10.1287/moor.2018.0953  

   Nagarajan, Viswanath; Schieber, Baruch; Shachnai, Hadas (February 2020, Mathematics of Operations Research)
3. K -Orbit closures and Hessenberg varieties

   https://doi.org/10.1017/fms.2025.10063  

   Can, Mahir Bilen; Precup, Martha; Shareshian, John; Uğurlu, Özlem (June 2025, Forum of Mathematics, Sigma)
4. k -mer approaches for biodiversity genomics

   https://doi.org/10.1101/gr.279452.124  

   Jenike, Katharine M; Campos-Domínguez, Lucía; Boddé, Marilou; Cerca, José; Hodson, Christina N; Schatz, Michael C; Jaron, Kamil S (January 2025, Genome Research)

   The wide array of currently available genomes displays a wonderful diversity in size, composition, and structure and is quickly expanding thanks to several global biodiversity genomics initiatives. However, sequencing of genomes, even with the latest technologies, can still be challenging for both technical (e.g., small physical size, contaminated samples, or access to appropriate sequencing platforms) and biological reasons (e.g., germline-restricted DNA, variable ploidy levels, sex chromosomes, or very large genomes). In recent years,k-mer-based techniques have become popular to overcome some of these challenges. They are based on the simple process of dividing the analyzed sequences (e.g., raw reads or genomes) into a set of subsequences of lengthk, calledk-mers, and then analyzing the frequency or sequences of thosek-mers. Analyses based onk-mers allow for a rapid and intuitive assessment of complex sequencing data sets. Here, we provide a comprehensive review to the theoretical properties and practical applications ofk-mers in biodiversity genomics with a special focus on genome modeling. 

   more » « less
5. Back Stable K -Theory Schubert Calculus

   https://doi.org/10.1093/imrn/rnac315  

   Lam, Thomas; Lee, Seung Jin; Shimozono, Mark (November 2022, International Mathematics Research Notices)

   Abstract We study the back stable $$K$$-theory Schubert calculus of the infinite flag variety. We define back stable (double) Grothendieck polynomials and double $$K$$-Stanley functions and establish coproduct expansion formulae. Applying work of Weigandt, we extend our previous results on bumpless pipedreams from cohomology to $$K$$-theory. We study finiteness and positivity properties of the ring of back stable Grothendieck polynomials and divided difference operators in $$K$$-homology. 

   more » « less