8 citations · 13 across the 5 of their papers we have counts for
5 papers · 1 filter
The K_4-free process
Guy Wolfovitz
We consider the K_4-free process. In this process, the edges of the complete n-vertex graph are traversed in a uniformly random order, and each traversed edge is added to an initia…
A concentration result with application to subgraph count
Guy Wolfovitz
Let H = (V,E) be a k-uniform hypergraph with a vertex set V and an edge set E. Let V_p be constructed by taking every vertex in V independently with probability p. Let X be the num…
Sub-Gaussian tails for the number of triangles in G(n,p)
Guy Wolfovitz
Let X be the random variable that counts the number of triangles in the random graph G(n,p). We show that for some absolute constant c, the probability that X deviates from its exp…
Triangle-free Subgraphs at the Triangle-Free Process
Guy Wolfovitz
We consider the triangle-free process: given an integer n, start by taking a uniformly random ordering of the edges of the complete n-vertex graph K_n. Then, traverse the ordered e…
Lower Bounds for the Size of Random Maximal H-Free Graphs
Guy Wolfovitz
We consider the next greedy randomized process for generating maximal H-free graphs: Given a fixed graph H and an integer n, start by taking a uniformly random permutation of the e…