PaperlayerView exact revision on arXiv

Source-linked AI summary

A stronger bound for the strong chromatic index

Henning Bruhn, Felix Joos

arXiv:1504.02583v1math.COcs.DMmath.PR

TL;DR

If true, the conjecture would be optimal, because a blow-up of the 5-cycle attains equality. The paper improves the sparsity and coloring steps of a probabilistic approach and develops a Talagrand-type inequality that excludes exceptional outcomes. The paper improves the prior strong-edge-coloring bound for sufficiently large maximum degree, with asymptotically best-possible sparsity and a coloring lemma needing fewer colors.

  • Problem

    If true, the conjecture would be optimal, because a blow-up of the 5-cycle attains equality.

    Source: §1 · p. 1

  • Method

    The paper improves the sparsity and coloring steps of a probabilistic approach and develops a Talagrand-type inequality that excludes exceptional outcomes.

    Source: §1 · p. 2

  • Results

    The paper improves the prior strong-edge-coloring bound for sufficiently large maximum degree, with asymptotically best-possible sparsity and a coloring lemma needing fewer colors.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The resulting approach combines stronger sparsity and coloring lemmas with a concentration inequality that can ignore very rare large effects.

    Source: §1 · p. 2, §7 · p. 15

    The authors state that the method cannot go beyond 1.73∆(G)² because the sparsity bound permits a neighborhood clique of that size.

    Source: §2 · p. 4

Abstract

from arXiv · show

We prove $\chi_s'(G)\leq 1.93 \Delta(G)^2$ for graphs of sufficiently large maximum degree where $\chi_s'(G)$ is the strong chromatic index of $G$. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where it is allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.

1 Introduction

The introduction frames strong edge coloring as a harder problem than ordinary edge coloring and builds on probabilistic methods for improving its bounds. The paper improves both parts of that approach and also gives a bound for strong cliques.

1 Introduction

  • A strong edge coloring partitions the edges into induced matchings; the minimum number of such classes is the strong chromatic index χ′ s(G).Ordinary edge coloring instead partitions the edges into matchings.Source: §1 · p. 1
  • Blow-ups of the 5-cycle attain equality in the strong edge coloring conjecture, while induced matchings are harder to bound than ordinary matchings.The introduction presents this difficulty as a reason strong edge coloring is more challenging.Source: §1 · pp. 1, 3
  • Molloy and Reed used probabilistic coloring in two steps: sparsity of neighborhoods in L2(G), followed by a coloring result for graphs with sparse neighborhoods.A strong edge coloring corresponds to a vertex coloring of the square of the linegraph.Source: §1 · pp. 1–2
  • The paper improves both steps of the probabilistic approach: its sparsity result is asymptotically best-possible, and its coloring lemma needs fewer colors.The main theorem applies to graphs of sufficiently large maximum degree.Source: §1 · pp. 1–2
  • For graphs with maximum degree ∆≥400, every strong clique has size at most 1.74∆².A strong clique is a clique in the square of the linegraph.Source: §1 · p. 2

2 Outline and proof of Theorem 1

The proof colors edges by viewing them as vertices of the squared line graph, then combines a sparsity bound with a coloring lemma to obtain the 1.93∆(G)^2 bound.

2 Outline and proof of Theorem 1

  • The proof views strong edge coloring as vertex coloring in L2(G), then uses sparse neighborhoods and a probabilistic coloring lemma.The strong neighborhood of an edge is its neighborhood in L2(G).Source: §2 · p. 3
  • The proof applies Lemma 2 with r = 2∆^2, δ = 0.24, and γ = 0.035.This application follows the neighborhood bound from Lemma 4.Source: §2 · p. 4
  • The authors improve both steps of Molloy and Reed’s approach: their sparsity bound is asymptotically best-possible, and their coloring lemma needs fewer colors.The paper says the new sparsity bound is nearly optimal and contrasts its coloring parameter with Molloy and Reed’s.Source: §2 · p. 4
  • 1.93∆(G)^2 is the resulting strong chromatic-index bound; the new sparsity lemma with Molloy and Reed’s coloring lemma gives 1.99∆(G)^2.The paper reports that its coloring lemma then yields the 1.93 factor.Source: §2 · p. 4
  • The method cannot beat 1.73∆(G)^2, even with a vastly improved coloring lemma, because its sparsity bound does not exclude such a neighborhood clique.The stated ceiling follows from using edge densities alone.Source: §2 · p. 4

