Top 10 Arxiv Papers Today in Combinatorics

#1. Sets in $\mathbb{R}^d$ determining $k$ taxicab distances
Vajresh Balaji, Olivia Edwards, Anne Marie Loftin, Solomon Mcharo, Lo Phillips, Alex Rice, Bineyam Tsegaye
We address an analog of a problem introduced by Erd\H{o}s and Fishburn, itself an inverse formulation of the famous Erd\H{o}s distance problem, in which the usual Euclidean distance is replaced with the metric induced by the $\ell^1$-norm, commonly referred to as the $\textit{taxicab metric}$. Specifically, we investigate the following question: given $d,k\in \mathbb{N}$, what is the maximum size of a subset of $\mathbb{R}^d$ that determines at most $k$ distinct taxicab distances, and can all such optimal arrangements be classified? We completely resolve the question in dimension $d=2$, as well as the $k=1$ case in dimension $d=3$, and we also provide a full resolution in the general case under an additional hypothesis.
more | pdf | html
Tweets
bvajresh: One of the papers I worked on this summer is up on arXiv. Can't wait to see it in a journal! https://t.co/t4CxdbC2ly
mathMGb: Vajresh Balaji, Olivia Edwards, Anne Marie Loftin, Solomon Mcharo, Lo Phillips, Alex Rice, Bineyam Tsegaye : Sets in $\mathbb{R}^d$ determining $k$ taxicab distances https://t.co/ccUCENSGjx https://t.co/ZMtfmuhqnV
None.
None.
Other stats
Sample Sizes : None.
Authors: 7
Total Words: 10315
Unqiue Words: 1739

#2. What is the Perfect Shuffle?
James Enouen
When shuffling a deck of cards, one probably wants to make sure it is thoroughly shuffled. A way to do this is by sifting through the cards to ensure that no adjacent cards are the same number, because surely this is a poorly shuffled deck. Unfortunately, human intuition for probability tends to lead us astray. For a standard 52-card deck of playing cards, the event is actually extremely likely. This report will attempt to elucidate how to answer this surprisingly difficult combinatorial question directly using rook polynomials.
more | pdf | html
None.
Tweets
toyo9: 題名がストレートですね。ルーク多項式というのを使うみたいです。 What is the Perfect Shuffle? https://t.co/O5OMydSess
mathCObot: James Enouen : What is the Perfect Shuffle? https://t.co/xqbcuiv62o https://t.co/Ou7OfUvX3x
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

#3. Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs
Charlotte Knierim, Maxime Larcher, Anders Martinsson, Andreas Noever
Haj\'os conjectured in 1968 that every Eulerian graph can be decomposed into at most $\lfloor (n-1)/2\rfloor$ edge-disjoint cycles. This has been confirmed for some special graph classes, but the general case remains open. In a sequence of papers by Bienia and Meyniel (1986), Dean (1986), and Bollob\'as and Scott (1996) it was analogously conjectured that every \emph{directed} Eulerian graph can be decomposed into $O(n)$ cycles. In this paper, we show that every directed Eulerian graph can be decomposed into at most $O(n \log \Delta)$ disjoint cycles, thus making progress towards the conjecture by Bollob\'as and Scott. Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least $1$, there exists a cycle with weight at least $\Omega(\log \log n/{\log n})$, thus resolving a question by Bollob\'as and Scott.
more | pdf | html
None.
Tweets
mathCObot: Charlotte Knierim, Maxime Larcher, Anders Martinsson, Andreas Noever : Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs https://t.co/U4hgFPCmsU https://t.co/vEjFX2b3ip
None.
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 8950
Unqiue Words: 1699

#4. On random stable matchings: cyclic matchings with strict preferences and two-side matchings with partially ordered preferences
Boris Pittel
Consider a cyclically ordered collection of $r$ equinumerous agent sets with strict preferences of every agent over the agents from the next agent set. A weakly stable cyclic matching is a partition of the set of agents into disjoint union of $r$-long cycles, one agent from each set per cycle, such that there are no destabilizing $r$-long cycles, i.e. cycles in which every agent strictly prefers its successor to its successor in the matching. Assuming that the preferences are uniformly random and independent, we show that the expected number of stable matchings grows with $n$ (cardinality of each agent set) as $(n\log n)^{r-1}$. We also consider a bipartite stable matching problem where preference list of each agent forms a partially ordered set. Each partial order is an intersection of several, $k_i$ for side $i$, independent, uniformly random, strict orders. For $k_1+k_2>2$, the expected number of stable matchings is analyzed for three, progressively stronger, notions of stability. The expected number of weakly stable matchings...
more | pdf | html
None.
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 9083
Unqiue Words: 2149

