Abstract: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 $\Theta(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.
From: Yumou Fei [view email]
[v1]
Tue, 24 Mar 2026 01:49:11 UTC (46 KB)
[v2]
Wed, 12 Aug 2026 23:44:13 UTC (46 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。