Source author record

Neal Bushaw

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

ResearcherUnclaimed source record

math.CO math.PR math.DS math.GR

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Rainbow Saturation

We introduce a notion of rainbow saturation and the corresponding rainbow saturation number. This is the saturation version of the rainbow Turán numbers whose systematic study was initiated by Keevash, Mubayi, Sudakov, and Verstraëte. We give examples of graphs for which the rainbow saturation number is bounded away from the ordinary saturation number. This includes all complete graphs $K_n$ for $n\geq 4$ , and several bipartite graphs. It is notable that there are non-bipartite graphs for which this is the case, as this does not happen when it comes to the rainbow extremal number versus the traditional extremal number. We also show that saturation numbers are linear for a large class of graphs, providing a partial rainbow analogue of a well known theorem of Kásonyi and Tuza. We conclude this paper with related open questions and conjectures.

preprint2022arXiv

Rainbow Turán Methods for Trees

The rainbow Turán number, a natural extension of the well studied traditional Turán number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstraëte. The rainbow Turán number of a graph $H$ , $ex^{*}(n,H)$ , is the largest number of edges for an $n$ vertex graph $G$ which can be properly edge colored with no rainbow $H$ subgraph. We explore the reduction method for finding upper bounds on rainbow Turán numbers, and use this to inform results for the rainbow Turán numbers of double stars, caterpillars, and perfect binary trees. In addition, we define $k$ -unique colorings and the related $k$ -unique Turán numbers. We provide preliminary results on this new variant on the classic problem.

preprint2015arXiv

The typical structure of graphs with no large cliques

In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed $r \in \mathbb{N}$ , almost every $n$ -vertex $K_{r+1}$ -free graph is $r$ -partite. In this paper we extend this result to all functions $r = r(n)$ with $r \leqslant (\log n)^{1/4}$ . The proof combines a new (close to sharp) supersaturation version of the Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits.

preprint2014arXiv

Random-step Markov processes

We explore two notions of stationary processes. The first is called a random-step Markov process in which the stationary process of states, $(X_i)_{i \in \mathbb{Z}}$ has a stationary coupling with an independent process on the positive integers, $(L_i)_{i \in \mathbb{Z}}$ of `random look-back distances'. That is, $L_0$ is independent of the `past states', $(X_i, L_i)_{i<0}$ , and for every positive integer $n$ , the probability distribution on the `present', $X_0$ , conditioned on the event $\{L_0 = n\}$ and on the past is the same as the probability distribution on $X_0$ conditioned on the ` $n$ -past', $(X_i)_{-n\leq i <0}$ and $\{L_0 = n\}$ . A random Markov process is a generalization of a Markov chain of order $n$ and has the property that the distribution on the present given the past can be uniformly approximated given the $n$ -past, for $n$ sufficiently large. Processes with the latter property are called uniform martingales, closely related to the notion of a `continuous $g$ -function'. We show that every stationary process on a countable alphabet that is a uniform martingale and is dominated by a finite measure is also a random Markov process and that the random variables $(L_i)_{i \in \mathbb{Z}}$ and associated coupling can be chosen so that the distribution on the present given the $n$ -past and the event $\{L_0 = n\}$ is `deterministic': all probabilities are in $\{0,1\}$ . In the case of finite alphabets, those random-step Markov processes for which $L_0$ can be chosen with finite expected value are characterized. For stationary processes on an uncountable alphabet, a stronger condition is also considered which is sufficient to imply that a process is a random Markov processes. In addition, a number of examples are given throughout to show the sharpness of the results.

preprint2014arXiv

The sharp threshold for maximum-size sum-free subsets in even-order abelian groups

We study sum-free sets in sparse random subsets of even order abelian groups. In particular, we determine the sharp threshold for the following property: the largest such set is contained in some maximum-size sum-free subset of the group. This theorem extends recent work of Balogh, Morris and Samotij, who resolved the case G = Z_{2n}, and who obtained a weaker threshold (up to a constant factor) in general.

preprint2014arXiv

Turán Numbers for Forests of Paths in Hypergraphs

The Turán number of an r-uniform hypergraph H is the maximum number of edges in any r-graph on n vertices which does not contain H as a subgraph. Let P_l^(r) denote the family of r-uniform loose paths on l edges, F(k,l) denote the family of hypergraphs consisting of k disjoint paths from P_l^(r), and P'_l^(r) denote an r-uniform linear path on l edges. We determine precisely ex_r(n;F(k,l)) and ex_r(n;k*P'_l^(r)), as well as the Turán numbers for forests of paths of differing lengths (whether these paths are loose or linear) when n is appropriately large dependent on k,l,r, for r>=3. Our results build on recent results of Füredi, Jiang, and Seiver who determined the extremal numbers for individual paths, and provide more hypergraphs whose Turan numbers are exactly determined.

preprint2012arXiv

2-Colored Matchings in a 3-Colored K^{3}_{12}

Let $K_{n}^{r}$ denote the complete $r$ -uniform hypergraph on $n$ vertices. A matching $M$ in a hypergraph is a set of pairwise vertex disjoint edges. Recent Ramsey-type results rely on lemmas about the size of monochromatic matchings. A starting point for this study comes from a well-known result of Alon, Frankl, and Lovász (1986). Our motivation is to find the smallest $n$ such that every $t$ -coloring of $K_{n}^{r}$ contains an $s$ -colored matching of size $k$ . It has been conjectured that in every coloring of the edges of $K_n^r$ with 3 colors there is a 2-colored matching of size at least $k$ provided that $n \geq kr + \lfloor \frac{k-1}{r+1} \rfloor$ . The smallest test case is when $r=3$ and $k=4$ . We prove that in every 3-coloring of the edges of $K_{12}^3$ there is a 2-colored matching of size 4.

preprint2011arXiv

Turàn numbers of Multiple Paths and Equibipartite Trees

The Turán number of a graph H, ex(n;H), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let P_l denote a path on l vertices, and kP_l denote k vertex-disjoint copies of P_l. We determine ex(n, kP_3) for n appropriately large, answering in the positive a conjecture of Gorgol. Further, we determine ex (n, kP_l) for arbitrary l, and n appropriately large relative to k and l. We provide some background on the famous Erdős-Sós conjecture, and conditional on its truth we determine ex(n;H) when H is an equibipartite forest, for appropriately large n.

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.

Neal Bushaw

Research overview

Is this your work?

8 publications

Rainbow Saturation

Rainbow Turán Methods for Trees

The typical structure of graphs with no large cliques

Random-step Markov processes

The sharp threshold for maximum-size sum-free subsets in even-order abelian groups

Turán Numbers for Forests of Paths in Hypergraphs

2-Colored Matchings in a 3-Colored K^{3}_{12}

Turàn numbers of Multiple Paths and Equibipartite Trees

See the researcher in context

Building this map preview