Top 10 Arxiv Papers Today in Combinatorics


2.008 Mikeys
#1. Graphs avoiding immersion of K_{3,3}
Zdeněk Dvořák, Michal Hruška
DeVos and Malekian gave a structural description of graphs avoiding an immersion of K_{3,3}, showing that all such graphs are composed over small edge-cuts from graphs with at most 8 vertices and from 3-regular planar graphs. We provide another proof of this fact, simpler in some aspects.
more | pdf | html
Figures
None.
Tweets
mathCObot: Zdeněk Dvořák, Michal Hruška : Graphs avoiding immersion of K_{3,3} https://t.co/EIEUnLzgYT https://t.co/Sy4eVi41HZ
MathPaper: Graphs avoiding immersion of K_{3,3}. https://t.co/nySyv7ukDu
Derektionary: RT @MathPaper: Graphs avoiding immersion of K_{3,3}. https://t.co/nySyv7ukDu
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7751
Unqiue Words: 1213

2.005 Mikeys
#2. A Dirac-type theorem for Berge cycles in random hypergraphs
Dennis Clemens, Julia Ehrenmüller, Yury Person
A Hamilton Berge cycle of a hypergraph on $n$ vertices is an alternating sequence $(v_1, e_1, v_2, \ldots, v_n, e_n)$ of distinct vertices $v_1, \ldots, v_n$ and distinct hyperedges $e_1, \ldots, e_n$ such that $\{v_1,v_n\}\subseteq e_n$ and $\{v_i, v_{i+1}\} \subseteq e_i$ for every $i\in [n-1]$. We prove the following Dirac-type theorem about Berge cycles in the binomial random $r$-uniform hypergraph $H^{(r)}(n,p)$: for every integer $r \geq 3$, every real $\gamma>0$ and $p \geq \frac{\ln^{17r} n}{n^{r-1}}$ asymptotically almost surely, every spanning subgraph $H \subseteq H^{(r)}(n,p)$ with minimum vertex degree $\delta_1(H) \geq \left(\frac{1}{2^{r-1}} + \gamma\right) p \binom{n}{r-1}$ contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on $p$ is optimal up to some polylogarithmic factor.
more | pdf | html
Figures
None.
Tweets
mathCObot: Dennis Clemens, Julia Ehrenmüller, Yury Person : A Dirac-type theorem for Berge cycles in random hypergraphs https://t.co/jaPrJMDbSv https://t.co/eDOkmSGweq
MathPaper: A Dirac-type theorem for Berge cycles in random hypergraphs. https://t.co/PRpVIQ4O6k
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11984
Unqiue Words: 2104

2.005 Mikeys
#3. Counting 3-Stack-Sortable Permutations
Colin Defant
We prove a "Decomposition Lemma" that allows us to count preimages of certain sets of permutations under West's stack-sorting map $s$. As a first application, we give a new proof of Zeilberger's formula for the number of 2-stack-sortable permutations in $S_n$. Our proof generalizes, allowing us to find an algebraic equation satisfied by the generating function that counts 2-stack-sortable permutations according to length, number of descents, and number of peaks. This is the first proof of this formula that generalizes to 3-stack-sortable permutations. Indeed, the same method yields a recurrence relation for $W_3(n)$, the number of 3-stack-sortable permutations in $S_n$. Hence, we obtain the first polynomial-time algorithm for computing these numbers. We compute $W_3(n)$ for $1\le n\le 174$, extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for $\lim_{n\to\infty}W_3(n)^{1/n}$. Our computations allow us to disprove a conjecture of B\'ona, although we do not yet know for...
more | pdf | html
Figures
None.
Tweets
mathCObot: Colin Defant : Counting 3-Stack-Sortable Permutations https://t.co/bwUvrCv8em https://t.co/RDeW9yNZjo
MathPaper: Counting 3-Stack-Sortable Permutations. https://t.co/Cp0lm3k0ud
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 10101
Unqiue Words: 2252

