1.7k citations
- Technion – Israel Institute of TechnologyIL151 papers
- Oranim Academic College of EducationIL134 papers
- Tel Aviv UniversityIL55 papers
- Heidelberg UniversityDE36 papers
- Carmel (Israel)IL29 papers
- Columbia UniversityUS25 papers
- Massachusetts Institute of TechnologyUS25 papers
- National Research University Higher School of EconomicsRU25 papers
- University of AmsterdamNL22 papers
- Hebrew University of JerusalemIL21 papers
- Princeton UniversityUS21 papers
- Centre National de la Recherche ScientifiqueFR20 papers
5 papers · 2 filters
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…
The Max-Flow Min-Cut Theorem for Countable Networks
Ron Aharoni, Eli Berger, Agelos Georgakopoulos +2
We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are "orthogonal" to each other…
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…
On the Density of a Graph and its Blowup
Asaf Shapira, Raphael Yuster
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n,p) contains the smallest density of copies of K…
Multigraphs (only) satisfy a weak triangle removal lemma
Asaf Shapira, Raphael Yuster
The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can…