KNKathryn Nyman

Kathryn Nyman

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Kathryn Nyman has a total of 17 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On statistics of prime parking functions, Łukasiewicz paths, and quasisymmetric functions

    by Pamela E. Harris, Selvi Kara, Erin McNicholas, Kathryn Nyman, Mei Yin

    We recall that a parking function of length $n+1$ is said to be prime if removing any instance of 1 yields a parking function of length $n$. In this article, we study prime parking functions from multiple lenses. We derive an explicit formula for the average value of the total displacement of prime parking functions. We present a formula for the displacement-enumerator of prime parking functions that involves a sum over Łukasiewicz paths. We describe the one-to-one correspondence between parking functions and labeledŁukasiewicz paths via Dyck paths. We introduce the concept of $\ell$-forward differences and use this as a vehicle for examining ties, ascents, and descents in prime parking functions. We establish a link between Schur functions corresponding to the partition $(i,1^{n-i})$ and fundamental quasisymmetric functions indexed by prime parking function tie sets of size $n-i.$

  • Voting on Relations Using Pairs Information

    by Karl-Dieter Crisman, Erin McNicholas, Kathryn Nyman, Michael Orrison

    Rather than analyzing the attributes of voting procedures, we present a common framework within which to understand and juxtapose various methods. This framework allows us to draw surprising connections between disparate procedures presented in a wide range of papers spanning several decades.

  • Fair division with multiple pieces

    by Kathryn Nyman, Francis Edward Su, Shira Zerbib


  • Open Access

    Fair division with multiple pieces

    by Kathryn Nyman, Francis Edward Su, Shira Zerbib

    Given a set of $p$ players we consider problems concerning envy-free allocation of collections of $k$ pieces from a given set of goods or chores. We show that if $p\le n$ and each player can choose $k$ pieces out of $n$ pieces of a cake, then there exist a division of the cake and an allocation of the pieces where at least $\frac{p}{2(k^2-k+1)}$ players get their desired $k$ pieces each. We further show that if $p\le k(n-1)+1$ and each player can choose $k$ pieces, one from each of $k$ cakes that are divided into $n$ pieces each, then there exist a division of the cakes and allocation of the pieces where at least $\frac{p}{2k(k-1)}$ players get their desired $k$ pieces. Finally we prove that if $p\ge k(n-1)+1$ and each player can choose one shift in each of $k$ days that are partitioned into $n$ shifts each, then, given that the salaries of the players are fixed, there exist $n(1+\ln k)$ players covering all the shifts, and moreover, if $k=2$ then $n$ players suffice. Our proofs combine topological methods and theorems of F\"uredi, Lov\'asz and Gallai from hypergraph theory.

  • Open Access

    Double-interval societies

    by Maria Klawe, Kathryn L. Nyman, Jacob N. Scott, Francis Edward Su

    Consider a society of voters, each of whom specify an approval set over a linear political spectrum. We examine double-interval societies, in which each person's approval set is represented by two disjoint closed intervals, and study this situation where the approval sets are pairwise-intersecting: every pair of voters has a point in the intersection of their approval sets. The approval ratio for a society is, loosely speaking, the popularity of the most popular position on the spectrum. We study the question: what is the minimal guaranteed approval ratio for such a society? We provide a lower bound for the approval ratio, and examine a family of societies that have rather low approval ratios. These societies arise from double-n strings: arrangements of n symbols in which each symbol appears exactly twice.

  • Open Access

    Properties of Generalized Derangement Graphs

    by Hannah Jackson, Kathryn Nyman, Les Reid

    A permutation sigma in Sn is a k-derangement if for any subset X = {a1, . . ., ak} \subseteq [n], {sigma(a1), . . ., sigma(ak)} is not equal to X. One can form the k-derangement graph on the set of permutations of Sn by connecting two permutations sigma and tau if sigma(tau)^-1 is a k-derangement. We characterize when such a graph is connected or Eulerian. For n an odd prime power, we determine the independence, clique and chromatic number of the 2-derangement graph.

  • Open Access

    Weighted pebbling numbers on graphs

    by Stephanie Jones, Joshua D. Laison, Cameron McLeman, Kathryn Nyman

    We expand the theory of pebbling to graphs with weighted edges. In a weighted pebbling game, one player distributes a set amount of weight on the edges of a graph and his opponent chooses a target vertex and places a configuration of pebbles on the vertices. Player one wins if, through a series of pebbling moves, he can move at least one pebble to the target. A pebbling move of p pebbles across an edge with weight w leaves the floor of pw pebbles on the next vertex. We find the weighted pebbling numbers of stars, graphs with at least 2|V|-1 edges, and trees with given targets. We give an explicit formula for the minimum total weight required on the edges of a length-2 path, solvable with p pebbles and exhibit a graph which requires an edge with weight 1/3 in order to achieve its weighted pebbling number.

  • Open Access

    Two-player envy-free multi-cake division

    by John Cloutier, Kathryn L. Nyman, Francis Edward Su

    We introduce a generalized cake-cutting problem in which we seek to divide multiple cakes so that two players may get their most-preferred piece selections: a choice of one piece from each cake, allowing for the possibility of linked preferences over the cakes. For two players, we show that disjoint envy-free piece selections may not exist for two cakes cut into two pieces each, and they may not exist for three cakes cut into three pieces each. However, there do exist such divisions for two cakes cut into three pieces each, and for three cakes cut into four pieces each. The resulting allocations of pieces to players are Pareto-optimal with respect to the division. We use a generalization of Sperner's lemma on the polytope of divisions to locate solutions to our generalized cake-cutting problem.

  • Open Access

    Annihilators of permutation modules

    by Stephen Doty, Kathryn Nyman

    Permutation modules are fundamental in the representation theory of symmetric groups $\Sym_n$ and their corresponding Iwahori--Hecke algebras $\He = \He(\Sym_n)$. We find an explicit combinatorial basis for the annihilator of a permutation module in the "integral" case -- showing that it is a cell ideal in G.E. Murphy's cell structure of $\He$. The same result holds whenever $\He$ is semisimple, but may fail in the non-semisimple case.