7 papers
Ranked spreadness and sample-based testing
Gaia Carenini
In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coor…
A quantitative container characterization of one-sided testability
Gaia Carenini, Cameron Seth, Yuichi Yoshida
We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira.…
Embedding Induced Bounded Degree Graphs
Gaia Carenini
We prove a sparse embedding theorem for induced embeddings of bounded-degree graphs. The theorem applies to pairs : the graph supplies the positive edges of the…
A unified abstract regularity lemma
Gaia Carenini, Leonardo Franchi
The goal of this short note is to prove a unified abstract regularity lemma which recovers Szemerédi's graph regularity lemma, Green's arithmetic regularity lemma, and a regularit…
A Sparse Transference Principle for a Non-Monotone Ramsey Property
Gaia Carenini
We prove a sparse transference theorem for induced Ramsey graphs. The theorem transfers the weighted random-host proof of Aragão, Campos, Dahia, Filipe, and Marciano to the sparse…
A strengthening of Chang's lemma
Gaia Carenini, Leonardo Franchi
We prove a strengthening of Chang's lemma for subsets of . The classical conclusion that the large spectrum is contained in a subspace of dimension at most $2\vareps…