pith. sign in

arxiv: 1312.2994 · v1 · pith:3G7BXDMKnew · submitted 2013-12-10 · 🧮 math.CO

A counterexample to sparse removal

classification 🧮 math.CO
keywords graphalphaedgesgraphsmboxnumberremovalsparse
0
0 comments X
read the original abstract

The Tur\'{a}n number of a graph $H$, denoted $\mbox{ex}(n,H)$, is the maximum number of edges in an $n$-vertex graph with no subgraph isomorphic to $H$. Solymosi conjectured that if $H$ is any graph and $\mbox{ex}(n,H) = O(n^{\alpha})$ where $\alpha > 1$, then any $n$-vertex graph with the property that each edge lies in exactly one copy of $H$ has $o(n^{\alpha})$ edges. This can be viewed as conjecturing a possible extension of the removal lemma to sparse graphs, and is well-known to be true when $H$ is a non-bipartite graph, in particular when $H$ is a triangle, due to Ruzsa and Szemer\'{e}di. Using Sidon sets we exhibit infinitely many bipartite graphs $H$ for which the conjecture is false.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.