Answer: Yes.
Theorem 3.2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateConsider \infmax on undirected graphs with the linear threshold model. There exists an instance where the greedy algorithm only achieves a $(1- (1 - 1/k)^k + O(1/k^{0.2}))$-approximation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For each sufficiently large \(k\), does there exist a finite catalogue \(\mathcal H\) of equal-size \(n\) undirected linear-threshold community templates and rational community masses \(\mu_H\), with \(\sum_H\mu_H=1\), such that assigning each community \(k\) seeds by template-wise greedy yields aggregate infected-mass ratio at most \(1-(1-1/k)^k+Ck^{-1/5}\) relative to the best template-wise \(k\)-seed assignments, for some constant \(C\)?
A society is given by its support: a finite nonempty catalogue \(\mathcal H\) of simple, unweighted, undirected graphs on the labelled vertex set \(\{1,\ldots,n\}\), each with positive binary-rational mass \(\mu_H\), where \(\sum_H\mu_H=1\). The support size is \(\tau=|\mathcal H|\), not the number of possible templates. Let \(m=n\) and let \(L\) be the total encoding bit length; state any running times in \(m,\tau,L,k\).
Communities have no edges between them. In a template, seeds are initially infected; independently, each nonisolated vertex samples an integer threshold uniformly from \(\{1,\ldots,\deg_H(v)\}\), and becomes permanently infected when at least that many neighbors are infected. Unseeded isolated vertices remain uninfected. Write \(\sigma_H(S)\) for the expected final number infected, including seeds.
For \(1\leq k\leq n\), a template-wise assignment chooses exactly \(k\) distinct vertices \(S_H\) in every template and uses that same set throughout its community mass. Its infected mass is \(I((S_H)_H)=\sum_H\mu_H\sigma_H(S_H)/n\); define \(\mathrm{OPT}=\max_{(S_H)_H:\,|S_H|=k}I((S_H)_H)\).
Template-wise greedy starts from the empty set in each template and repeatedly adds a vertex maximizing the exact marginal increase in \(\sigma_H\), breaking ties by smallest vertex label. Assume exact influence-value oracle access. Let \(I_{\mathrm{gr}}\) be its infected mass.
Do there exist constants \(C>0\) and \(k_0\) such that, for every integer \(k\geq k_0\), some \(n\geq k\) and society as defined above satisfy \(I_{\mathrm{gr}}/\mathrm{OPT}\leq 1-(1-1/k)^k+Ck^{-1/5}\)?
For a single finite undirected graph, greedy has examples with ratio at most \(1-(1-1/k)^k+O(k^{-1/5})\), while its universal guarantee is \(1-(1-1/k)^k+\Omega(k^{-3})\). [Schoenebeck, Tao, and Yu](https://arxiv.org/html/2002.11679)
No separate result specifically formulated for distributional societies was verified.
Yes. Singleton supports are allowed. More generally, the template-wise objective separates into independent single-graph objectives, so no separate distributional construction is needed.
We use the following known result, supplied in the question: there exist constants \(C>0\) and \(k_0\) such that, for every integer \(k\geq k_0\), there is a finite simple, unweighted, undirected graph \(G_k\), with at least \(k\) vertices, and a valid greedy trajectory whose final seed set \(B_k\) satisfies
\(
\frac{\sigma_{G_k}(B_k)}
{\max_{|S|=k}\sigma_{G_k}(S)}
\leq 1-(1-1/k)^k+Ck^{-1/5}.
\)
This is [Schoenebeck–Tao–Yu, Theorem 3.2 and Example 3.3](https://arxiv.org/html/2002.11679#S3). Their construction is indexed by every sufficiently large integer \(k\). Definition 2.1 uses exactly the threshold process in this question: independent uniform integer thresholds, seeds initially infected, and unseeded isolated vertices never infected.
A greedy trajectory permitted by that theorem can be realized under smallest-label tie-breaking.
Fix its ordered selections \(b_1,\ldots,b_k\). Relabel \(b_i\) by \(i\), and assign the remaining vertices distinct labels greater than \(k\). Let \(\pi\) be this relabelling and \(H_k\) the resulting graph.
For every seed set \(S\), we have
\(
\sigma_{H_k}(\pi(S))=\sigma_{G_k}(S).
\)
Indeed, relabelling preserves degrees and adjacency. Coupling each vertex’s threshold with its relabelled counterpart makes the infected sets correspond at every iteration, hence also at termination.
We now prove by induction that smallest-label greedy selects \(1,\ldots,k\) in that order. Suppose it has selected \(1,\ldots,i-1\). By influence invariance and validity of the original trajectory, vertex \(i\) maximizes the marginal influence. Moreover, every other unselected vertex has label greater than \(i\). Thus the prescribed tie-breaking selects \(i\). This proves the induction.
Relabelling also preserves the optimum, because it bijects the seed sets of size \(k\). Consequently, the displayed approximation bound holds for the required deterministic greedy rule on \(H_k\).
For any society, define
\(
M_H=\max_{|S|=k}\sigma_H(S)
\)
and let \(B_H\) be its prescribed greedy seed set.
Every feasible assignment satisfies
\(
I((S_H)_H)\leq \frac1n\sum_{H\in\mathcal H}\mu_H M_H.
\)
Conversely, each maximum is attained because there are finitely many seed sets. Choosing an attaining set independently in every template is feasible. Hence
\(
\mathrm{OPT}=\frac1n\sum_{H\in\mathcal H}\mu_H M_H.
\)
Since seeds remain infected, \(M_H\geq k>0\). Therefore, defining
\(
r_H=\frac{\sigma_H(B_H)}{M_H},
\qquad
w_H=\frac{\mu_HM_H}{\sum_{J\in\mathcal H}\mu_JM_J},
\)
we obtain
\(
\frac{I_{\mathrm{gr}}}{\mathrm{OPT}}
=\sum_{H\in\mathcal H}w_Hr_H.
\)
The weights are positive and sum to one. Thus the society ratio is a weighted average of its single-template ratios. Conversely, every single-graph ratio occurs in a singleton society.
For each \(k\geq k_0\), take the relabelled graph \(H_k\), put \(n=|V(H_k)|\), and choose
\(
\mathcal H=\{H_k\},\qquad \mu_{H_k}=1.
\)
This is an admissible society: its support is finite and nonempty, its sole mass is a positive binary rational, and \(n\geq k\). There are no edges between communities because there is only one template community.
The common normalization cancels:
\(
\frac{I_{\mathrm{gr}}}{\mathrm{OPT}}
=
\frac{\sigma_{H_k}(\{1,\ldots,k\})/n}
{\max_{|S|=k}\sigma_{H_k}(S)/n}
\leq
1-(1-1/k)^k+Ck^{-1/5}.
\)
The constants from the single-graph theorem therefore establish exactly the requested statement.
⟨structured verdict parsed — rendered above⟩
The output proves the requested existence statement. The cited result applies to the specified diffusion model, and both the tie-breaking reduction and singleton-society construction are valid. No major or minor issues were found.
The prover states the imported result precisely: fixed constants \(C>0\) and \(k_0\), and a suitable graph and greedy trajectory for every integer \(k\geq k_0\).
The citation supports this formulation. Theorem 3.2 gives the approximation upper bound; Example 3.3 constructs an unweighted, simple, undirected graph indexed by sufficiently large integer \(k\); and Proposition 3.5 identifies its greedy selections. Definition 2.1 specifies independent uniform integer thresholds, initially infected seeds, and infinite thresholds at isolated vertices. These agree with the task. [Schoenebeck–Tao–Yu, Definitions 2.1 and 2.5 and Section 3](https://arxiv.org/html/2002.11679#S3).
The asymptotic upper bound supplies constants independent of \(k\). Increasing \(k_0\) as necessary is consistent with the task. No explicit numerical constants are required.
The selected vertices \(b_1,\ldots,b_k\) are distinct because a valid greedy trajectory selects only unselected vertices. Thus assigning \(b_i\) label \(i\), and assigning all other vertices the remaining labels, defines a bijection onto \(\{1,\ldots,n\}\).
The coupling argument is complete: adjacency and degrees are preserved, corresponding thresholds have the same distributions, and corresponding infected sets agree initially and after every update. Isolated vertices also correspond. Consequently,
\(\sigma_{H_k}(\pi(S))=\sigma_{G_k}(S)\)
holds for every seed set \(S\).
The induction includes the base case through the empty selected prefix when \(i=1\).
At iteration \(i\), influence invariance transfers the original marginal-maximization property to vertex \(i\). Every other available vertex has a larger label: labels below \(i\) have already been selected. Hence smallest-label tie-breaking selects \(i\), even if other vertices have equal marginal influence.
This establishes the entire ordered selection \(1,\ldots,k\).
Relabelling bijects all seed sets of cardinality exactly \(k\) and preserves their influence values. Both the numerator for the realized greedy trajectory and the optimal denominator are therefore preserved. The imported ratio bound transfers without changing its constants.
For every template, the maximum \(M_H\) exists because the feasible family is finite and nonempty. The assignment constraint allows an independent choice in each template, so the upper bound
\(\mathrm{OPT}\leq n^{-1}\sum_H\mu_HM_H\)
is attained.
Seeds remain infected, giving \(M_H\geq k>0\). Thus the ratio and weights are well-defined. Substitution verifies the weighted-average identity, and positivity of the masses verifies that the weights are positive and sum to one.
Its support has size \(\tau=1\), its mass \(1\) is a positive binary rational, and its graph is finite with \(n\geq k\). Relabelling supplies the required labelled vertex set. A single community introduces no edges between communities.
The common factor \(1/n\) cancels from the ratio, yielding exactly the requested inequality for every \(k\geq k_0\).
This is an existence proof, with no running-time claim requiring expression in \(m,\tau,L,k\). It establishes the requested greedy approximation examples; it does not classify computational complexity.
Required clarification or repair: None.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.