Testing Properties of Edge Distributions
This work addresses distribution testing for edge distributions, connecting to graph property testing and extremal combinatorics, but is incremental as it extends existing frameworks to a new context.
The paper tackles the problem of testing properties like bipartiteness, triangle-freeness, and square-freeness for probability distributions over graph edges, establishing nearly-tight sample complexity bounds of Θ(n), n^{4/3±o(1)}, and n^{9/8±o(1)} respectively.
We initiate the study of distribution testing for probability distributions over the edges of a graph, motivated by the closely related question of ``edge-distribution-free'' graph property testing. The main results of this paper are nearly-tight bounds on testing bipartiteness, triangle-freeness and square-freeness of edge distributions, whose sample complexities are shown to scale as $Î(n)$, $n^{4/3\pm o(1)}$ and $n^{9/8\pm o(1)}$, respectively. The technical core of our paper lies in the proof of the upper bound for testing square-freeness, wherein we develop new techniques based on certain birthday-paradox-type lemmas that may be of independent interest. We will discuss how our techniques fit into the general framework of distribution-free property testing. We will also discuss how our results are conceptually connected with Turán problems and subgraph removal lemmas in extremal combinatorics.