3 Density of the strong neighborhood

The section proves a sparsity lemma for strong neighborhoods by bounding the edges induced by an edge’s neighborhood in the square line graph. It parameterizes local structure to combine triangle, edge, path, and 4-cycle counts into a nearly tight bound.

3 Density of the strong neighborhood

  • Lemma 4 bounds the number of edges induced by an edge’s strong neighborhood in L2(G), the square of the line graph.The proof may assume G is Δ-regular by embedding it in a Δ-regular graph, which only increases the induced-edge count.Source: §3 · pp. 4–5
  • The proof parameterizes the neighborhood using α for triangles through e and β for 4-cycles through e plus certain incident triangles.It sets X to the neighbors of either endpoint of e, excluding the endpoints, and uses |X| = (2 − α)Δ − 2.Source: §3 · pp. 4–5
  • The edge-count estimate combines paths crossing from X through Y with 4-cycles between X and Y, which reduce strong-neighborhood degrees.Each counted 4-cycle reduces the degree of four edges; the proof also uses Cauchy–Schwarz when estimating the number of such cycles.Source: §3 · pp. 5–7
  • The contribution is to parameterize structural elements also used by Molloy and Reed and combine them to obtain a nearly tight bound.The section notes that Lemma 4 bounds the largest clique in L2(G), but this did not significantly improve Theorem 3.Source: §3 · p. 8

4 The sparsity lemma is best-possible

This section constructs graphs whose strong neighborhoods nearly attain the sparsity lemma’s density bound. The construction uses Hadamard codes to organize edges between two vertex sets.

4 The sparsity lemma is best-possible

  • The construction uses Hadamard-code sets with controlled sizes, element frequencies, and pairwise intersections.For distinct sets, the intersection size is either 0 or n/4; each element belongs to n − 1 sets.Source: §4 · pp. 8–9
  • The graph is built from two copies of the ground set, a set Y indexed by code sets, and vertices u and v joined to the respective copies.The resulting maximum degree is Δ = n + 1.Source: §4 · p. 9
  • The constructed graph’s strong-neighborhood density asymptotically coincides with the bound of Lemma 4.The construction has 2Δ² − O(Δ) edges between X and Y.Source: §4 · p. 9

5 The coloring procedure

The section modifies the Molloy–Reed probabilistic coloring approach to save colors in vertex neighborhoods. It estimates repeated colors after a random coloring and conflict-resolution step, then uses concentration and the Lovász Local Lemma to obtain a global coloring.

5 The coloring procedure

  • Unlike the basic procedure that uncolors both endpoints of a conflict, the modified approach counts repeated colors beyond pairs.It introduces P_u for same-colored nonadjacent pairs remaining in N(u), and T_u for same-colored nonadjacent triples, to control overcounting.Source: §5 · p. 10
  • The procedure first assigns each vertex one of C = ⌈(1 − γ)r⌉ colors independently, then independently orients edges to resolve conflicts.When adjacent vertices share a color, the orientation determines which endpoint is uncolored.Source: §5 · p. 10
  • The procedure seeks at least γr saved colors in each neighborhood so remaining uncolored vertices can be colored greedily.The savings are bounded below by P_u − T_u; the proof estimates these quantities and their concentration.Source: §5 · pp. 10, 12, 13
  • The Lovász Local Lemma turns the local neighborhood conditions into a coloring satisfying them globally.The section uses concentration of P_u and T_u and notes that each bad event depends only on events associated with vertices within distance two.Source: §5 · pp. 11, 13

6 How to possibly save more colors

The 1.93Δ² bound remains well above the conjectured 1.25Δ², but the authors identify structural differences that may permit improvement. They explain why the current sparsity argument does not capture those differences and say they could not exploit them substantially.

6 How to possibly save more colors

  • The 1.93Δ² bound remains far from the conjectured 1.25Δ², and the authors see possible improvements through more sophisticated arguments.They identify two observations that motivate this hope.Source: §6 · p. 13
  • The two proof steps are dissociated: the coloring lemma uses strong-neighborhood sparsity but no structural information about coloring edges.The authors suggest that using the edge-coloring structure could help.Source: §6 · p. 13
  • The sparsity lemma is asymptotically tight, but the blow-up of the 5-cycle has much sparser strong neighborhoods.For this example, Δ=2k and each edge’s strong neighborhood is the rest of the graph; its induced edge count is about 25/32Δ⁴, versus 3/2Δ⁴ in Lemma 4.Source: §6 · p. 13
  • Dense strong neighborhoods require many 4-cycles, which lower the square-linegraph degrees of their edges below 2Δ².The authors could not exploit this observation to obtain a substantial improvement.Source: §6 · pp. 13–14

