### Top 10 Arxiv Papers Today in Combinatorics

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7751
Unqiue Words: 1213

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11984
Unqiue Words: 2104

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 10101
Unqiue Words: 2252

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 4733
Unqiue Words: 1061

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11416
Unqiue Words: 2169

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 1708
Unqiue Words: 581

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6014
Unqiue Words: 1276

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11564
Unqiue Words: 1812

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 5
Total Words: 4332
Unqiue Words: 1204

##### #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
None.
###### Tweets
mathCObot: Ivan Mogilnykh : Perfect codes from PGL(2,5) in Star graphs https://t.co/Q2p4jxN7UF https://t.co/WeXyt8V4zK
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3268
Unqiue Words: 766

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
Online
###### Stats
Tracking 99,599 papers.