23 citations · 54 across the 45 of their papers we have counts for
5 papers · 1 filter
Exact Bounds for Some Hypergraph Saturation Problems
Guy Moshkovitz, Asaf Shapira
Let W_n(p,q) denote the minimum number of edges in an n x n bipartite graph G on vertex sets X,Y that satisfies the following condition; one can add the edges between X and Y that…
Small Complete Minors Above the Extremal Edge Density
Asaf Shapira, Benny Sudakov
A fundamental result of Mader from 1972 asserts that a graph of high average degree contains a highly connected subgraph with roughly the same average degree. We prove a lemma show…
Ramsey Theory, Integer Partitions and a New Proof of the Erdos-Szekeres Theorem
Guy Moshkovitz, Asaf Shapira
Let H be a k-uniform hypergraph whose vertices are the integers 1,...,N. We say that H contains a monotone path of length n if there are x_1 < x_2 < ... < x_{n+k-1} so that H conta…
A Note on the Balanced ST-Connectivity
Shiva Kintali, Asaf Shapira
We prove that every YES instance of Balanced ST-Connectivity has a balanced path of polynomial length.
Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
Hao Huang, Jie Ma, Asaf Shapira +2
A minimum feedback arc set of a directed graph is a smallest set of arcs whose removal makes acyclic. Its cardinality is denoted by . We show that an Eulerian digraph…