Source author record

Emily Heath

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Lower bounds on the Erdős-Gyárfás problem via color energy graphs

Given positive integers $p$ and $q$ , a $(p,q)$ -coloring of the complete graph $K_n$ is an edge-coloring in which every $p$ -clique receives at least $q$ colors. Erdős and Shelah posed the question of determining $f(n,p,q)$ , the minimum number of colors needed for a $(p,q)$ -coloring of $K_n$ . In this paper, we expand on the color energy technique introduced by Pohoata and Sheffer to prove new lower bounds on this function, making explicit the connection between bounds on extremal numbers and $f(n,p,q)$ . Using results on the extremal numbers of subdivided complete graphs, theta graphs, and subdivided complete bipartite graphs, we generalize results of Fish, Pohoata, and Sheffer, giving the first nontrivial lower bounds on $f(n,p,q)$ for some pairs $(p,q)$ and improving previous lower bounds for other pairs.

preprint2020arXiv

New Upper Bounds for the Erdős-Gyárfás Problem on Generalized Ramsey Numbers

A $(p,q)$ -coloring of a graph $G$ is an edge-coloring of $G$ which assigns at least $q$ colors to each $p$ -clique. The problem of determining the minimum number of colors, $f(n,p,q)$ , needed to give a $(p,q)$ -coloring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$ . The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in\{4,5\}$ , each of which was proved by giving a deterministic construction which combined a $(p,p-1)$ -coloring using few colors with an algebraic coloring. In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colorings of $p$ -cliques with $p-1$ colors which can appear in our modified version of the $(p,p-1)$ -coloring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$ -colorings, which would otherwise make this problem intractable for large values of $p$ . In addition, we generalize our algebraic coloring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$ .

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.