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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 7751

Unqiue Words: 1213

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.

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.

Sample Sizes : None.

Authors: 3

Total Words: 11984

Unqiue Words: 2104

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.

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.

Sample Sizes : None.

Authors: 1

Total Words: 10101

Unqiue Words: 2252

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.

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.

Sample Sizes : None.

Authors: 4

Total Words: 4733

Unqiue Words: 1061

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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 11416

Unqiue Words: 2169

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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 1708

Unqiue Words: 581

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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 6014

Unqiue Words: 1276

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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 11564

Unqiue Words: 1812

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.

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.

Sample Sizes : None.

Authors: 5

Total Words: 4332

Unqiue Words: 1204

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.

mathCObot:
Ivan Mogilnykh : Perfect codes from PGL(2,5) in Star graphs https://t.co/Q2p4jxN7UF https://t.co/WeXyt8V4zK

None.

None.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible