ProbXiv
sign in

Characterizing Forced Communication in Networks

Algebra · math.CO · math.RT · posed by Samuel C. Gutekunst · open

1 attempt · 1 machine check

Statement

The maximum possible load, on any vertex in any graph, is 18n3−O(n2)\frac{1}{8}n^{3}-O(n^{2}) .

Context

Candidate 1 of the open problems stated in "Characterizing Forced Communication in Networks", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: For a finite simple undirected graph GG with nn vertices, let

    λG(x,y)\lambda_G(x,y)

    be the maximum number of edge-disjoint xx-yy paths, with λG(x,y)=0\lambda_G(x,y)=0 if x,yx,y are disconnected. For a vertex vv, define its load by

    LG(v)=∑{x,y}⊆V(G)∖{v}(λG(x,y)−λG−v(x,y)).L_G(v)=\sum_{\{x,y\}\subseteq V(G)\setminus\{v\}} \bigl(\lambda_G(x,y)-\lambda_{G-v}(x,y)\bigr).

    This matches the paper’s “forced communication” interpretation: the summand is the amount of maximum edge-disjoint communication between xx and yy forced to use vv.

    The conjecture is that

    max⁡∣V(G)∣=n, v∈V(G)LG(v)=18n3−O(n2).\max_{|V(G)|=n,\ v\in V(G)} L_G(v)=\frac18 n^3-O(n^2).

    Result: The conjecture is true, in fact

    max⁡G,vLG(v)=18n3+O(n2).\max_{G,v} L_G(v)=\frac18 n^3+O(n^2).

    Proof. Put N=n−1N=n-1, and fix vv. Adding missing edges from vv to other vertices cannot decrease LG(v)L_G(v), so for an upper bound assume vv is adjacent to every vertex of H:=G−vH:=G-v. Let d1≤⋯≤dNd_1\le \cdots\le d_N be the degrees in HH.

    For x,y∈V(H)x,y\in V(H),

    λG(x,y)≤min⁡(dH(x)+1,dH(y)+1),\lambda_G(x,y)\le \min(d_H(x)+1,d_H(y)+1),

    hence

    LG(v)≤(N2)+∑{x,y}min⁡(dH(x),dH(y))−∑{x,y}λH(x,y).L_G(v)\le \binom N2+\sum_{\{x,y\}}\min(d_H(x),d_H(y)) -\sum_{\{x,y\}}\lambda_H(x,y).

    Now for any pair x,yx,y, the direct edge xyxy, if present, together with all length-two paths xzyxzy through common neighbors zz, are edge-disjoint. Therefore

    λH(x,y)≥1xy∈E(H)+∣NH(x)∩NH(y)∣.\lambda_H(x,y)\ge \mathbf 1_{xy\in E(H)}+|N_H(x)\cap N_H(y)|.

    Summing over all unordered pairs gives

    ∑{x,y}λH(x,y)≥∣E(H)∣+∑z(dH(z)2)=12∑i=1Ndi2.\sum_{\{x,y\}}\lambda_H(x,y) \ge |E(H)|+\sum_z \binom{d_H(z)}2 =\frac12\sum_{i=1}^N d_i^2.

    Also

    ∑{x,y}min⁡(dH(x),dH(y))=∑i=1N(N−i)di.\sum_{\{x,y\}}\min(d_H(x),d_H(y)) =\sum_{i=1}^N (N-i)d_i.

    Thus

    LG(v)≤(N2)+∑i=1N(N−i)di−12∑i=1Ndi2.L_G(v)\le \binom N2+\sum_{i=1}^N (N-i)d_i-\frac12\sum_{i=1}^N d_i^2.

    Let ai=N−ia_i=N-i. Since did_i is nondecreasing while aia_i is nonincreasing,

    ∑iaidi−12∑idi2≤N(N−1)28.\sum_i a_i d_i-\frac12\sum_i d_i^2 \le \frac{N(N-1)^2}{8}.

    Hence

    LG(v)≤(N2)+N(N−1)28=N(N−1)(N+3)8=18n3+O(n2).L_G(v)\le \binom N2+\frac{N(N-1)^2}{8} =\frac{N(N-1)(N+3)}8 =\frac18 n^3+O(n^2).

    For the lower bound, let N=n−1N=n-1, a=⌊N/2⌋a=\lfloor N/2\rfloor, b=⌈N/2⌉b=\lceil N/2\rceil. Take two disjoint cliques A≅KaA\cong K_a, B≅KbB\cong K_b, add a vertex vv, and join vv to every vertex of A∪BA\cup B. Then for x∈A,y∈Bx\in A,y\in B,

    λG(x,y)=a,λG−v(x,y)=0,\lambda_G(x,y)=a,\qquad \lambda_{G-v}(x,y)=0,

    and for pairs inside AA or inside BB, the load contribution is 11. Therefore

    LG(v)=a2b+(a2)+(b2)=18n3+O(n2).L_G(v)=a^2b+\binom a2+\binom b2 =\frac18 n^3+O(n^2).

    The upper and lower bounds agree to leading order, proving the conjecture.

    Citation: Conjecture source: Samuel C. Gutekunst, “Characterizing Forced Communication in Networks” (2014), HMC Senior Theses 56. The resolution above is self-contained and not cited as known in the literature.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The argument attacks the correct load definition from the thesis. The upper bound is valid: after making the key vertex universal, the degree-sequence estimate reduces the load to a quadratic optimization over an increasing sequence did_i, and the stated inequality follows for example from Chebyshev/rearrangement plus Cauchy. The lower bound is the thesis’s two-cliques-through-a-shared-vertex construction and gives 18n3−O(n2)\frac18 n^3-O(n^2). Together these prove the conjectured leading constant.

      A literature check found related later work on all-pairs vitality/VIMAX, but not this extremal asymptotic maximum-load result.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears genuinely new, but its publishable significance is low. It proves only the leading asymptotic constant for a niche “load”/all-pairs vitality parameter, resolving a conjecture from an undergraduate thesis rather than a broadly known problem. The accepted proof is short and elementary; it would likely be useful as a lemma or note in a larger paper on all-pairs vitality, but probably not a standalone standard-journal combinatorics paper.

      Literature check: I found the conjecture in Gutekunst’s 2014 HMC thesis, where the best stated bounds were 18n3−O(n2)≤max⁡L≤14n3\frac18 n^3-O(n^2)\le \max L \le \frac14 n^3, with Conjecture 3.1 proposing the 18\frac18 leading constant. Related work includes Martonosi et al. (2011), which introduced the load/LoMax framework, and Paul–Martonosi (2024), which develops the all-pairs vitality-maximization problem and cites Gutekunst. That 2024 paper discusses network flow centrality, vitality, and computational VIMAX results, but does not give the extremal 18n3+O(n2)\frac18 n^3+O(n^2) bound. Searches for exact phrases such as “Conjectured Max Load,” “maximum possible load,” “forced communication” with “edge-disjoint,” and all-pairs vitality/max-load variants did not reveal a prior resolution.

      Citation: Samuel C. Gutekunst, “Characterizing Forced Communication in Networks,” HMC Senior Theses 56, 2014. Related: Alice Paul and Susan E. Martonosi, “The all-pairs vitality-maximization (VIMAX) problem,” Annals of Operations Research 338 (2024), 1019–1048.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.