Source author record

Tom Bohman

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 Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

17works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

A Critical Probability for Biclique Partition of $G_{n,p}$

The biclique partition number of a graph $G= (V,E)$ , denoted $bp(G)$ , is the minimum number of pairwise edge disjoint complete bipartite subgraphs of $G$ so that each edge of $G$ belongs to exactly one of them. It is easy to see that $bp(G) \leq n - α(G)$ , where $α(G)$ is the maximum size of an independent set of $G$ . Erdős conjectured in the 80's that for almost every graph $G$ equality holds; i.e., if $G=G_{n,1/2}$ then $bp(G) = n - α(G)$ with high probability. Alon showed that this is false. We show that the conjecture of Erdős is true if we instead take $G=G_{n,p}$ , where $p$ is constant and less than a certain threshold value $p_0 \approx 0.312$ . This verifies a conjecture of Chung and Peng for these values of $p$ . We also show that if $p_0 < p <1/2$ then $bp(G_{n,p}) = n - (1 + Θ(1)) α(G_{n,p})$ with high probability.

preprint2022arXiv

A Construction for Boolean cube Ramsey numbers

Let $Q_n$ be the poset that consists of all subsets of a fixed $n$ -element set, ordered by set inclusion. The poset cube Ramsey number $R(Q_n,Q_n)$ is defined as the least $m$ such that any 2-coloring of the elements of $Q_m$ admits a monochromatic copy of $Q_n$ . The trivial lower bound $R(Q_n,Q_n)\ge 2n$ was improved by Cox and Stolee, who showed $R(Q_n,Q_n)\ge 2n+1$ for $3\le n\le 8$ and $n\ge 13$ using a probabilistic existence proof. In this paper, we provide an explicit construction that establishes $R(Q_n,Q_n)\ge 2n+1$ for all $n\ge 3$ . The best known upper bound, due to Lu and Thompson, is $R(Q_n, Q_n) \le n^2 - 2n + 2$ .

preprint2022arXiv

Complexes of nearly maximum diameter

The diameter of a strongly connected $d$ -dimensional simplicial complex is the diameter of its dual graph. We provide a probabilistic proof of the existence of $d$ -dimensional simplicial complexes with diameter $(\frac{1}{d \cdot d!} - (\log n)^{-ε}) n^d$ . Up to the first order term, this is the best possible lower bound for the maximum diameter of a $d$ -complex on $n$ vertices as a simple volume argument shows that the diameter of a $d$ -dimensional simplicial complex is at most $\frac{1}{d} \binom{n}{d}$ . We also find the right first-order asymptotics for the maximum diameter of a $d$ -pseudomanifold on $n$ vertices.

preprint2021arXiv

Independent sets in hypergraphs omitting an intersection

A $k$ -uniform hypergraph with $n$ vertices is an $(n,k,\ell)$ -omitting system if it does not contain two edges whose intersection has size exactly $\ell$ . If in addition it does not contain two edges whose intersection has size greater than $\ell$ , then it is an $(n,k,\ell)$ -system. Rödl and Šiňajová proved a lower bound for the independence number of $(n,k,\ell)$ -systems that is sharp in order of magnitude for fixed $2 \le \ell \le k-1$ . We consider the same question for the larger class of $(n,k,\ell)$ -omitting systems. For $k\le 2\ell+1$ , we believe that the behavior is similar to the case of $(n,k,\ell)$ -systems and prove a nontrivial lower bound for the first open case $\ell=k-2$ . For $k>2\ell+1$ we give new lower and upper bounds which show that the minimum independence number of $(n,k,\ell)$ -omitting systems has a very different behavior than for $(n,k,\ell)$ -systems. Our lower bound for $\ell=k-2$ uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for $k> 2\ell+1$ are obtained from some pseudorandom graphs. We also prove some related results where we forbid more than two edges with a prescribed common intersection size and this leads to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number $r_{k}(F^{k},t)$ , where $F^{k}$ is the $k$ -uniform Fan. Here the behavior is quite different than the case $k=2$ which reduces to the classical graph Ramsey number $r(3,t)$ .

preprint2020arXiv

Hamilton cycles in 3-out

Let G_{\rm 3-out} denote the random graph on vertex set [n] in which each vertex chooses 3 neighbors uniformly at random. Note that G_{\rm 3-out} has minimum degree 3 and average degree 6. We prove that the probability that G_{\rm 3-out} is Hamiltonian goes to 1 as n tends to infinity.

preprint2016arXiv

A note on $G$ -intersecting families

