MathLabs

第4题

设 SS 是由 mm 个满足 1≤a<b≤n1\le a<b\le n 的正整数对 (a,b)(a,b) 组成的集合。证明存在至少 m(4m−n2)3n\dfrac{m(4m-n^2)}{3n} 个三元组 (a,b,c)(a,b,c)，使得 (a,b),(a,c)(a,b),(a,c) 和 (b,c)(b,c) 都属于 SS。
第 2/5 步：给每条边的公共邻点数作下界
上一步下一步
∣Di∩Dj∣≥di+dj−n((i,j)∈S)|D_i\cap D_j|\ge d_i+d_j-n\qquad((i,j)\in S)
详细分析

对边 (i,j)(i,j)，Di∩DjD_i\cap D_j 中的顶点与 i,ji,j 构成好三元组。两个邻点集都包含在 nn 个顶点中，由容斥原理 ∣Di∩Dj∣=di+dj−∣Di∪Dj∣≥di+dj−n|D_i\cap D_j|=d_i+d_j-|D_i\cup D_j|\ge d_i+d_j-n。