Top 10 Arxiv Papers Today in Combinatorics


2.007 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 7
Total Words: 10315
Unqiue Words: 1739

2.001 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

1.998 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 8950
Unqiue Words: 1699

1.998 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 9083
Unqiue Words: 2149

1.998 Mikeys
#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
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 10183
Unqiue Words: 1492

1.998 Mikeys
#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
Figures
Tweets
mathCObot: Daoji Huang : An Affine Analogue of Fulton's Ideals for Matrix Schubert Variety https://t.co/VzxsTvi5hs https://t.co/FjzekILqKK
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3401
Unqiue Words: 788

1.998 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 12836
Unqiue Words: 2862

1.998 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5321
Unqiue Words: 1040

1.998 Mikeys
#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
Figures
None.
Tweets
mathCObot: Xiwang Cao, Keqin Feng : Uniform mixing on abelian Cayley graphs https://t.co/Opqq85evzq https://t.co/Quk69Bg6rm
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8479
Unqiue Words: 1989

1.998 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

About

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
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 225,776 papers.