2024/10/07 by Frederik Garbe, Jan Hladký, Garbe, Frederik +1
Computer Science · Mathematics · #Optimization and Variational Analysis #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.5070/c65465674
It is well-known that if \((A,B)\) is an \(\tfracε2\)-regular pair (in the sense of Szemerédi) then there exist sets \(A'⊂ A\) and \(B'⊂ B\) with \(|A'|≤ ε|A|\) and \(|B'|≤ ε|B|\) so that the degrees of all vertices in \(A∖ A'\) differ by at most \(ε|B|\) and the degrees of all vertices in \(B∖ B'\) differ by at most \(ε|A|\). We call such a property \(ε\)-degularity. This leads to the notion of an \(ε\)-degular partition of a graph in the same way as the definition of \(ε\)-regular pairs leads to the notion of \(ε\)-regular partitions.We show that there exist graphs in which any \(ε\)-degular partition requires the number of clusters to be \(tower(Θ(ε-1/3))\). That is, even though degularity is a substantial relaxation of regularity, in general one cannot improve much on the bounds that come with Szemerédi's regularity lemma.Mathematics Subject Classifications: 05C35Keywords: Szemerédi's regularity lemma, degree