On restricted sumsets with bounded degree relations

Abstract Given two subsets and a binary relation , the restricted sumset of with respect to is defined as . When is taken as the equality relation, determining the minimum value of is the famous Erdős–Heilbronn problem, which was solved separately by Dias da Silva, Hamidoune and Alon, Nathanson and Ruzsa. Lev later conjectured that if with and is a matching between subsets of and , then . We confirm this conjecture in the case where for any , provided that for some sufficiently large depending only on . Our proof builds on a recent work by Bollobás, Leader, and Tiba, and a rectifiability argument developed by Green and Ruzsa. Furthermore, our method extends to cases when is a degree‐bounded relation, either on both sides and or solely on the smaller set. In addition, we construct subsets with such that for any prime number , where is a matching on . This extends an earlier construction by Lev and highlights a distinction between the combinatorial notion of the restricted sumset and the classcial Erdős–Heilbronn problem, where holds given is the equality relation on and .