A. Shapira

activity

20072026

most citedA Proof of Green's Conjecture Regarding the Removal Properties of Sets of Linear Equations

23 citations · 54 across the 45 of their papers we have counts for

collaborators

Showing math.COShow all

52 papers · 1 filter

math.CO2026

NP-Hardness of Generalized-Turán Graph Modification Problems

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

For graphs $G, T$ and a graph-family $H$ , let $e x (G, T, H)$ denote the maximum possible number of copies of $T$ in an $H$ -free subgraph of $G$ . Alon and…

math.CO2026

A Tight Erdős-Stone Bound for All Graph Densities

Asaf Shapira, Raphael Yuster

The Erdős--Stone Theorem asserts that if a graph has edge density $1 - 1/ r + δ$ then it contains a complete $(r + 1)$ -partite graph with $b$ vertices in each part, where $b=b_n(r,δ) \gg…

math.CO2026

On Ramsey Properties of k-Majority Tournaments

Asaf Shapira, Raphael Yuster

A central objective in Ramsey theory is determining whether restricted families of discrete structures necessarily contain substantially larger homogeneous substructures, compared…

math.CO2025

Regularity for hypergraphs with bounded VC $_{2}$ dimension

Lior Gishboliner, Asaf Shapira, Yuval Wigderson

While Szemerédi's graph regularity lemma is an indispensable tool for studying extremal problems in graph theory, using it comes with a hefty price, since a worst-case graph may on…

math.CO2025

When does a tree activate the random graph?

Asaf Cohen Antonir, Yuval Peled, Asaf Shapira +2

Let $F$ and $G$ be two graphs. A spanning subgraph $H$ of $G$ is called weakly $F$ -saturated if one can add to $H$ the edges of $G ∖ H$ in some order, so that whenever a ne…

math.CO2025

Is it easy to regularize a hypergraph with easy links?

Lior Gishboliner, Asaf Shapira, Yuval Wigderson

A partition of a (hyper)graph is $ε$ -homogenous if the edge densities between almost all clusters are either at most $ε$ or at least $1 - ε$ . Suppose a…

math.CO2025

Hardness of Hypergraph Edge Modification Problems

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

For a fixed graph $F$ , let $e x_{F} (G)$ denote the size of the largest $F$ -free subgraph of $G$ . Computing or estimating $e x_{F} (G)$ for various pairs $F, G$ is one of the central proble…

math.CO2024

A Generalization of Varnavides's Theorem

Asaf Shapira

A linear equation $E$ is said to be sparse if there is $c > 0$ so that every subset of $[n]$ of size $n^{1 - c}$ contains a solution of $E$ in distinct integers. The problem of charact…

math.CO2023

Trimming forests is hard (unless they are made of stars)

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

Graph modification problems ask for the minimal number of vertex/edge additions/deletions needed to make a graph satisfy some predetermined property. A (meta) problem of this type,…

math.CO2023

On Rödl's Theorem for Cographs

Lior Gishboliner, Asaf Shapira

A theorem of Rödl states that for every fixed $F$ and $ε > 0$ there is $δ = δ_{F} (ε)$ so that every induced $F$ -free graph contains a vertex set of size $δ n$ whose ed…

math.CO2023

Testing versus estimation of graph properties, revisited

Lior Gishboliner, Nick Kushnir, Asaf Shapira

A distance estimator for a graph property $P$ is an algorithm that given $G$ and $α, ε > 0$ distinguishes between the case that $G$ is $(α - ε)$ -close to…

math.CO2023

A new approach for the Brown-Erdos-Sos problem

Asaf Shapira, Mykhaylo Tyomkyn

The celebrated Brown-Erdős-Sós conjecture states that for every fixed $e$ , every $3$ -uniform hypergraph with $Ω (n^{2})$ edges contains $e$ edges spanned by $e + 3$ vertices. Up to this…

math.CO2023★ 1 cited

An efficient asymmetric removal lemma and its limitations

Lior Gishboliner, Asaf Shapira, Yuval Wigderson

The triangle removal states that if $G$ contains $ε n^{2}$ edge-disjoint triangles, then $G$ contains $δ (ε) n^{3}$ triangles. Unfortunately, there are no sensible bo…

math.CO2022

Bounding the number of odd paths in planar graphs via convex optimization

Asaf Cohen Antonir, Asaf Shapira

