Source author record

Robert A. Krueger

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

5works

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.

preprint2022arXiv

Sharp threshold for the Erdős-Ko-Rado theorem

For positive integers $n$ and $k$ with $n\geq 2k+1$ , the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$ -sets of $\{1,\dots,n\}$ , where two $k$ -sets are adjacent exactly when they are disjoint. The independent sets of $K(n,k)$ are $k$ -uniform intersecting families, and hence the maximum size independent sets are given by the Erdős-Ko-Rado Theorem. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$ . Bollobás, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. For $n=2k+1$ , we prove a hitting time result, which gives a sharp threshold for this problem at $p=3/4$ . Additionally, completing work of Das and Tran and work of Devlin and Kahn, we determine a sharp threshold function for all $n>2k+1$ .

preprint2021arXiv

Firefighting on the Hexagonal Grid and on Infinite Trees

The firefighter problem with $k$ firefighters on an infinite graph $G$ is an iterative graph process, defined as follows: Suppose a fire breaks out at a given vertex $v\in V(G)$ on Turn 1. On each subsequent even turn, $k$ firefighters protect $k$ vertices that are not on fire, and on each subsequent odd turn, any vertex that is on fire spreads the fire to all adjacent unprotected vertices. The firefighters' goal is to eventually stop the spread of the fire. If there exists a strategy for $k$ firefighters to eventually stop the spread of the fire, then we say $G$ is $k$ -containable. We consider the firefighter problem on the hexagonal grid, which is the graph whose vertices and edges are exactly the vertices and edges of a regular hexagonal tiling of the plane. It is not known if the hexagonal grid is $1$ -containable. In arXiv:1305.7076 [math.CO], it was shown that if the firefighters have one firefighter per turn and one extra firefighter on two turns, the firefighters can contain the fire. We improve on this result by showing that even with only one extra firefighter on one turn, the firefighters can still contain the fire. In addition, we explore $k$ -containability for birth sequence trees, which are infinite rooted trees that have the property that every vertex at the same level has the same degree. A birth sequence forest is an infinite forest, each component of which is a birth sequence tree. For birth sequence trees and forests, the fire always starts at the root of each tree. We provide a pseudopolynomial time algorithm to decide if all the vertices at a fixed level can be protected or not.

preprint2020arXiv

A note about monochromatic components in graphs of large minimum degree

For all positive integers $r\geq 3$ and $n$ such that $r^2-r$ divides $n$ and an affine plane of order $r$ exists, we construct an $r$ -edge colored graph with minimum degree $(1-\frac{r-2}{r^2-r})n-2$ such that the largest monochromatic component has order less than $\frac{n}{r-1}$ . This generalizes an example of Guggiari and Scott and, independently, Rahimi for $r=3$ and thus disproves a conjecture of Gyárfás and Sárközy for all integers $r\geq 3$ such that an affine plane of order $r$ exists.

preprint2020arXiv

Generalized Ramsey numbers: forbidding paths with few colors

Let $f(K_n, H, q)$ be the minimum number of colors needed to edge-color $K_n$ so that every copy of $H$ is colored with at least $q$ colors. Originally posed by Erdős and Shelah when $H$ is complete, the asymptotics of this extremal function have been extensively studied when $H$ is a complete graph or a complete balanced bipartite graph. Here we investigate this function for some other $H$ , and in particular we determine the asymptotic behavior of $f(K_n, P_v, q)$ for almost all values of $v$ and $q$ , where $P_v$ is a path on $v$ vertices.

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.