Source author record

H. A. Kierstead

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

9works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Random bipartite posets and extremal problems

Previously, Erdős, Kierstead and Trotter investigated the dimension of random height~ $2$ partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing the relative tightness of the Füredi-Kahn upper bounds on dimension in terms of maximum degree; and (2)~developing machinery for estimating the expected dimension of a random labeled poset on $n$ points. For these reasons, most of their effort was focused on the case $0<p\le 1/2$ . While bounds were given for the range $1/2\le p <1$ , the relative accuracy of the results in the original paper deteriorated as $p$ approaches~ $1$ . Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range $1/2\le p<1$ . Our sharpened analysis shows that as $p$ approaches~ $1$ , the expected value of dimension increases and then decreases, answering in the negative a question posed in the original paper. Along the way, we apply inequalities of Talagrand and Janson, establish connections with latin rectangles and the Euler product function, and make progress on both extremal problems.

preprint2019arXiv

On coloring numbers of graph powers

The weak $r$ -coloring numbers $wcol_r(G)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $col(G)$ , and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs. Let $G^p$ denote the $p$ -th power of $G$ . We show that, all integers $p >0$ and $Δ\ge 3$ and graphs $G$ with $Δ(G) \leq Δ$ satisfy $col(G^p) \in O(p \cdot wcol_{\lceil p/2\rceil}(G)(Δ-1)^{\lfloor p/2\rfloor})$ ; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$ . For the square of graphs $G$ , we also show that, if the maximum average degree $2k-2 < mad(G) \leq 2k$ , then $col(G^2) \leq (2k-1)Δ(G)+2k+1$ .

preprint2016arXiv

On the Corrádi-Hajnal Theorem and a question of Dirac

In 1963, Corrádi and Hajnal proved that for all $k\geq1$ and $n\geq3k$ , every graph $G$ on $n$ vertices with minimum degree $δ(G)\geq2k$ contains $k$ disjoint cycles. The bound $δ(G) \geq 2k$ is sharp. Here we characterize those graphs with $δ(G)\geq2k-1$ that contain $k$ disjoint cycles. This answers the simple-graph case of Dirac's 1963 question on the characterization of $(2k-1)$ -connected graphs with no $k$ disjoint cycles. Enomoto and Wang refined the Corrádi-Hajnal Theorem, proving the following Ore-type version: For all $k\geq1$ and $n\geq3k$ , every graph $G$ on $n$ vertices contains $k$ disjoint cycles, provided that $d(x)+d(y)\geq 4k-1$ for all distinct nonadjacent vertices $x,y$ . We refine this further for $k\geq3$ and $n\geq3k+1$ : If $G$ is a graph on $n$ vertices such that $d(x)+d(y)\geq 4k-3$ for all distinct nonadjacent vertices $x,y$ , then $G$ has $k$ vertex-disjoint cycles if and only if the independence number $α(G)\leq n-2k$ and $G$ is not one of two small exceptions in the case $k=3$ . We also show how the case $k=2$ follows from Lovász' characterization of multigraphs with no two disjoint cycles.

preprint2015arXiv

First-fit coloring on interval graphs has performance ratio at least 5

First-fit is the online graph coloring algorithm that considers vertices one at a time in some order and assigns each vertex the least positive integer not used already on a neighbor. The maximum number of colors used by first-fit on graph G over all vertex orders is denoted χ_{FF}(G). The exact value of R := \sup_G [χ_{FF}(G) / ω(G)] over interval graphs G is unknown. Pemmaraju, Raman, and Varadarajan (2004) proved R <= 10, and this can be improved to 8. Witsenhausen (1976) and Chrobak and Ślusarek (1988) showed R >= 4, and Ślusarek (1993) improved this to 4.45. We prove R >= 5.

preprint2015arXiv

The (2k-1)-connected multigraphs with at most k-1 disjoint cycles

In 1963, Corrádi and Hajnal proved that for all $k \ge 1$ and $n \ge 3k$ , every (simple) graph on n vertices with minimum degree at least 2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2k-1)-connected multigraphs do not contain k disjoint cycles? Recently, the authors characterized the simple graphs G with minimum degree $δ(G) \ge 2k-1$ that do not contain k disjoint cycles. We use this result to answer Dirac's question in full.

preprint2014arXiv

On the choice number of complete multipartite graphs with part size four

Let $\mathrm{ch}(G)$ denote the choice number of a graph $G$ , and let $K_{s*k}$ be the complete $k$ -partite graph with $s$ vertices in each part. Erdős, Rubin, and Taylor showed that $\mathrm{ch}( K_{2*k})=k$ , and suggested the problem of determining the choice number of $K_{s*k}.$ The first author established $\mathrm{ch}( K_{3*k})=\left\lceil \frac{4k-1}{3}\right\rceil$ . Here we prove $\mathrm{ch} (K_{4*k})=\left\lceil \frac{3k-1}{2}\right\rceil$ .

preprint2013arXiv

An extension of the Hajnal-Szemeredi theorem to directed graphs

Hajnal and Szemeredi proved that every graph G with |G|=ks and minimum degree at least k(s-1) contains k vertex disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph D with |D|=ks and minimum (total) degree at least 2k(s-1)-1 contains k vertex disjoint transitive tournaments on s vertices. Our result implies the Hajnal-Szemeredi Theorem, and the degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.

preprint2013arXiv

On directed versions of the Corrádi-Hajnal Corollary

For $k \in \mathbb N$ , Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $δ(G) \ge 2k$ has a $C_3$ -factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle $C_3$ . Wang proved that every directed graph $\overrightarrow G$ on $3k$ vertices with minimum total degree $δ_t(\overrightarrow G):=\min_{v\in V}(deg^-(v)+deg^+(v)) \ge 3(3k-1)/2$ has a $\overrightarrow C_3$ -factor, where $\overrightarrow C_3$ is the directed 3-cycle. The degree bound in Wang's result is tight. However, our main result implies that for all integers $a \ge 1$ and $b \ge 0$ with $a+b=k$ , every directed graph $\overrightarrow G$ on $3k$ vertices with minimum total degree $δ_t(\overrightarrow G)\ge 4k-1$ has a factor consisting of $a$ copies of $\overrightarrow T_3$ and $b$ copies of $\overrightarrow C_3$ , where $\overrightarrow T_3$ is the transitive tournament on three vertices. In particular, using $b=0$ , there is a $\overrightarrow T_3$ -factor of $\overrightarrow G$ , and using $a=1$ , it is possible to obtain a $\overrightarrow C_3$ -factor of $\overrightarrow G$ by reversing just one edge of $\overrightarrow G$ . All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph $\overrightarrow G$ on $3k$ vertices with minimum semidegree $δ_0(\overrightarrow G):=\min_{v\in V}\min(deg^-(v),deg^+(v)) \ge 2k$ has a $\overrightarrow C_3$ -factor, and prove that this is asymptotically correct.

preprint2011arXiv

Pósa's Conjecture for graphs of order at least 2\times 10^8

In 1962 Pósa conjectured that every graph G on n vertices with minimum degree at least 2n/3 contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of Pósa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than 2n/3. Still in 1996, Komlós, Sárközy, and Szemerédi proved Pósa's Conjecture, using the Regularity and Blow-up Lemmas, for graphs of order n > n_0, where n_0 is a very large constant. Here we show without using these lemmas that n_0=2\times 10^8 is sufficient. We are motivated by the recent work of Levitt, Szemerédi and Sárközy, but our methods are based on techniques that were available in the 90's.

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.