Top 10 Arxiv Papers Today in Combinatorics

#1. Central limit theorems for patterns in multiset permutations and set partitions
Valentin Féray
We use the recently developed method of weighted dependency graphs to prove central limit theorems for the number of occurrences of any fixed pattern in multiset permutations and in set partitions. This generalizes results for patterns of size 2 in both settings, obtained by Canfield, Janson and Zeilberger and Chern, Diaconis, Kane and Rhoades, respectively.
more | pdf | html
None.
Tweets
mathCObot: Valentin Féray : Central limit theorems for patterns in multiset permutations and set partitions https://t.co/SjNvV6jErG https://t.co/CaZ9vj18HE
MathPaper: Central limit theorems for patterns in multiset permutations and set partitions. https://t.co/FUuHp9ccqK
elcaborotativo: RT @mathCObot: Valentin Féray : Central limit theorems for patterns in multiset permutations and set partitions https://t.co/SjNvV6jErG htt…
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 18517
Unqiue Words: 3208

#2. Crystal constructions in Number Theory
Anna Puskás
Weyl group multiple Dirichlet series and metaplectic Whittaker functions can be described in terms of crystal graphs. We present crystals as parameterized by Littelmann patterns and we give a survey of purely combinatorial constructions of prime power coefficients of Weyl group multiple Dirichlet series and metaplectic Whittaker functions using the language of crystal graphs. We explore how the branching structure of crystals manifests in these constructions, and how it allows access to some intricate objects in number theory and related open questions using tools of algebraic combinatorics.
more | pdf | html
None.
Tweets
MathPaper: Crystal constructions in Number Theory. https://t.co/wVPyPBFeRk
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 12764
Unqiue Words: 2576

#3. Zeros of the Möbius function of permutations
Robert Brignall, Vít Jelínek, Jan Kynčl, David Marchant
We show that if a permutation $\pi$ contains two intervals of length 2, where one interval is an ascent and the other a descent, then the M\"{o}bius function $\mu[\pi]$ of the interval $[1,\pi]$ is zero. As a consequence, we show that the proportion of permutations of length $n$ with principal M\"{o}bius function equal to zero is asymptotically bounded below by $(1-1/e)^2\ge 0.3995$. This is the first result determining the value of $\mu[1,\pi]$ for an asymptotically positive proportion of permutations $\pi$. We also show that if a permutation $\phi$ can be expressed as a direct sum of the form $\alpha \oplus 1 \oplus \beta$, then any permutation $\pi$ containing an interval order-isomorphic to $\phi$ has $\mu[1, \pi]=0$; we deduce this from a more general result showing that $\mu [\sigma, \pi]=0$ whenever $\pi$ contains an interval of a certain form. Finally, we show that if a permutation $\pi$ contains intervals isomorphic to certain pairs of permutations, or to certain permutations of length six, then $\mu[1, \pi] = 0$.
more | pdf | html
None.
Tweets
MathPaper: Zeros of the M\"{o}bius function of permutations. https://t.co/NNAjBV6MhM
Priceeqn: RT @MathPaper: Zeros of the M\"{o}bius function of permutations. https://t.co/NNAjBV6MhM
None.
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9593
Unqiue Words: 1725

#4. Reciprocals of exponential polynomials and permutation enumeration
Ira M. Gessel
We show that the reciprocal of a partial sum with 2m terms of the alternating exponential series is the exponential generating function for permutations in which every increasing run has length congruent to 0 or 1 modulo 2m. More generally we study polynomials whose reciprocals are exponential generating functions for permutations whose run lengths are restricted to certain congruence classes, and extend these results to noncommutative symmetric functions that count words with the same restrictions on run lengths.
more | pdf | html
None.
Tweets
sigfpe: exp(-x)⁻¹ = exp(x) So (1-x+x²/2!-…)⁻¹ = 1+x+x²/x!+… What happens to RHS when you use *partial* sum on left? This paper finds nice combinatorial interpretation of coefficients you get on right. https://t.co/j1qOl92wT2 https://t.co/AWo2M84SKj
mathCObot: Ira M. Gessel : Reciprocals of exponential polynomials and permutation enumeration https://t.co/aWP9XtdL2d
None.
None.
Other stats
Sample Sizes : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Authors: 1
Total Words: 2416
Unqiue Words: 718

#5. A combinatorial classification of 2-regular simple modules for Nakayama algebras
Rene Marczinzik, Martin Rubey, Christian Stump
We discuss combinatorial interpretations of several homological properties of Nakayama algebras in terms of Dyck path statistics. We thereby classify and enumerate various classes of Nakayama algebras. Most importantly, we classify their 2-regular simple modules, corresponding to exact structures on the category of projective modules. We also classify 1-regular simple modules, quasi-hereditary Nakayama algebras and Nakayama algebras of global dimension at most two. As it turns out, most classes are enumerated by well-known combinatorial sequences, such as Fibonacci, Riordan and Narayana numbers. We first obtain interpretations in terms of the Auslander-Reiten quiver of the algebra using homological algebra. Then, we apply suitable bijections to relate these to combinatorial statistics on Dyck paths.
more | pdf | html
None.
Tweets
mathCObot: Rene Marczinzik, Martin Rubey, Christian Stump : A combinatorial classification of 2-regular simple modules for Nakayama algebras https://t.co/N0VtaAIID5 https://t.co/KHP12lBsyP
MathPaper: A combinatorial classification of 2-regular simple modules for Nakayama algebras. https://t.co/ftNTobPsSp
None.
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 13457
Unqiue Words: 2295

