Source author record

J. T. Geneson

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Bounding sequence extremal functions with formations

An $(r, s)$ -formation is a concatenation of $s$ permutations of $r$ letters. If $u$ is a sequence with $r$ distinct letters, then let $\mathit{Ex}(u, n)$ be the maximum length of any $r$ -sparse sequence with $n$ distinct letters which has no subsequence isomorphic to $u$ . For every sequence $u$ define $\mathit{fw}(u)$ , the formation width of $u$ , to be the minimum $s$ for which there exists $r$ such that there is a subsequence isomorphic to $u$ in every $(r, s)$ -formation. We use $\mathit{fw}(u)$ to prove upper bounds on $\mathit{Ex}(u, n)$ for sequences $u$ such that $u$ contains an alternation with the same formation width as $u$ . We generalize Nivasch's bounds on $\mathit{Ex}((ab)^{t}, n)$ by showing that $\mathit{fw}((12 \ldots l)^{t})=2t-1$ and $\mathit{Ex}((12\ldots l)^{t}, n) =n2^{\frac{1}{(t-2)!}α(n)^{t-2}\pm O(α(n)^{t-3})}$ for every $l \geq 2$ and $t\geq 3$ , such that $α(n)$ denotes the inverse Ackermann function. Upper bounds on $\mathit{Ex}((12 \ldots l)^{t} , n)$ have been used in other papers to bound the maximum number of edges in $k$ -quasiplanar graphs on $n$ vertices with no pair of edges intersecting in more than $O(1)$ points. If $u$ is any sequence of the form $a v a v' a$ such that $a$ is a letter, $v$ is a nonempty sequence excluding $a$ with no repeated letters and $v'$ is obtained from $v$ by only moving the first letter of $v$ to another place in $v$ , then we show that $\mathit{fw}(u)=4$ and $\mathit{Ex}(u, n) =Θ(nα(n))$ . Furthermore we prove that $\mathit{fw}(abc(acb)^{t})=2t+1$ and $\mathit{Ex}(abc(acb)^{t}, n) = n2^{\frac{1}{(t-1)!}α(n)^{t-1}\pm O(α(n)^{t-2})}$ for every $t\geq 2$ .

preprint2014arXiv

On k-visibility graphs

We examine several types of visibility graphs in which sightlines can pass through $k$ objects. For $k \geq 1$ we bound the maximum thickness of semi-bar $k$ -visibility graphs between $\lceil \frac{2}{3} (k + 1) \rceil$ and $2k$ . In addition we show that the maximum number of edges in arc and circle $k$ -visibility graphs on $n$ vertices is at most $(k+1)(3n-k-2)$ for $n > 4k+4$ and ${n \choose 2}$ for $n \leq 4k+4$ , while the maximum chromatic number is at most $6k+6$ . In semi-arc $k$ -visibility graphs on $n$ vertices, we show that the maximum number of edges is ${n \choose 2}$ for $n \leq 3k+3$ and at most $(k+1)(2n-\frac{k+2}{2})$ for $n > 3k+3$ , while the maximum chromatic number is at most $4k+4$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.