Source author record

Danny Rorabaugh

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

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Density dichotomy in random words

Word $W$ is said to encounter word $V$ provided there is a homomorphism $ϕ$ mapping letters to nonempty words so that $ϕ(V)$ is a substring of $W$ . For example, taking $ϕ$ such that $ϕ(h)=c$ and $ϕ(u)=ien$ , we see that "science" encounters "huh" since $cienc=ϕ(huh)$ . The density of $V$ in $W$ , $δ(V,W)$ , is the proportion of substrings of $W$ that are homomorphic images of $V$ . So the density of "huh" in "science" is $2/{8 \choose 2}$ . A word is doubled if every letter that appears in the word appears at least twice. The dichotomy: Let $V$ be a word over any alphabet, $Σ$ a finite alphabet with at least 2 letters, and $W_n \in Σ^n$ chosen uniformly at random. Word $V$ is doubled if and only if $\mathbb{E}(δ(V,W_n)) \rightarrow 0$ as $n \rightarrow \infty$ . We further explore convergence for nondoubled words and concentration of the limit distribution for doubled words around its mean.

preprint2016arXiv

Regular colorings and factors of regular graphs

An $(r-1,1)$ -coloring of an $r$ -regular graph $G$ is an edge coloring such that each vertex is incident to $r-1$ edges of one color and $1$ edge of a different color. In this paper, we completely characterize all $4$ -regular pseudographs (graphs that may contain parallel edges and loops) which do not have a $(3,1)$ -coloring. An $\{r-1,1\}$ -factor of an $r$ -regular graph is a spanning subgraph in which each vertex has degree either $r-1$ or $1$ . We prove various conditions that that must hold for any vertex-minimal $5$ -regular pseudographs without $(4,1)$ -colorings or without $\{4,1\}$ -factors. Finally, for each $r\geq 6$ we construct graphs that are not $(r-1,1)$ -colorable and, more generally, are not $(r-t,t)$ -colorable for small $t$ .

preprint2015arXiv

Toward the Combinatorial Limit Theory of Free Words

Free words are elements of a free monoid, generated over an alphabet via the binary operation of concatenation. Casually speaking, a free word is a finite string of letters. Henceforth, we simply refer to them as words. Motivated by recent advances in the combinatorial limit theory of graphs-notably those involving flag algebras, graph homomorphisms, and graphons-we investigate the extremal and asymptotic theory of pattern containment and avoidance in words. Word V is a factor of word W provided V occurs as consecutive letters within W. W is an instance of V provided there exists a nonerasing monoid homomorphsism ϕ with ϕ(V) = W. For example, using the homomorphism ϕ defined by ϕ(P) = Ror, ϕ(h) = a, and ϕ(D) = baugh, we see that Rorabaugh is an instance of PhD. W avoids V if no factor of W is an instance of V. V is unavoidable provided, over any finite alphabet, there are only finitely many words that avoid V. Unavoidable words were classified by Bean, Ehrenfeucht, and McNulty (1979) and Zimin (1982). We briefly address the following Ramsey-theoretic question: For unavoidable word V and a fixed alphabet, what is the longest a word can be that avoids V? The density of V in W is the proportion of nonempty substrings of W that are instances of V. Since there are 45 substrings in Rorabaugh and 28 of them are instances of PhD, the density of PhD in Rorabaugh is 28/45. We establish a number of asymptotic results for word densities, including the expected density of a word in arbitrarily long, random words and the minimum density of an unavoidable word over arbitrarily long words. This is joint work with Joshua Cooper.

preprint2014arXiv

A bound on a convexity measure for point sets

A planar point set is in convex position precisely when it has a convex polygonization, that is, a polygonization with maximum interior angle measure at most π. We can thus talk about the convexity of a set of points in terms of the minimum, taken over all polygonizations, of the maximum interior angle. The main result presented here is a nontrivial combinatorial upper bound of this min-max value in terms of the number of points in the set. Motivated by a particular construction, we also pose a natural conjecture for the best upper bound.

preprint2014arXiv

Bounds on Zimin Word Avoidance

How long can a word be that avoids the unavoidable? Word $W$ encounters word $V$ provided there is a homomorphism $ϕ$ defined by mapping letters to nonempty words such that $ϕ(V)$ is a subword of $W$ . Otherwise, $W$ is said to avoid $V$ . If, on any arbitrary finite alphabet, there are finitely many words that avoid $V$ , then we say $V$ is unavoidable. Zimin (1982) proved that every unavoidable word is encountered by some word $Z_n$ , defined by: $Z_1 = x_1$ and $Z_{n+1} = Z_n x_{n+1} Z_n$ . Here we explore bounds on how long words can be and still avoid the unavoidable Zimin words.

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.