Consider a graph $G$ and a $k$ -uniform hypergraph $\mathcal{H}$ on common vertex set $[n]$ . We say that $\mathcal{H}$ is $G$ -intersecting if for every pair of edges in $X,Y \in \mathcal{H}$ there are vertices $x \in X$ and $y \in Y$ such that $x = y$ or $x$ and $y$ are joined by an edge in $G$ . This notion was introduced by Bohman, Frieze, Ruszinkó and Thoma who proved a natural generalization of the Erdős-Ko-Rado Theorem for $G$ -intersecting $k$ -uniform hypergraphs for $G$ sparse and $k = O( n^{1/4} )$ . In this note, we extend this result to $k = O\left( \sqrt{n} \right)$ .

preprint2016arXiv

Adding random edges to dense graphs

This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the appearance of a fixed size clique, small diameter and $k$ -connectivity.

preprint2016arXiv

How many random edges make a dense graph hamiltonian?

This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding $Θ(n)$ random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.

preprint2016arXiv

On randomly generated intersecting hypergraphs

Let $c$ be a positive constant. We show that if $r=\lfloor cn^{1/3}\rfloor$ and the members of ${[n]\choose r}$ are chosen sequentially at random to form an intersecting hypergraph then with limiting probability $(1+c^3)^{-1}$ , as $n\to\infty$ , the resulting family will be of maximum size ${n-1\choose r-1}$ .

preprint2016arXiv

On randomly generated intersecting hypergraphs II

Let $c$ be a positive constant. Suppose that $r=o(n^{5/12})$ and the members of $\binom{[n]}{r}$ are chosen sequentially at random to form an intersecting hypergraph $\mathcal{H}$ . We show that whp $\mathcal{H}$ consists of a simple hypergraph $\mathcal{S}$ of size $Θ(r/n^{1/3})$ , a distinguished vertex $v$ and all $r$ -sets which contain $v$ and meet every edge of $\mathcal{S}$ . This is a continuation of the study of such random intersecting systems started in [Electron. J. Combin, (2003) R29] where the case $r=O(n^{1/3})$ was considered. To obtain the stated result we continue to investigate this question in the range $ω(n^{1/3})\le r \le o(n^{5/12})$ .

preprint2014arXiv

More on the bipartite decomposition of random graphs

For a graph $G=(V,E)$ , let $bc(G)$ denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of $G$ so that each edge of $G$ belongs to exactly one of them. It is easy to see that for every graph $G$ , $bc(G) \leq n -α(G)$ , where $α(G)$ is the maximum size of an independent set of $G$ . Erdős conjectured in the 80s that for almost every graph $G$ equality holds, i.e., that for the random graph $G(n,0.5)$ , $bc(G)=n-α(G)$ with high probability, that is, with probability that tends to 1 as $n$ tends to infinity. The first author showed that this is slightly false, proving that for most values of $n$ tending to infinity and for $G=G(n,0.5)$ , $bc(G) \leq n-α(G)-1$ with high probability. We prove a stronger bound: there exists an absolute constant $c>0$ so that $bc(G) \leq n-(1+c)α(G)$ with high probability.

preprint2014arXiv

The independent neighborhoods process

A triangle $T^{(r)}$ in an $r$ -uniform hypergraph is a set of $r+1$ edges such that $r$ of them share a common $(r-1)$ -set of vertices and the last edge contains the remaining vertex from each of the first $r$ edges. Our main result is that the random greedy triangle-free process on $n$ points terminates in an $r$ -uniform hypergraph with independence number $O((n \log n)^{1/r})$ . As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number $r(T^{(r)}, K_s^{(r)})$ has order of magnitude $s^r/\log s$ . This answers questions posed in~\cite{BFM, KMV} and generalizes the celebrated results of Ajtai-Komlós-Szemerédi~\cite{AKS} and Kim~\cite{K} to hypergraphs.

preprint2012arXiv

A greedy algorithm for finding a large 2-matching on a random cubic graph

A 2-matching of a graph $G$ is a spanning subgraph with maximum degree two. The size of a 2-matching $U$ is the number of edges in $U$ and this is at least $n-\k(U)$ where $n$ is the number of vertices of $G$ and $\k$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm \textsc{2greedy} for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching $U$ with $\k(U) = \tildeΘ\of{n^{1/5}}$.

preprint2012arXiv

Random greedy triangle-packing beyond the 7/4 barrier

The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. Begin with a complete graph on $n$ vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random out of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph, and a longstanding open problem is to estimate the final number of edges, or equivalently the time it takes the process to conclude. The intuition that the edge distribution is roughly uniform at all times led to a folklore conjecture that the final number of edges is $n^{3/2+o(1)}$ with high probability, whereas the best known upper bound is $n^{7/4+o(1)}$ . It is no coincidence that various methods break precisely at the exponent 7/4 as it corresponds to the inherent barrier where co-degrees become comparable to the variations in their values that arose earlier in the process. In this work we significantly improve upon the previous bounds by establishing that w.h.p. the number of edges in the final graph is at most $n^{5/3+o(1)}$ . Our approach relies on a system of martingales used to control key graph parameters, where the crucial new idea is to harness the self-correcting nature of the process in order to control these parameters well beyond the point where their early variation matches the order of their expectation.