#5. Double Affine Bruhat Order
Amanda Welch
We classify cocovers and covers of a given element of the double affine Weyl semigroup W with respect to the Bruhat order, specifically when W is associated to a finite root system that is irreducible and simply laced. We show two approaches: one extending the work of Lam and Shimozono, and its strengthening by Milicevic, where cocovers are characterized in the affine case using the quantum Bruhat graph of the finite Weyl group, and another, which takes a more geometrical approach by using the length difference set defined by Muthiah and Orr.
more | pdf | html
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 10183
Unqiue Words: 1492

#6. An Affine Analogue of Fulton's Ideals for Matrix Schubert Variety
Daoji Huang
We give an affine analogue of Fulton's generators for ideals defining matrix Schubert varieties described in terms of essential sets, in the affine case by considering infinite periodic matrices. This provides a tool for computing with Schubert varieties in the affine flag variety of type A.
more | pdf | html
Tweets
mathCObot: Daoji Huang : An Affine Analogue of Fulton's Ideals for Matrix Schubert Variety https://t.co/VzxsTvi5hs https://t.co/FjzekILqKK
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3401
Unqiue Words: 788

#7. Partitionable sets, almost partitionable sets and their applications
Yanxun Chang, Simone Costa, Tao Feng, Xiaomiao Wang
This paper introduces almost partitionable sets to generalize the known concept of partitionable sets. These notions provide a unified frame to construct $\mathbb{Z}$-cyclic patterned starter whist tournaments and cyclic balanced sampling plans excluding contiguous units. The existences of partitionable sets and almost partitionable sets are investigated. As an application, a large number of maximum or maximal optical orthogonal codes are constructed. These maximal optical orthogonal codes fail to be maximum for just one codeword.
more | pdf | html
None.
None.
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 12836
Unqiue Words: 2862

#8. Bases for Quotients of Symmetric Polynomials
Andrew Weinfeld
We create several families of bases for the symmetric polynomials. From these bases we prove that certain Schur symmetric polynomials form a basis for quotients of symmetric polynomials that generalize the cohomology and the quantum cohomology of the Grassmannian. Our work also provides an alternative proof of a result due to Grinberg.
more | pdf | html
None.
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5321
Unqiue Words: 1040

#9. Uniform mixing on abelian Cayley graphs
Xiwang Cao, Keqin Feng
In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. In 2003, Childs et al. found a graph in which the continuous-time quantum walk spreads exponentially faster than any classical algorithm for a certain black-box problem. Since then, there are extensive explorations on quantum walks on graphs. Among them, uniform mixing provides a uniform probability distribution of information over time which attracts a special attention. However, there are only a few known examples of graphs which admit uniform mixing. In this paper, we give a characterization of abelian Cayley graphs having uniform mixing. Some concrete constructions of such graphs are provided. Particularly, for cubelike graphs, it is shown that the Cayley graph ${\rm Cay}(\mathbb{F}_2^{2k};S)$ having uniform mixing if and only if $f$ is a bent function, where $f$ is the characteristic function of $S$.
more | pdf | html
None.
Tweets
mathCObot: Xiwang Cao, Keqin Feng : Uniform mixing on abelian Cayley graphs https://t.co/Opqq85evzq https://t.co/Quk69Bg6rm
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8479
Unqiue Words: 1989

#10. Lattice Points in the Newton Polytopes of Key Polynomials
Neil J. Y. Fan, Peter L. Guo, Simon C. Y. Peng, Sophie C. C. Sun
We confirm a conjecture of Monical, Tokcan and Yong on a characterization of the lattice points in the Newton polytopes of key polynomials.
more | pdf | html
None.
Tweets
mathCObot: Neil J.Y. Fan, Peter L. Guo, Simon C.Y. Peng, Sophie C.C. Sun : Lattice Points in the Newton Polytopes of Key Polynomials https://t.co/6zJ58iL6KS https://t.co/zfkYJQH2ky
None.
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 225,776 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
Stats
Tracking 225,776 papers.