BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Patrick Bennett contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
For a graph $G$, let $τ(G)$ be the maximum number of colors such that there exists an edge-coloring of $G$ with no two color classes being isomorphic. We investigate the behavior of $τ(G)$ when $G=G(n, p)$ is the classical Erdős-Rényi random graph.
We discuss the differential equation method for establishing dynamic concentration of discrete random processes. We present several relatively simple examples of it and aim to make the method understandable to the unfamiliar reader who has some basic knowledge on probabilistic methods, random graphs and differential equations.
We estimate the likely values of the chromatic and independence numbers of the random $r$-uniform $d$-regular hypergraph on $n$ vertices for fixed $r$, large fixed $d$, and $n \rightarrow \infty$.
A $(4, 5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique spans at least five colors. We show that there exist $(4, 5)$-colorings of $K_n$ using $\frac 56 n + o(n)$ colors. This settles a disagreement between Erdős and Gyárfás reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollobás and Erdős, and analyzed by Bohman, Frieze and Lubetzky.
A permutation in a digraph $G=(V, E)$ is a bijection $f:V \rightarrow V$ such that for all $v \in V$ we either have that $f$ fixes $v$ or $(v, f(v)) \in E$. A derangement in $G$ is a permutation that does not fix any vertex. In [1] it is proved that in any digraph, the ratio of derangements to permutations is at most $1/2$. Answering a question posed in [1], we show that the set of possible ratios of derangements to permutations in digraphs is dense in the interval $[0, 1/2]$.
A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $τ(G)$ is at most twice the triangle packing number $ν(G)$, where the triangle packing number $ν(G)$ is the maximum size of a set of edge-disjoint triangles in $G$ and the triangle covering number $τ(G)$ is the minimal size of a set of edges intersecting all triangles. In this paper, we prove that Tuza's conjecture holds in the Erdős-Rényi random graph $G(n,m)$ for all range of $m$, closing the gap in what was previously known. (Recently, this result was also independently proved by Jeff Kahn and Jinyoung Park.) We employ a random greedy process called the online triangle packing process to produce a triangle packing in $G(n,m)$ and analyze this process by using the differential equations method.
The triangle packing number $ν(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2ν(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $m \le 0.2403n^{3/2}$ or $m\ge 2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.
In the noisy channel model from coding theory, we wish to detect errors introduced during transmission by optimizing various parameters of the code. Bennett, Dudek, and LaForge framed a variation of this problem in the language of alternating paths in edge-colored complete bipartite graphs in 2016. Here, we extend this problem to the random graph $\mathbb{G}(n,p)$. We seek the alternating connectivity, $κ_{r,\ell}(G)$, which is the maximum $t$ such that there is an $r$-edge-coloring of $G$ such that any pair of vertices is connected by $t$ internally disjoint and alternating (i.e. no consecutive edges of the same color) paths of length $\ell$. We have three main results about how this parameter behaves in $\mathbb{G}(n,p)$ that basically cover all ranges of $p$: one for paths of length two, one for the dense case, and one for the sparse case. For paths of length two, we found that $κ_{r,\ell}(G)$ is essentially the codegree of a pair of vertices. For the dense case when $p$ is constant, we were able to achieve the natural upper bounds of minimum degree (minus some intersection) or the total number of disjoint paths between a pair of vertices. For the sparse case, we were able to find colorings that achieved the natural obstructions of minimum degree or (in a slightly less precise result) the total number of paths of a certain length in a graph. We broke up this sparse case into ranges of $p$ corresponding to when $\mathbb{G}(n,p)$ has diameter $k$ or $k+1$. We close with some remarks about a similar parameter and a generalization to pseudorandom graphs.
Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle $C_5$. We show that every graph of order $n$ and size $\left( 1-\frac{1}{k}\right)\binom{n}{2}$, where $k\ge 3$ is an integer, contains at least \[ \left( \frac{1}{10} -\frac{1}{2k} + \frac{1}{k^2} - \frac{1}{k^3} + \frac{2}{5 k^4} \right)n^5 +o(n^5) \] copies of $C_5$. This bound is optimal, since a matching upper bound is given by the balanced complete $k$-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.