preprint2012arXiv

Random triangle removal

Starting from a complete graph on $n$ vertices, repeatedly delete the edges of a uniformly chosen triangle. This stochastic process terminates once it arrives at a triangle-free graph, and the fundamental question is to estimate the final number of edges (equivalently, the time it takes the process to finish, or how many edge-disjoint triangles are packed via the random greedy algorithm). Bollobás and Erdős (1990) conjectured that the expected final number of edges has order $n^{3/2}$ , motivated by the study of the Ramsey number $R(3,t)$ . An upper bound of $o(n^2)$ was shown by Spencer (1995) and independently by Rödl and Thoma (1996). Several bounds were given for variants and generalizations (e.g., Alon, Kim and Spencer (1997) and Wormald (1999)), while the best known upper bound for the original question of Bollobás and Erdős was $n^{7/4+o(1)}$ due to Grable (1997). No nontrivial lower bound was available. Here we prove that with high probability the final number of edges in random triangle removal is equal to $n^{3/2+o(1)}$ , thus confirming the 3/2 exponent conjectured by Bollobás and Erdős and matching the predictions of Spencer et al. For the upper bound, for any fixed $ε>0$ we construct a family of $\exp(O(1/ε))$ graphs by gluing $O(1/ε)$ triangles sequentially in a prescribed manner, and dynamically track all homomorphisms from them, rooted at any two vertices, up to the point where $n^{3/2+ε}$ edges remain. A system of martingales establishes concentration for these random variables around their analogous means in a random graph with corresponding edge density, and a key role is played by the self-correcting nature of the process. The lower bound builds on the estimates at that very point to show that the process will typically terminate with at least $n^{3/2-o(1)}$ edges left.

preprint2010arXiv

A note on the random greedy triangle-packing algorithm

The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. We begin with a complete graph on $n$ vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random from the collection of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph. In this note we show that with high probability the number of edges in the final graph is at most $O\big( n^{7/4}\log^{5/4}n \big)$ .

preprint2009arXiv

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as $n \to \infty$ , the minimum degree in G is at least $cn^{1-(v_H-2)/(e_H-1)}(\log n)^{1/(e_H-1)}$ . This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs $K_{r,r}$ with $r \ge 5$ . When H is a complete graph $K_s$ with $s \ge 5$ we show that for some C>0, with high probability the independence number of G is at most $Cn^{2/(s+1)}(\log n)^{1-1/(e_H-1)}$ . This gives new lower bounds for Ramsey numbers R(s,t) for fixed $s \ge 5$ and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.

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.

Tom Bohman

Research overview

Is this your work?

17 publications

A Critical Probability for Biclique Partition of $G_{n,p}$

A Construction for Boolean cube Ramsey numbers

Complexes of nearly maximum diameter

Independent sets in hypergraphs omitting an intersection

Hamilton cycles in 3-out

A note on $G$ -intersecting families

Adding random edges to dense graphs

How many random edges make a dense graph hamiltonian?

On randomly generated intersecting hypergraphs

On randomly generated intersecting hypergraphs II

More on the bipartite decomposition of random graphs

The independent neighborhoods process

A greedy algorithm for finding a large 2-matching on a random cubic graph

Random greedy triangle-packing beyond the 7/4 barrier

Random triangle removal

A note on the random greedy triangle-packing algorithm

The early evolution of the H-free process

See the researcher in context

Building this map preview

Tom Bohman

Research overview

Is this your work?

17 publications

A Critical Probability for Biclique Partition of Gn,pG_{n,p}Gn,p​

A Construction for Boolean cube Ramsey numbers

Complexes of nearly maximum diameter

Independent sets in hypergraphs omitting an intersection

Hamilton cycles in 3-out

A note on GGG-intersecting families

Adding random edges to dense graphs

How many random edges make a dense graph hamiltonian?

On randomly generated intersecting hypergraphs

On randomly generated intersecting hypergraphs II

More on the bipartite decomposition of random graphs

The independent neighborhoods process

A greedy algorithm for finding a large 2-matching on a random cubic graph

Random greedy triangle-packing beyond the 7/4 barrier

Random triangle removal

A note on the random greedy triangle-packing algorithm

The early evolution of the H-free process

See the researcher in context

Building this map preview

A Critical Probability for Biclique Partition of $G_{n,p}$

A note on $G$ -intersecting families