16 papers · 1 filter
Thresholds for geometric graphs
Bhargav Narayanan
A metric probability space admits thresholds if the random geometric graph on has a threshold for every monotone graph property. We connect the existence of thresholds to t…
How to pick your football team
Bhargav Narayanan
Team captains Alice and Bob divide up footballers, each reduced to a real-valued score, into two teams of footballers each. On each turn, one captain plays picker, and the…
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…
Friendly bisections of random graphs
Asaf Ferber, Matthew Kwan, Bhargav Narayanan +2
Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph admits a friendly bisection of its vertex set, i.e., a partition of its…
The threshold for the square of a Hamilton cycle
Jeff Kahn, Bhargav Narayanan, Jinyoung Park
Resolving a conjecture of Kühn and Osthus from 2012, we show that is the threshold for the random graph to contain the square of a Hamilton cycle.
A universal exponent for homeomorphs
Peter Keevash, Jason Long, Bhargav Narayanan +1
We prove a uniform bound on the topological Turán number of an arbitrary two-dimensional simplicial complex : any -vertex two-dimensional complex with at least $C_S n^{3-1/5}…