Let $N_{P} (n, H)$ denote the maximum number of copies of $H$ in an $n$ vertex planar graph. The problem of bounding this function for various graphs $H$ has been extensive…

math.CO2022★ 1 cited

Hypergraph removal with polynomial bounds

Lior Gishboliner, Asaf Shapira

Given a fixed $k$ -uniform hypergraph $F$ , the $F$ -removal lemma states that every hypergraph with few copies of $F$ can be made $F$ -free by the removal of few edges. Unfortunately,…

math.CO2021

Weakly saturated hypergraphs and a conjecture of Tuza

Asaf Shapira, Mykhaylo Tyomkyn

Given a fixed hypergraph $H$ , let $\mbox{wsat}(n,H)$ denote the smallest number of edges in an $n$ -vertex hypergraph $G$ , with the property that one can sequentially add the edges…

math.CO2021

Quasirandom Graphs and the Pantograph Equation

Asaf Shapira, Mykhaylo Tyomkyn

The pantograph differential equation and its solution, the deformed exponential function, are remarkable objects that appear in areas as diverse as combinatorics, number theory, st…

math.CO2020

Constructing Dense Grid-Free Linear $3$ -Graphs

Lior Gishboliner, Asaf Shapira

We show that there exist linear $3$ -uniform hypergraphs with $n$ vertices and $Ω (n^{2})$ edges which contain no copy of the $3 \times 3$ grid. This makes significant progress on a co…

math.CO2020

Testing linear inequalities of subgraph statistics

Lior Gishboliner, Asaf Shapira, Henrique Stagni

Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property $P$ and those that are far from satisfying…

math.CO2019

A New Bound for the Brown--Erdős--Sós Problem

David Conlon, Lior Gishboliner, Yevgeny Levanzov +1

Let $f (n, v, e)$ denote the maximum number of edges in a $3$ -uniform hypergraph not containing $e$ edges spanned by at most $v$ vertices. One of the most influential open problems in…

math.CO2019★ 2 cited

A Ramsey variant of the Brown-Erdős-Sós conjecture

Asaf Shapira, Mykhaylo Tyomkyn

An $r$ -uniform hypergraph ( $r$ -graph for short) is called linear if every pair of vertices belong to at most one edge. A linear $r$ -graph is complete if every pair of vertices are…

math.CO2019

A Tight Bound for Hyperaph Regularity

Guy Moshkovitz, Asaf Shapira

The hypergraph regularity lemma -- the extension of Szemerédi's graph regularity lemma to the setting of $k$ -uniform hypergraphs -- is one of the most celebrated combinatorial resu…

math.CO2019

Testing Graphs against an Unknown Distribution

Lior Gishboliner, Asaf Shapira

The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics…

math.CO2019

A quantitative Lovász criterion for Property B

Asaf Ferber, Asaf Shapira

A well known observation of Lovász is that if a hypergraph is not $2$ -colorable, then at least one pair of its edges intersect at a single vertex. %This very simple criterion turne…

NP-Hardness of Generalized-Turán Graph Modification Problems

A Tight Erdős-Stone Bound for All Graph Densities

On Ramsey Properties of k-Majority Tournaments

Regularity for hypergraphs with bounded VC2​ dimension

When does a tree activate the random graph?

Is it easy to regularize a hypergraph with easy links?

Hardness of Hypergraph Edge Modification Problems

A Generalization of Varnavides's Theorem

Trimming forests is hard (unless they are made of stars)

On Rödl's Theorem for Cographs

Testing versus estimation of graph properties, revisited

A new approach for the Brown-Erdos-Sos problem

An efficient asymmetric removal lemma and its limitations

Bounding the number of odd paths in planar graphs via convex optimization

Hypergraph removal with polynomial bounds

Weakly saturated hypergraphs and a conjecture of Tuza

Quasirandom Graphs and the Pantograph Equation

Constructing Dense Grid-Free Linear 3-Graphs

Testing linear inequalities of subgraph statistics

A New Bound for the Brown--Erdős--Sós Problem

A Ramsey variant of the Brown-Erdős-Sós conjecture

A Tight Bound for Hyperaph Regularity

Testing Graphs against an Unknown Distribution

A quantitative Lovász criterion for Property B

Regularity for hypergraphs with bounded VC $_{2}$ dimension

Constructing Dense Grid-Free Linear $3$ -Graphs