Source-linked AI summary
Uniformly Weighted Graphical Designs
Zawad Chowdhury, Rekha R. Thomas
TL;DR
Uniformly weighted graphical designs are important but can be absent even in structured graphs, raising questions about their existence and size. The paper characterizes existence through two-valued eigenconfigurations and develops the associated polyhedral viewpoint. It applies this theory to families with designs of all strengths and to infinite families with none.
Problem
Uniformly weighted designs can be rare or nonexistent even in structured graphs, so the paper asks when they exist and how their cardinalities are controlled.
Method
The paper characterizes designs using two-valued eigenconfigurations, polyhedral geometry, binary integer programming, and Laplacian eigenvalue algebra.
Results
The paper provides a geometric existence criterion, characterizes threshold-graph designs, proves a geometric duality result for linear codes and orthogonal arrays, and constructs families with no designs of any strength.
Takeaways & Limitations
Uniformly weighted graphical designs admit a geometric and polyhedral analysis that yields both positive families and systematic nonexistence constructions.
Takeaways & Limitations
Whether most graphs are generically Laplacian irreducible remains open, despite strong experimental support and limited theoretical results.
Abstract
from arXiv · showhide
A graphical design is a subset of vertices of a graph, along with a weight for each chosen vertex, that can perfectly average chosen subspaces of functions on the graph. A design is uniformly weighted if all the weights are equal, and several well-known combinatorial objects such as orthogonal arrays, combinatorial block designs and t-wise permutations are uniformly weighted graphical designs. While one might expect to see uniformly weighted designs in structured graphs, they do not always exist. In this paper we characterize the existence of uniformly weighted graphical designs, and use our result to provide several families of graphs that have, and do not have, such designs. Our results offer a polyhedral view of the structures that control the existence and cardinalities of these designs. In particular, we characterize all uniformly weighted designs of threshold graphs, and provide a geometric proof of the duality of linear codes and linear orthogonal arrays. We also provide a novel construction for graphs whose Laplacian characteristic polynomials are almost irreducible, to produce families without uniformly weighted designs.
1. Introduction
The paper asks when uniformly weighted graphical designs exist and how small they can be, addressing their rarity even in structured graphs. It develops a geometric framework and applies it to examples and graph families with and without such designs.
- Graphical designs: Uniformly weighted designs average selected Laplacian eigenspaces using equal positive weights on chosen vertices.Graphical designs may use arbitrary weights, but uniform weighting requires aw = a > 0 for every selected vertex.
- Research questions: Uniformly weighted designs are rare and may fail to exist even in highly structured graphs, motivating existence and cardinality questions.The paper separately asks whether such designs exist at a given strength and whether one can meet the dimension bound.
- Main contribution: The main geometric result characterizes existence through eigenconfigurations that take exactly two values under a linear functional.The associated eigenpolytopes also encode polyhedral information about uniformly weighted designs and their cardinalities.
- Combinatorial connections: Orthogonal arrays, combinatorial block designs, and t-wise permutations fit the graphical-design framework through Hamming, Johnson, and transposition graphs.For fixed strength, the summed dimensions of averaged eigenspaces are O(n^t) in all three settings.
- Examples and families: The paper applies this framework to the icosahedral graph, binary hypercube, complete tripartite graphs, threshold graphs, and other structured families.It characterizes threshold-graph designs and gives a geometric proof of linear-code and linear-orthogonal-array duality.
- Nonexistence: Infinite graph families without uniformly weighted designs arise from Laplacian eigenvalue algebra and a construction involving almost irreducible characteristic polynomials.The concluding construction produces families with no uniformly weighted designs of any strength.
2. Weights of designs
The paper recasts uniformly weighted designs as a geometric condition on eigenconfigurations and connects minimal designs to facets of eigenpolytopes. This framework also yields subset-sum complexity and concrete examples with different uniform-weight behavior.
- Eigenconfigurations and eigenpolytopes: The t-th eigenconfiguration B_t consists of columns from eigenvectors corresponding to eigenspaces not averaged by a strength-t design, and its convex hull is the eigenpolytope P_t.The eigenconfiguration is formed from the remaining eigenvectors after separating the eigenspaces that the design must average.
- Existence criterion: A graph has a uniformly weighted design of strength t if and only if B_t is 2-valued under some linear functional.A 2-valued configuration is one on which a linear functional takes exactly two distinct values.
- Polyhedral characterization: Minimal uniformly weighted designs correspond to two parallel supporting hyperplanes of P_t, separating the eigenconfiguration points indexed outside and inside the design.This is the uniformly weighted analogue of the facet characterization for minimal positively weighted designs.
- Multiple weights: A design with ℓ distinct positive weights exists exactly when B_t lies in ℓ + 1 parallel affine hyperplanes encoding those weights.The hyperplanes have levels a_0, a_0 + δ_1, ..., a_0 + δ_ℓ.
- Examples: For C6 + K4, strengths 4 and 3 have uniformly weighted minimal designs meeting dimension bounds s_4 = 9 and s_3 = 8, respectively.At strength 4, the designs are the K4 and C6 vertex sets; at strength 3, all minimal designs are uniformly weighted.
- Computational perspective: Uniformly weighted designs are equivalent to nonempty zero-sum subsets of eigenvector columns, making strength-one existence equivalent to rational multidimensional subset sum.This establishes an algorithmic complexity connection for deciding whether such designs exist.
3. Polyhedral Geometry of 2-valued Configurations
The section develops polyhedral criteria for 2-valued eigenconfigurations, connecting their witness faces to uniformly weighted designs and their cardinalities. It applies these ideas to hypercubes, simplicial configurations, and examples with or without dimension-bound designs.
- 2-valued configurations: A 2-valued configuration has two extremal faces, called 2-witnesses, containing all configuration points.No configuration point may lie in the interior of its convex hull, although points may lie in the relative interiors of the two witness faces.
- Design cardinalities: A minimal uniformly weighted design corresponds to a facet of the eigenpolytope, while lower-dimensional witness faces can yield designs outside the dimension bound.The section introduces meeting the dimension bound as requiring a 2-witness face to contain at least dim(P) points.
- Hypercubes: For hypercube graphs, the last eigenspace supplies a 2-witness direction producing two designs with 2^(n−1) vertices, meeting the dimension bound when t ≥ n/2.The relevant eigenvectors are indexed by binary vectors and have eigenvalues 2|y|.
- 2-valued configurations: In dimensions at most 3, every 2-valued configuration has a 2-witness that is a facet, whereas this can fail in dimensions at least 4.The configuration P_d is 2-valued but has no 2-witness facet.
- Higher-dimensional examples: Projection preserves 2-valuedness, enabling a hypercube projection to a tetrahedron and a uniformly weighted design of size 2^(n−2) at strength t = floor(2n/3).The tetrahedron’s witness direction has one face containing one fourth and the other containing three fourths of the vertices.
- Design cardinalities: Centrally symmetric full-dimensional configurations whose points are all vertices have witness faces containing half the vertices, and sufficiently large strengths force a dimension-bound design when one exists.The latter conclusion applies when t ≤ floor(n/2) and a uniformly weighted design exists.
4. Graph Families with Uniformly Weighted Designs
The paper identifies graph families with uniformly weighted designs across strengths, including families where all minimal designs are uniform and families with more selective uniformity. Complete tripartite, threshold, and hypercube graphs illustrate these geometric and coding-theoretic patterns.
- 2-level Eigenpolytopes: Complete tripartite graphs K1,2,n have uniformly weighted minimal designs supported on each part, with sizes 1, 2, and n.Their relevant eigenpolytopes are 2-level, and all minimal designs are uniformly weighted.
- Threshold Graphs: Threshold-graph eigenpolytopes can be non-2-level while their eigenconfigurations remain 2-valued at every strength.The construction uses a shared basis of integral eigenvectors for connected threshold graphs.
- Threshold Graphs: Threshold graphs have a singleton uniformly weighted design at every strength, although some minimal positively weighted designs are not uniformly weighted.For strengths 1 ≤ t ≤ k − 2, interior points of certain simplex faces force uniformly weighted designs to include all or none of those points.
- Threshold Graphs: In the example T (1, 1, 2, 3, 1), the eigenconfiguration B2 is a tetrahedron with repeated vertices and points interior to a triangular face.The facet through b3, b4, and b8 takes values 3 and 27 on different point groups, hence three values overall and is not a 2-witness.
- Hypercube Graphs and Simplex Projections: Linear-code projections produce hypercube designs: a code of dimension d yields a strength-t design with 2^(n−d) points.The projection forms a (2^d − 1)-simplex and corresponds to the dual code.
- Hypercube Graphs and Simplex Projections: BCH-code duals give hypercube designs of size at most 2^(mt+1) = O(n^t), and expanded constructions meet the dimension bound at all strengths.The paper presents this as a geometric proof of the duality between linear codes and linear orthogonal arrays.
5. Graph Families without Uniformly Weighted Designs
The paper constructs infinite families of Laplacian irreducible graphs, and shows that such graphs have no nontrivial uniformly weighted designs at any strength. The construction uses Eisenstein’s criterion and repeated bridge attachments.
- Laplacian irreducible graphs have no nontrivial uniformly weighted designs at any strength.All nonzero Laplacian eigenvalues are conjugate, forcing any uniformly weighted design to average all eigenspaces and therefore use the entire vertex set.
- Whether most graphs are generically Laplacian irreducible remains open, so the construction does not settle the random-graph case.Experimental evidence supports a positive answer, but existing proofs are limited; the paper instead constructs explicit infinite families.
- Eisenstein’s criterion proves that a Laplacian Eisenstein characteristic polynomial makes the graph Laplacian irreducible.After dividing by x, all nonleading coefficients are divisible by 2 while the constant term is not divisible by 4.
- The construction builds infinite families by repeatedly bridging an anchor graph to copies of a repeat graph under four polynomial conditions.The conditions require Laplacian Eisenstein characteristic polynomials, an odd constant term for pH,v, and a mod-2 congruence between principal-minor polynomials.
- The bridge construction preserves the Laplacian Eisenstein property inductively across every graph in the family.The coefficient of x remains nonzero modulo 4, while each resulting characteristic polynomial remains monic and divisible by x.
- Monorail and houseboat graphs are infinite families without uniformly weighted designs at any strength.The monorail family uses a single-edge repeat graph, while the houseboat family arises from a different repeat graph satisfying the theorem’s conditions.