1 citations · 1 across the 14 of their papers we have counts for
15 papers
The -color poset Ramsey number of the diamond is
Tom Bohman, Will Cong, Quentin Dubroff +3
The -color Ramsey number of a poset is the smallest dimension such that any -coloring of the -dimensional Boolean lattice contains a monochromatic induced copy of…
Online Permutation Embedding: Optimal Stopping and Scaling Laws
Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov
We study optimal online algorithms for embedding a permutation of into an iid stream of uniform random variables. This problem is a broad generalization of the cl…
Faster random walks via infrequent steering
Boris Bukh, Quentin Dubroff
Random walks on graphs can be slow. To speed them up, imagine that at each step instead of choosing the neighbor at random, there is a small probability that we can…
Thresholds vs. expectation thresholds for non-spanning graphs
Quentin Dubroff
The threshold for the event that the binomial random graph contains a copy of a graph is the unique for which , an…
On Minimum Cost Rainbow Structures
Patrick Bennett, Quentin Dubroff, Alan Frieze +1
We discuss the expected minimum cost of rainbow spanning trees and Hamilton cycles in randomly edge colored random graphs.
On the "second" Kahn--Kalai Conjecture: cliques, cycles, and trees
Quentin Dubroff, Jeff Kahn, Jinyoung Park
We prove a few simple cases of a random graph statement that would imply the "second" Kahn--Kalai Conjecture. Even these cases turn out to be reasonably challenging, and it is hope…
On the "second" Kahn--Kalai Conjecture
Quentin Dubroff, Jeff Kahn, Jinyoung Park
We make progress on a conjecture of Kahn and Kalai, the original (stronger but less general) version of what became known as the ``Kahn-Kalai Conjecture" (KKC; now a theorem of Par…
Note on a conjecture of Talagrand: expectation thresholds vs. fractional expectation thresholds
Quentin Dubroff, Jeff Kahn, Jinyoung Park
We show that a restricted version of a conjecture of M. Talagrand on the relation between "expectation thresholds" and "fractional expectation thresholds" follows easily from a str…
On the -space of a random graph
Quentin Dubroff, Jeff Kahn
The edge space of a graph is the vector space with members naturally identified with subgraphs of , and the -space is the subspace…
Clique Supersaturation
Quentin Dubroff, Benjamin Gunby, Bhargav Narayanan +1
We study how many copies of a graph that another graph with a given number of cliques is guaranteed to have. For example, one of our main results states that for all $t\ge…
A Counterexample to a Directed KKL Inequality
Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan
We show that the natural directed analogues of the KKL theorem [KKL88] and the Eldan--Gross inequality [EG20] from the analysis of Boolean functions fail to hold. This is in contra…
Reverse discrepancy and almost zero-sum stars
Quentin Dubroff
For chosen from the -valued functions on the edges of a hypergraph with , how large can one make $\min_{v \in V} |\sum_…
Tower Gaps in Multicolour Ramsey Numbers
Quentin Dubroff, António Girão, Eoin Hurley +1
Resolving a problem of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower height separation between their -colour and -colour Ramsey num…
Linear cover time is exponentially unlikely
Quentin Dubroff, Jeff Kahn
Proving a 2009 conjecture of Itai Benjamini, we show: For any C there is an such that for any simple graph on of size , and an ordinary rand…
A better bound for ordinary triangles
Quentin Dubroff
Let be a finite set of points in the plane. A c-ordinary triangle is a set of three non-collinear points of such that each line spanned by the points contains at most p…