Gregory B. Sorkin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Gregory B. Sorkin has a total of 92 co-authors. Here are the top co-authors by number of shared publications:
- Alan Frieze
Department of Mathematical Sciences Carnegie Mellon University Pittsburgh Pennsylvania USA
7 shared publications Alexander D. Scott
7 shared publicationsDon Coppersmith
IDA Center for Communications Research, Princeton, NJ
4 shared publicationsAbraham Flaxman
Carnegie Mellon University Pittsburgh
3 shared publications- Alina Beygelzimer
IBM Research
3 shared publications - Béla Bollobás
University of Cambridge, Cambridge, UK
3 shared publications
Latest Publications
- Open Access
Reverse Littlewood--Offord problems with parity conditions
We consider the probability that the random signed sum $ξ_1 v_1 + \dotsb + ξ_n v_n$ lies within a given distance $r$ of the origin, where $v_1,\dotsc,v_n \in \mathbb{R}^d$ are fixed unit vectors and $ξ_1,\dotsc,ξ_n$ are independently and uniformly distributed on $\{-1,+1\}$. In particular, our results demonstrate that, for certain values of $r$, the infimum of this probability is very sensitive to the parity of $n$. We prove that, for any $d\geq 3$, there is some $\varepsilon = \varepsilon(d) > 0$ such that for any $n \not\equiv d \mod 2$ and unit vectors $v_1,\dotsc,v_n\in \mathbb{R}^d$, there are signs $η_1,\dotsc,η_n \in \{-1,+1\}$ such that $\|\sum_{i=1}^n η_i v_i\| \leq \sqrt{d - \varepsilon}$, and so $\mathbb{P}(\| ξ_1 v_1 + \dotsb + ξ_n v_n \| \leq \sqrt{d-\varepsilon}) > 0$. This is in contrast to the case of $n\equiv d \mod 2$, wherein the above probability can be zero. More is known if $d=2$ and $n$ is odd, and in this case we present a construction demonstrating that $\mathbb{P}(\|ξ_1 v_1 + \dotsb + ξ_n v_n\| \leq 1)$ can decay exponentially as $n$ increases.Open AccessReverse Littlewood--Offord problems with parity conditions
We consider the probability that the random signed sum $ξ_1 v_1 + \dotsb + ξ_n v_n$ lies within a given distance $r$ of the origin, where $v_1,\dotsc,v_n \in \mathbb{R}^d$ are fixed unit vectors and $ξ_1,\dotsc,ξ_n$ are independently and uniformly distributed on $\{-1,+1\}$. In particular, our results demonstrate that, for certain values of $r$, the infimum of this probability is very sensitive to the parity of $n$. We prove that, for any $d\geq 3$, there is some $\varepsilon = \varepsilon(d) > 0$ such that for any $n \not\equiv d \mod 2$ and unit vectors $v_1,\dotsc,v_n\in \mathbb{R}^d$, there are signs $η_1,\dotsc,η_n \in \{-1,+1\}$ such that $\|\sum_{i=1}^n η_i v_i\| \leq \sqrt{d - \varepsilon}$, and so $\mathbb{P}(\| ξ_1 v_1 + \dotsb + ξ_n v_n \| \leq \sqrt{d-\varepsilon}) > 0$. This is in contrast to the case of $n\equiv d \mod 2$, wherein the above probability can be zero. More is known if $d=2$ and $n$ is odd, and in this case we present a construction demonstrating that $\mathbb{P}(\|ξ_1 v_1 + \dotsb + ξ_n v_n\| \leq 1)$ can decay exponentially as $n$ increases. - Open Access
Optimally building spanning graphs in semirandom graph processes
The semirandom graph process constructs a graph $G$ in a series of rounds, starting with the empty graph on $n$ vertices. In each round, a player is offered a vertex $v$ chosen uniformly at random, and chooses an edge on $v$ to add to $G$. The player's aim is to make $G$ satisfy some property as quickly as possible. Our interest is in the property that $G$ contain a given $n$-vertex graph $H$ with maximum degree $Δ$. In 2021, Ben-Eliezer, Gishboliner, Hefetz and Krivelevich showed that there is a semirandom strategy that achieves this, with probability tending to 1 as $n$ tends to infinity, in $(1 + o_Δ(1)) \frac{3 Δn}{2}$ rounds, where $o_Δ(1)$ is a function that tends to $0$ as $Δ$ tends to infinity. We improve this to $(1 + o_Δ(1)) \frac{Δn}{2}$, which can be seen to be asymptotically optimal in $Δ$. We show the same result for a variant of the semirandom graph process, namely the semirandom tree process introduced by Burova and Lichev, where in each round the player is offered the edge set of a uniformly chosen tree on $n$ vertices, and chooses one edge to keep.Open AccessOptimally building spanning graphs in semirandom graph processes
The semirandom graph process constructs a graph $G$ in a series of rounds, starting with the empty graph on $n$ vertices. In each round, a player is offered a vertex $v$ chosen uniformly at random, and chooses an edge on $v$ to add to $G$. The player's aim is to make $G$ satisfy some property as quickly as possible. Our interest is in the property that $G$ contain a given $n$-vertex graph $H$ with maximum degree $Δ$. In 2021, Ben-Eliezer, Gishboliner, Hefetz and Krivelevich showed that there is a semirandom strategy that achieves this, with probability tending to 1 as $n$ tends to infinity, in $(1 + o_Δ(1)) \frac{3 Δn}{2}$ rounds, where $o_Δ(1)$ is a function that tends to $0$ as $Δ$ tends to infinity. We improve this to $(1 + o_Δ(1)) \frac{Δn}{2}$, which can be seen to be asymptotically optimal in $Δ$. We show the same result for a variant of the semirandom graph process, namely the semirandom tree process introduced by Burova and Lichev, where in each round the player is offered the edge set of a uniformly chosen tree on $n$ vertices, and chooses one edge to keep. - Open Access
- 11 March 2025
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (2)
Perfect Matchings and Loose Hamilton Cycles in the Semirandom Hypergraph Model
We study the 2‐offer semirandom 3‐uniform hypergraph model on vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect matching and another that constructs a loose Hamilton cycle, both succeeding asymptotically almost surely within steps. Both results extend to ‐uniform hypergraphs. Our methods are qualitatively different from those that have been used for semirandom graphs. Much of the analysis is done on an auxiliary graph that is a uniform ‐out subgraph of a random bipartite graph, and this tool may be useful in other contexts.
- 11 March 2025
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (2)
Open AccessPerfect Matchings and Loose Hamilton Cycles in the Semirandom Hypergraph Model
We study the 2‐offer semirandom 3‐uniform hypergraph model on vertices. At each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect matching and another that constructs a loose Hamilton cycle, both succeeding asymptotically almost surely within steps. Both results extend to ‐uniform hypergraphs. Our methods are qualitatively different from those that have been used for semirandom graphs. Much of the analysis is done on an auxiliary graph that is a uniform ‐out subgraph of a random bipartite graph, and this tool may be useful in other contexts.
- Open Access
- 3 February 2023
- Published by Springer Nature in The Mathematical Intelligencer
- Vol. 45 (4) , 312-318
Snakes and Ladders and Intransitivity, or What Mathematicians Do in Their Time Off
- 3 February 2023
- Published by Springer Nature in The Mathematical Intelligencer
- Vol. 45 (4) , 312-318
Open AccessSnakes and Ladders and Intransitivity, or What Mathematicians Do in Their Time Off
- Open Access
Hamilton cycles in a semi-random graph model
We show that with high probability we can build a Hamilton cycle after at most $1.85 n$ rounds in a particular semi-random model. In this model, in one round, we are given a {uniform random} $v\in[n]$ and then we can add an {arbitrary} edge $\{v,w\}$. Our result improves on $2.016 n$ in a recent paper of Gao, MacRury, and Pralat.Open AccessHamilton cycles in a semi-random graph model
We show that with high probability we can build a Hamilton cycle after at most $1.85 n$ rounds in a particular semi-random model. In this model, in one round, we are given a {uniform random} $v\in[n]$ and then we can add an {arbitrary} edge $\{v,w\}$. Our result improves on $2.016 n$ in a recent paper of Gao, MacRury, and Pralat. - 2 June 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 36 (2) , 1306-1342
The Ising Antiferromagnet and Max Cut on Random Regular Graphs
The Ising antiferromagnet is an important statistical physics model with close connections to the Max Cut problem. Combining spatial mixing arguments with the method of moments and the interpolatio...
- 2 June 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 36 (2) , 1306-1342
The Ising Antiferromagnet and Max Cut on Random Regular Graphs
The Ising antiferromagnet is an important statistical physics model with close connections to the Max Cut problem. Combining spatial mixing arguments with the method of moments and the interpolatio...
- Open Access
Snakes and Ladders and Intransitivity, or what mathematicians do in their time off
This recreational mathematics article shows that the game of Snakes and Ladders is intransitive: square 69 has a winning edge over 79, which in turn beats 73, which beats 69. Analysis of the game is a nice illustration of Markov chains, simulations of different sorts, and size-biased sampling. Connecting this to "intransitive dice" illustrates the power of a name, and the joy of working with colleagues. When draws do not count, we show a minimal example of intransitive dice, with one die having just a single "face" and two dice each having two faces.
Open AccessSnakes and Ladders and Intransitivity, or what mathematicians do in their time off
This recreational mathematics article shows that the game of Snakes and Ladders is intransitive: square 69 has a winning edge over 79, which in turn beats 73, which beats 69. Analysis of the game is a nice illustration of Markov chains, simulations of different sorts, and size-biased sampling. Connecting this to "intransitive dice" illustrates the power of a name, and the joy of working with colleagues. When draws do not count, we show a minimal example of intransitive dice, with one die having just a single "face" and two dice each having two faces.
- 22 September 2021
- Published by Wiley in Random Structures & Algorithms
- Vol. 61 (1) , 126-172
Successive minimum spanning trees
In a complete graphwith independent uniform(or exponential) edge weights, letbe the minimum‐weight spanning tree (MST), andthe MST after deleting the edges of all previous trees. We show that each tree's weightconverges in probability to a constant, with, and we conjecture that. The problem is distinct from Frieze and Johansson's minimum combined weightofkedge‐disjoint spanning trees; indeed,. With an edge of weightw“arriving” at time, Kruskal's algorithm defines forests, initially empty and eventually equal to, each edge added to the first possible. Using tools of inhomogeneous random graphs we obtain structural results including that the fraction of vertices in the largest component ofconverges to some. We conjecture that the functionstend to time translations of a single function.
- 22 September 2021
- Published by Wiley in Random Structures & Algorithms
- Vol. 61 (1) , 126-172
Successive minimum spanning trees
In a complete graphwith independent uniform(or exponential) edge weights, letbe the minimum‐weight spanning tree (MST), andthe MST after deleting the edges of all previous trees. We show that each tree's weightconverges in probability to a constant, with, and we conjecture that. The problem is distinct from Frieze and Johansson's minimum combined weightofkedge‐disjoint spanning trees; indeed,. With an edge of weightw“arriving” at time, Kruskal's algorithm defines forests, initially empty and eventually equal to, each edge added to the first possible. Using tools of inhomogeneous random graphs we obtain structural results including that the fraction of vertices in the largest component ofconverges to some. We conjecture that the functionstend to time translations of a single function.
- Open Access
- 1 December 2020
- Published by Wiley in Random Structures & Algorithms
- Vol. 57 (4) , 1205-1247
Successive shortest paths in complete graphs with random edge weights
- 1 December 2020
- Published by Wiley in Random Structures & Algorithms
- Vol. 57 (4) , 1205-1247
Open AccessSuccessive shortest paths in complete graphs with random edge weights
- Open Access
The Ising antiferromagnet and max cut on random regular graphs
The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {\sc Max Cut} of random regular graphs predicted by Zdeborov\'a and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
Open AccessThe Ising antiferromagnet and max cut on random regular graphs
The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {\sc Max Cut} of random regular graphs predicted by Zdeborov\'a and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.