#6. The Active Bijection 2.b - Decomposition of activities for oriented matroids, and general definitions of the active bijection
Emeric Gioan, Michel Las Vergnas
The active bijection for oriented matroids (and real hyperplane arrangements, and graphs, as particular cases) is introduced and investigated by the authors in a series of papers. Given any oriented matroid defined on a linearly ordered ground set, we exhibit one particularit\'e of its bases, which we call its active basis, with remarkable properties. It preserves activities (for oriented matroids in the sense of Las Vergnas, for matroid bases in the sense of Tutte), as well as some active partitions of the ground set associated with oriented matroids and matroid bases. It yields a canonical bijection between classes of reorientations and bases [...]. It also yields a refined bijection between all reorientations and subsets of the ground set. Those bijections are related to various Tutte polynomial expressions [...]. They contain various noticeable bijections involving orientations/signatures/reorientations and spanning trees/simplices/bases of a graph/real hyperplane arrangement/oriented matroid. [...] In previous papers of...
more | pdf | html
None.
Tweets
mathCObot: Emeric Gioan, Michel Las Vergnas : The Active Bijection 2.b - Decomposition of activities for oriented matroids, and general definitions of the active bijection https://t.co/zttSGGbq0V
MathPaper: The Active Bijection 2.b - Decomposition of activities for oriented matroids, and general definitions of the active bijection. https://t.co/9n6MLD0UEP
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 30909
Unqiue Words: 3685

#7. Monochromatic cycle partitions in random graphs
Richard Lang, Allan Lo
Erd\H{o}s, Gy\'arf\'as and Pyber showed that every $r$-edge-coloured complete graph $K_n$ can be covered by $25 r^2 \log r$ vertex-disjoint monochromatic cycles (independent of $n$). Here, we extend their result to the setting of binomial random graphs. That is, we show that if $p = p(n) \geq \Omega(n^{-1/(2r)})$, then with high probability any $r$-edge-coloured $G(n,p)$ can be covered by at most $1000 r^4 \log r$ vertex-disjoint monochromatic cycles. This answers a question of Kor\'andi, Mousset, Nenadov, \v{S}kori\'{c} and Sudakov.
more | pdf | html
None.
Tweets
mathCObot: Richard Lang, Allan Lo : Monochromatic cycle partitions in random graphs https://t.co/Lab0IYC8bT
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8808
Unqiue Words: 1739

#8. $(k,λ)$-Anti-Powers and Other Patterns in Words
Amanda Burcroff
Given a word, we are interested in the structure of its contiguous subwords split into $k$ blocks of equal length, especially in the homogeneous and anti-homogeneous cases. We introduce the notion of $(\mu_1,\dots,\mu_k)$-block-patterns, words of the form $w = w_1\cdots w_k$ where, when $\{w_1,\dots,w_k\}$ is partitioned via equality, there are $\mu_s$ sets of size $s$ for each $s \in \{1,\dots,k\}$. This is a generalization of the well-studied $k$-powers and the $k$-anti-powers recently introduced by Fici, Restivo, Silva, and Zamboni, as well as a refinement of the $(k,\lambda)$-anti-powers introduced by Defant. We generalize the anti-Ramsey-type results of Fici et al. to $(\mu_1,\dots,\mu_k)$-block-patterns and improve their bounds on $N_\alpha(k,k)$, the minimum length such that every word of length $N_\alpha(k,k)$ on an alphabet of size $\alpha$ contains a $k$-power or $k$-anti-power. We also generalize their results on infinite words avoiding $k$-anti-powers to the case of $(k,\lambda)$-anti-powers. We provide a few results...
more | pdf | html
Tweets
MathPaper: $(k,\lambda)$-Anti-Powers and Other Patterns in Words. https://t.co/HtrJzXHoM1
mathCObot: Amanda Burcroff : $(k,λ)$-Anti-Powers and Other Patterns in Words https://t.co/qGFXXKQ4Gq
None.
None.
Other stats
Sample Sizes : [1, 1, 1, 1, 1, 1, 1, 1]
Authors: 1
Total Words: 8391
Unqiue Words: 1614

#9. Remark on Barnette's Conjecture
Jan Florek
Barnette's conjecture states that every cubic $3$-connected bipartite plane graph is hamiltonian. We show that if such a graph possesses a $2$-factor ${\cal F }$ which consists only of facial $4$-cycles, then the following properties are satisfied: (1) If two faces have a common edge which is not in ${\cal F }$, there is a Hamilton cycle containing all edges of the first face, except this edge, and avoiding all edges of the second face which are not in ${\cal F }$. (2) If an edge is chosen on a face, there is a Hamilton cycle containing all other edges of this face.
more | pdf | html
None.
Tweets
mathCObot: Jan Florek : Remark on Barnette's Conjecture https://t.co/mmdT3KD1AB
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 1836
Unqiue Words: 558

#10. Uniquely restricted matchings in subcubic graphs without short cycles
Maximilian Fürst, Dieter Rautenbach
A matching $M$ in a graph $G$ is uniquely restricted if no other matching in $G$ covers the same set of vertices. We prove that any connected subcubic graph with $n$ vertices and girth at least $5$ contains a uniquely restricted matching of size at least $(n-1) / 3$ except for two exceptional cubic graphs of order $14$ and $20$.
more | pdf | html
None.
Tweets
MathPaper: Uniquely restricted matchings in subcubic graphs without short cycles. https://t.co/wctYvAThZw
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7561
Unqiue Words: 951

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 72,995 papers.

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