Zobrazeno 1 - 10
of 995
pro vyhledávání: '"DAVENPORT-Schinzel sequences"'
Autor:
NIVASCH, GABRIEL1 gabriel.nivasch@inf.ethz.ch
Publikováno v:
Journal of the ACM. Mar2010, Vol. 57 Issue 3, p17:1-17:44. 44p. 3 Diagrams.
Autor:
PETTIE, SETH1 pettie@umich.edu
Publikováno v:
Journal of the ACM. Oct2015, Vol. 62 Issue 5, p36-36:40. 40p.
Let $up(r, t) = (a_1 a_2 \dots a_r)^t$. We investigate the problem of determining the maximum possible integer $n(r, t)$ for which there exist $2t-1$ permutations $\pi_1, \pi_2, \dots, \pi_{2t-1}$ of $1, 2, \dots, n(r, t)$ such that the concatenated
Externí odkaz:
http://arxiv.org/abs/1909.10330
Autor:
Geneson, Jesse
For any sequence $u$, the extremal function $Ex(u, j, n)$ is the maximum possible length of a $j$-sparse sequence with $n$ distinct letters that avoids $u$. We prove that if $u$ is an alternating sequence $a b a b \dots$ of length $s$, then $Ex(u, j,
Externí odkaz:
http://arxiv.org/abs/1810.07175
Autor:
Wellman, Julian, Pettie, Seth
An order-$s$ Davenport-Schinzel sequence over an $n$-letter alphabet is one avoiding immediate repetitions and alternating subsequences with length $s+2$. The main problem is to determine the maximum length of such a sequence, as a function of $n$ an
Externí odkaz:
http://arxiv.org/abs/1610.09774
Autor:
Wellman, Julian, Pettie, Seth
Publikováno v:
In Discrete Mathematics July 2018 341(7):1987-1993
Autor:
Pettie, Seth
We present new, and mostly sharp, bounds on the maximum length of certain generalizations of Davenport-Schinzel sequences. Among the results are sharp bounds on order-$s$ {\em double DS} sequences, for all $s$, sharp bounds on sequences avoiding {\em
Externí odkaz:
http://arxiv.org/abs/1401.5709
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Pettie, Seth
One of the longest-standing open problems in computational geometry is to bound the lower envelope of $n$ univariate functions, each pair of which crosses at most $s$ times, for some fixed $s$. This problem is known to be equivalent to bounding the l
Externí odkaz:
http://arxiv.org/abs/1204.1086
Autor:
Wong, Kok Bin, Ku, Cheng Yeaw
Let $[n]=\{1, \ldots, n\}$. A sequence $u=a_1a_2\dots a_l$ over $[n]$ is called $k$-sparse if $a_i = a_j$, $i > j$ implies $i-j\geq k$. In other words, every consecutive subsequence of $u$ of length at most $k$ does not have letters in common. Let $u
Externí odkaz:
http://arxiv.org/abs/1311.1594