2.005 Mikeys
#4. On transversal and 2-packing numbers in uniform linear systems
Carlos A. Alfaro, G. Araujo-Pardo, C. Rubio-Motiel, Adrián Vázquez-Ávila
A linear system is a pair $(P,\mathcal{L})$ where $\mathcal{L}$ is a family of subsets on a ground finite set $P$, such that $|l\cap l^\prime|\leq 1$, for every $l,l^\prime \in \mathcal{L}$. The elements of $P$ and $\mathcal{L}$ are called points and lines, respectively, and the linear system is called intersecting if any pair of lines intersect in exactly one point. A subset $T$ of points of $P$ is a transversal of $(P,\mathcal{L})$ if $T$ intersects any line, and the transversal number, $\tau(P,\mathcal{L})$, is the minimum order of a transversal. On the other hand, a 2-packing set of a linear system $(P,\mathcal{L})$ is a set $R$ of lines, such that any three of them have a common point, then the 2-packing number of $(P,\mathcal{L})$, $\nu_2(P,\mathcal{L})$, is the size of a maximum 2-packing set. It is known that the transversal number $\tau(P,\mathcal{L})$ is bounded above by a quadratic function of $\nu_2(P,\mathcal{L})$. An open problem is to haracterize the families of linear systems which satisfies...
more | pdf | html
Figures
None.
Tweets
mathCObot: Carlos A. Alfaro, G. Araujo-Pardo, C. Rubio-Motiel, Adrián Vázquez-Ávila : On transversal and 2-packing numbers in uniform linear systems https://t.co/UzgOCiGBQ3 https://t.co/rSr0FNhYPM
MathPaper: On transversal and 2-packing numbers in uniform linear systems. https://t.co/1PA0OVy722
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 4733
Unqiue Words: 1061

2.005 Mikeys
#5. On partially ordered patterns of length 4 and 5 in permutations
Alice L. L. Gao, Sergey Kitaev
Partially ordered patterns (POPs) generalize the notion of classical patterns studied widely in the literature in the context of permutations, words, compositions and partitions. In an occurrence of a POP, the relative order of some of the elements is not important. Thus, any POP of length $k$ is defined by a partially ordered set on $k$ elements, and classical patterns correspond to $k$-element chains. The notion of a POP provides a convenient language to deal with larger sets of permutation patterns. This paper contributes to a long line of research on classical permutation patterns of length 4 and 5, and beyond, by conducting a systematic search of connections between sequences in the Online Encyclopedia of Integer Sequences (OEIS) and permutations avoiding POPs of length 4 and 5. As the result, we (i) obtain 13 new enumerative results for classical patterns of length 4 and 5, and a number of results for patterns of arbitrary length, (ii) collect under one roof many sporadic results in the literature related to avoidance of...
more | pdf | html
Figures
None.
Tweets
mathCObot: Alice L.L. Gao, Sergey Kitaev : On partially ordered patterns of length 4 and 5 in permutations https://t.co/8Soxnx4NtK https://t.co/rVVeborSvk
MathPaper: On partially ordered patterns of length 4 and 5 in permutations. https://t.co/DrNaqZ2QZQ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11416
Unqiue Words: 2169

2.005 Mikeys
#6. Nonsequenceable Steiner triple systems
Donald L. Kreher, Douglas R. Stinson
A partial Steiner triple system is is $sequenceable$ if the points can be sequenced so that no proper segment can be partitioned into blocks. We show that, if $0 \leq a \leq (n-1)/3$, then there exists a nonsequenceable PSTS$(n)$ of size $\frac{1}{3}\binom{n}{2}-a$, for all $n \equiv 1 \pmod{6}$ except for $n=7$.
more | pdf | html
Figures
None.
Tweets
mathCObot: Donald L. Kreher, Douglas R. Stinson : Nonsequenceable Steiner triple systems https://t.co/D79VTlUArV https://t.co/ElJghr82ii
MathPaper: Nonsequenceable Steiner triple systems. https://t.co/5elZ3t6Knp
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 1708
Unqiue Words: 581

2.005 Mikeys
#7. Some Results On The Flynn-Poonen-Schaefer Conjecture
Shalom Eliahou, Youssef Fares
For $c \in \mathbb{Q}$, consider the quadratic polynomial map $\varphi_c(x)=x^2-c$. Flynn, Poonen and Schaefer conjectured in 1997 that no rational cycle of $\varphi_c$ under iteration has length more than $3$. Here we discuss this conjecture using arithmetic and combinatorial means, leading to three main results. First, we show that if $\varphi_c$ admits a rational cycle of length $n \ge 3$, then the denominator of $c$ must be divisible by $16$. We then provide an upper bound on the number of periodic rational points of $\varphi_c$ in terms of the number of distinct prime factors of the denominator of $c$. Finally, we show that the Flynn-Poonen-Schaefer conjecture holds for $\varphi_c$ if that denominator has at most two distinct prime factors.
more | pdf | html
Figures
None.
Tweets
mathCObot: Shalom Eliahou (LMPA), Youssef Fares (LAMFA) : Some Results On The Flynn-Poonen-Schaefer Conjecture https://t.co/pP8G9gyNLj https://t.co/pCbN1prZXE
MathPaper: Some Results On The Flynn-Poonen-Schaefer Conjecture. https://t.co/6n4LPt7Ihi
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6014
Unqiue Words: 1276

2.005 Mikeys
#8. Permutation patterns in genome rearrangement problems: the reversal model
Giulio Cerbai, Luca Ferrari
In the context of the genome rearrangement problem, we analyze two well known models, namely the reversal and the prefix reversal models, by exploiting the connection with the notion of permutation pattern. More specifically, for any $k$, we provide a characterization of the set of permutations having distance $\leq k$ from the identity (which is known to be a permutation class) in terms of what we call generating peg permutations and we describe some properties of its basis, which allow to compute such a basis for small values of $k$.
more | pdf | html
Figures
None.
Tweets
mathCObot: Giulio Cerbai, Luca Ferrari : Permutation patterns in genome rearrangement problems: the reversal model https://t.co/6XeQBa3swL https://t.co/oQqDoZ0wwE
ComputerPapers: Permutation patterns in genome rearrangement problems: the reversal model. https://t.co/m0veNG39c9
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11564
Unqiue Words: 1812

2.001 Mikeys
#9. Largest 2-regular subgraphs in 3-regular graphs
Ilkyoo Choi, Ringi Kim, Alexandr Kostochka, Boram Park, Douglas B. West
For a graph $G$, let $f_2(G)$ denote the largest number of vertices in a $2$-regular subgraph of $G$. We determine the minimum of $f_2(G)$ over $3$-regular $n$-vertex simple graphs $G$. To do this, we prove that every $3$-regular multigraph with exactly $c$ cut-edges has a $2$-regular subgraph that omits at most $\max\{0,\lfloor (c-1)/2\rfloor\}$ vertices. More generally, every $n$-vertex multigraph with maximum degree $3$ and $m$ edges has a $2$-regular subgraph that omits at most $\max\{0,\lfloor (3n-2m+c-1)/2\rfloor\}$ vertices. These bounds are sharp; we describe the extremal multigraphs.
more | pdf | html
Figures
None.
Tweets
mathCObot: Ilkyoo Choi, Ringi Kim, Alexandr Kostochka, Boram Park, Douglas B. West : Largest 2-regular subgraphs in 3-regular graphs https://t.co/VqfydeVGXr https://t.co/fKOntRGMor
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 4332
Unqiue Words: 1204

2.001 Mikeys
#10. Perfect codes from PGL(2,5) in Star graphs
Ivan Mogilnykh
The Star graph $S_n$ is the Cayley graph of the symmetric group $Sym_n$ with the generating set $\{(1i): 2\leq i\leq n \}$. Arumugam and Kala proved that $\{\pi\in Sym_n: \pi(1)=1\}$ is a perfect code in $S_n$ for any $n, n\geq 3$ \cite{AK}. In this note we show that for any $n, n\geq 6$ the star graph $S_n$ contains a perfect code which is a union of cosets of the embedding of $PGL(2,5)$ into $Sym_6$.
more | pdf | html
Figures
None.
Tweets
mathCObot: Ivan Mogilnykh : Perfect codes from PGL(2,5) in Star graphs https://t.co/Q2p4jxN7UF https://t.co/WeXyt8V4zK
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3268
Unqiue Words: 766

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 99,599 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 99,599 papers.