7 Talagrand’s inequality and exceptional outcomes

Standard concentration inequalities require random variables to be sufficiently smooth, but rare outcomes can give the coloring variables large single-coordinate effects. The paper modifies Talagrand’s framework to exclude exceptional outcomes and gives conditions under which concentration still follows.

7 Talagrand’s inequality and exceptional outcomes

  • Talagrand’s inequality is unusable for the coloring variables when changing one color can affect up to r² counted pairs, although useful concentration requires deviations small relative to E[Pu].Such very large effects are rare, and the authors argue they should not determine whether the variable concentrates.Source: §7 · pp. 14–15
  • The paper defines upward (s, c)-certificates by requiring a small index set to witness that X cannot fall much under limited coordinate changes, comparing only outcomes outside Ω*.The definition allows an exceptional set of outcomes to be excluded.Source: §7 · p. 15
  • The paper separately bounds the distance between the median and expectation under upward-certificate assumptions.It notes that the concentration inequality is centered on med(X), while typical applications have a median close to the expectation.Source: §7 · pp. 15–16
  • The certificate framework also covers downward certificates, obtained by reversing the inequality for X.The paper states that its concentration lemmas remain valid for downward certificates.Source: §7 · p. 17
  • For independent product spaces with sufficiently rare Ω* and upward or downward certificates, the paper gives a Talagrand-type concentration bound.The stated setup assumes P[Ω*] ≤ M^-2 and t > 50c√s; the displayed probability bound is not fully legible in the supplied passage.Source: §7 · p. 17

8 Concentration for coloring procedure

The authors prove concentration for the pair- and triple-counting variables used in their coloring argument. They establish certificate bounds for these variables outside a set where some color appears too often.

8 Concentration for coloring procedure

  • The proof establishes that Pu and Tu, counting same-colored pairs and triples in N(u), are tightly concentrated around their expectations.The argument treats Pu explicitly and adapts it for Tu.Source: §8 · pp. 17–18
  • For Pu, the authors use downward certificates with s=3r and c=log²r outside outcomes where a color appears more than log r times in N(u).The certificate index set includes N(u), plus witnesses and edges associated with vertices uncolored during conflict resolution.Source: §8 · p. 18
  • A coordinate can distinguish two colors only in the specified witness case, so no coordinate can be a λ-difference for three or more colors.This bounds how many pairs a color contributes and supports the certificate argument for Pu.Source: §8 · pp. 18–19
  • For Tu, a color can contribute up to log³r/6 triples outside the exceptional set, requiring c=log³r and t=log⁴r√r in the application.The paper says the increased deviation compensates for the larger certificate parameter.Source: §8 · p. 19

9 Exceptional outcomes spoil triangle counting

The authors use their exceptional-outcome concentration inequality on triangle counts in G(n,p), extending the application beyond the coloring argument. By iterating the bound, they obtain strong concentration for probabilities down to p ≥ n^-1+β for every β > 0.

9 Exceptional outcomes spoil triangle counting

  • The paper’s motivation is concentration of T around E[T] when np → ∞, allowing deviations up to εn³p³ for fixed small ε.For larger p, changing one edge affects at most n triangles, and McDiarmid’s inequality suffices from p ≥ n^-1/3+γ.Source: §9 · p. 19
  • When p ≥ n^(−1/3+γ), N·n² tends to infinity; a version of McDiarmid’s inequality for binary random variables (see) allows this threshold to be dropped to p ≥ n^(−2/5+γ).Source: §9 · p. 19
  • The application excludes outcomes where an edge lies in more than n^δ triangles and outcomes where the total triangle count is unusually large.The authors add both kinds of outcomes to the exceptional set.Source: §9 · p. 20
  • Strong concentration of the triangle count follows for p ≥ n^-1+β for every β > 0 by iterating the paper’s inequality.The progression includes concentration for p ≥ n^-9/10+γ and then p ≥ n^-19/20+γ.Source: §9 · p. 20
Loading 1504.02583v1…