← All problems

The conjectured swap-distance bounds for graphical degree sequences

14 years old · traced to

For a degree sequence d={d1,d2,…,dn}\mathbf{d}=\{d_1,d_2,\ldots,d_n\}, let m=(∑di)/2m=(\sum d_i)/2 be the number of edges in any realization, and let

m∗=∑min⁡(di,n−di).m^*=\sum\min(d_i,n-d_i).

For realizations G1G_1 and G2G_2 of this degree sequence, write H′(G1,G2)H'(G_1,G_2) for the relevant discrepancy measure and distu(G1,G2)\mathbf{dist}_u(G_1,G_2) for their swap-distance. The swap-distance bounds conjecture. The following inequalities hold:

  1. distu(G1,G2)≤H′(G1,G2)⋅(1−m/(3n2))\mathbf{dist}_u(G_1,G_2)\le H'(G_1,G_2)\cdot(1-m/(3n^2));
  2. distu(G1,G2)≤m∗(1/2−m/(6n2))\mathbf{dist}_u(G_1,G_2)\le m^*(1/2-m/(6n^2));
  3. distu(G1,G2)≤m(1−m/(3n2))\mathbf{dist}_u(G_1,G_2)\le m(1-m/(3n^2)); and
  4. distu(G1,G2)≤5n2/24\mathbf{dist}_u(G_1,G_2)\le 5n^2/24.

These proposed bounds refine the preceding general upper bound on swap-distance and are intended to improve estimates for realizations of a common graphical degree sequence. The source provides no resolution of these statements.

References
  1. Péter L. Erdős, Zoltán Király and István Miklós, “On the swap-distances of different realizations of a graphical degree sequence”, arXiv:1205.2842 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.