{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihmtho5kkjozdieu4s7hvaopdxa4lbagtczs5unwjbytgavebekym",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhu7qzgynlo2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.22702v1",
  "publishedAt": "2026-03-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yumou Fei"
  ],
  "textContent": "**Authors:** Yumou Fei\n\nWe 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.",
  "title": "Testing Properties of Edge Distributions"
}