1 Introduction↩︎

Hypergraph partitioning is a fundamental combinatorial optimization problem that arises in a wide range of applications spanning engineering, scientific computing, machine learning, data analytics, and VLSI design. Classical hypergraph partitioning seeks to divide a hypergraph into balanced blocks while optimizing objectives such as cut size, communication volume, or load balance KarypisIrregular?, aykanat2008multi?, BUI1992153?, kernighan1970efficient?, fischer2009approximate?, Chekuri2018MinimumCA?, catalyurek2019profile?, li2018fiedler?. By employing hypergraphs – where hyperedges connect arbitrary subsets of vertices – such formulations can naturally capture higher-order dependencies that arise in complex systems.

schlag2023high? As a consequence, hypergraph partitioning has indeed been successful in tackling many challenges in a broad range of domains, partly because hypergraphic models provide a natural representation of multi-way interactions in various settings. Beyond high-performance scientific computing, and VLSI design MultiLevelVLSI?, 1676460?, devine2006parallel?, hypergraph partitioning formulations are also widely used in distributed databases, large-scale data analytics, social network analysis, and route planning karypis1999multilevel?, heuer2021multilevel?, catalyurek2023survey?, schlag2023high?, where hypergraph models facilitate scalable storage, computation, and communication. Very pertinent are also its applications in sparse matrix computations, where hypergraph partitioning captures communication requirements in operations such as sparse matrix–vector multiplication, enabling efficient distribution of data and computation across processors catalyurek1999hypergraph?, devine2006parallel?, buluc2016parallel?, ballard2016hypergraph?, DEVECI201569?, catalyurek:hal-00763563?.

In practice, hypergraph partitioning has been dominated by the multilevel paradigm, consisting of coarsening, initial partitioning, and refinement stages. This philosophy underlies influential systems such as hMETIS, PaToH, and KaHyPar MultiLevelVLSI?, schlag2023high?, heuer2021multilevel?. Modern developments include deterministic parallel algorithms such as BlasPart and Mt-KaHyPar, which target reproducibility and scalability on massive instances tong2025blaspart?, gottesburen2022deterministic?, while local-search heuristics, particularly the Fiduccia–Mattheyses (FM) algorithm, remain central to partition refinement through iterative improvement procedures fiduccia1988linear?, schlag2023high?. Similar ideas have also been adopted in distributed computing applications; for example, song2022hypergraph? proposed an online scheduling framework based on hypergraph partitioning and FM-inspired refinement, while ronzani2026hypergraph? studied GPU-based multilevel hypergraph partitioning under hard resource constraints, while the increasing scale of modern hypergraphs has motivated the development of numerous parallel partitioning frameworks 1372057?, Lars2021?, Kabiljo2017?, MalekiABP21?. A nice survey of recent advances can be found here catalyurek2023survey?.

1.0.0.1 Hypergraph edge partitioning

In this work, we study the specific problem of hypergraph edge partitioning, where the objective is to assign the hyperedges of a hypergraph to \(N\) groups while controlling the replication of vertices induced by this assignment. Unlike the more classical vertex-partitioning formulation, where vertices are distributed across blocks while minimizing cut-related objectives, edge partitioning allocates the hyperedges themselves and seeks to limit various vertex-replication costs.

Such edge-partitioning formulations arise naturally whenever hyperedges represent tasks, computations, transactions, communication patterns, or data dependencies that must be assigned across distributed resources. Such formulations have emerged in a variety of large-scale systems. In distributed graph analytics, assigning edges rather than vertices has been shown to significantly reduce communication bottlenecks and improve scalability on highly irregular graphs, motivating systems such as PowerGraph and subsequent edge-partitioning frameworks gonzalez2012powergraph?, Zhang2017GraphEdgePartitioning?, mayer20202pshighqualityedgepartitioning?, Bourse2014?. Similar ideas have been employed in large-scale graph-processing infrastructures operating at the trillion-edge scale, where edge partitioning provides a practical mechanism for balancing computation while controlling vertex replication and communication overhead TrillionEdges?, Dynamic?. Hypergraph edge partitioning also arises naturally in distributed storage systems, database sharding, parallel data analytics, and distributed task allocation, where hyperedges represent groups of data items or computational tasks that must be co-located while minimizing replication costs. From an algorithmic perspective, existing approaches include exact and optimization-based formulations SATPart?, mykhailenko2017simulated?, hybrid approaches Mayer2021Hybrid?, and balanced hyperedge-partitioning algorithms for large-scale data applications HEPart?. For example, one recent line of research has focused on scalable edge-partitioning frameworks for distributed graph analytics, where again the objective is to balance edge assignments while minimizing vertex replication and communication overhead. Representative examples include PowerGraph and subsequent scalable edge-partitioning systems, which offer additional evidence that assigning edges rather than vertices can substantially improve the processing of highly irregular networks and massive social graphs gonzalez2012powergraph?, Zhang2017GraphEdgePartitioning?, mayer20202pshighqualityedgepartitioning?, schlag2018scalable?. Another direction has pursued partitioners based on projective planes ProjectivePlane? or highly scalable hash-based partitioners, while a substantial body of work has focused on streaming graph edge partitioning, where edges arrive sequentially and must be assigned online while always balancing load and limiting vertex replication. Representative examples can be found here Petroni2015HDRF?, Mayer2018ADWISE?, Hoang2019CUSP?, together with other related replication-aware streaming partitioners Sajjad2016Boosting?, which trade structural awareness for speed and scalability, making them attractive for dynamic and large-scale settings PartitioningTrillionEdges?, chhabra_et_alV1?, Streaming?.

1.0.0.2 Formalization

To formalize the hypergraph edge partitioning problem, we first consider a hypergraph \(\mathcal{H}(\mathcal{V}, \mathbf{X})\), where \(\mathcal{V}\) denotes the vertex set, and \(\mathbf{X} \subseteq \binom{\mathcal{V}}{d}\) denotes the hyperedge set. An edge partitioning scheme, by assigning each hyperedge to one of \(N\) groups, results in a partition \(\{\mathbf{\Phi}_b\}_{b=1}^N\) of \(\mathbf{X}\). Labeling \(\mathcal{V}\) by \([n] = \{1,2,\dots,n\}\), each group \(b\) then ‘sees’ a vertex footprint \[\label{eq:32alpha95phi} \alpha(\mathbf{\Phi}_b)\triangleq\{i \in [n] \mid \exists \mathbf{e} \in \mathbf{\Phi}_b, \quad i \in \mathbf{e} \}\tag{1}\] which brings to the fore the maximum vertex footprint (MVF)³ defined as \[\label{eq:pi95X32} \pi_\mathbf{X} \triangleq \max_{b \in [N]} |\alpha(\mathbf{\Phi}_b)|\tag{2}\] which measures the size of the largest induced vertex set \(\alpha(\mathbf{\Phi}_b)\) across all groups. Additionally, the load-balance constraint is captured by the parameter \(\delta_\mathbf{X}\), defined, for example, as the ratio between the maximum group size and the ideal group size.

Despite the aforementioned algorithmic advances, the theoretical understanding of hypergraph edge partitioning – whether this is for the above footprint metric, or related metrics – remains incomplete. While graph partitioning \((d=2)\) enjoys some performance guarantees Dynamic?, TrillionEdges?, Zhang2017GraphEdgePartitioning?, comparatively little is known about the fundamental limits of hypergraph edge partitioning for general hypergraphs \((d\ge 3)\). The present work provides explicit characterizations of the achievable and unavoidable footprint in a broad class of probabilistic hypergraph models.

1.0.0.3 The IC-Design

The recent work in IC?, maheri2026order? proposed a combinatorial construction, termed the Interweaved-Cliques (IC) design, that leverages carefully structured interweaving sets to allow for hypergraph edge partitioning. Clique-based set structures also arise in several problems in coding and information theory, including coded caching and coded distributed computing MaN?, MKR?, PNR2?, Li2018CodedMapReduce?, BrEl2?, BrEl?. In contrast, the IC design leverages such structures for hypergraph edge partitioning, with the objective of minimizing the vertex footprint. Focusing on the setting of \(d\)-uniform hypergraphs, the work was able to show the order-optimality of the design, doing so only for the extreme case of very dense and homogeneous hypergraphs – where \(\mathbf{X}\) is drawn uniformly and densely from the different neighborhoods/subsets of the complete \(d\)-uniform hypergraph \(\mathbf{A}_{n,d}\). From a probabilistic standpoint, the model in IC? can be interpreted as capturing a high-entropy, dense regime, corresponding to a worst-case instance of an i.i.d. thinning model where \(\mathbf{X}\) samples uniformly and densely from \(\mathbf{A}_{n,d}\). As such, this prior approach does not account for heterogeneity, structural dependencies, or sparsity in the hyperedge set.

1.0.0.4 Going beyond maximal entropy hypergraphs – capturing heterogeneity, structural dependencies, and sparsity

In contrast, the present work considers a substantially more general model in which each potential hyperedge \(\mathbf{e} \in \mathbf{A}_{n,d}\) is included independently with its own prescribed probability \(\varphi_{\mathbf{e}}\), allowing for sparsity, broad heterogeneity and differently-structured neighborhoods in \(\mathbf{X}\). This generalization enables us to optimally capture various structure regimes and a very broad sparsity range. In particular, while prior results IC? were confined to dense instances where \(|\mathbf{X}|\) is within a constant factor from the size \(|\mathbf{A}_{n,d}|\) of the complete hypergraph \(\mathbf{A}_{n,d}\), we here establish tight fundamental limits under the much broader condition \(|\mathbf{X}| \gtrsim n N \log N\), thereby extending optimality down to very sparse \(\mathbf{X}\). For example, under a large-\(n\) interpretation, our presented result here extends down to hypergraphs whose edge set size can be of minimal order, as low as linear in \(n\).

We will treat both the \(d\)-uniform case and the general case of edge sets \[\mathbf{X}\subseteq \mathbf{A}_{n,1}\cup\mathbf{A}_{n,2}\cup\cdots\cup\mathbf{A}_{n,d}\] which may contain singleton hyperedges, pairwise hyperedges, and, more generally, hyperedges of size up to \(d\).

1.0.0.5 Positioning this work

Our work is related to a growing body of theory-oriented research on hypergraph optimization and partitioning, including approximation algorithms for hypergraph partitioning fischer2009approximate?, structural studies of hypergraph cuts and sparsification Chekuri2018MinimumCA?, hypergraph-based formulations for combinatorial optimization objectives catalyurek2019profile?, and spectral approaches to hypergraph partitioning based on Laplacian tensors li2018fiedler?. Complementary to many of the existing works in hypergraph partitioning, our emphasis is less on designing of improved partitioning algorithms, and more on identifying the fundamental limits of hypergraph edge partitioning under broad probabilistic hypergraph models. Specifically, we derive converse bounds on the minimum achievable maximum vertex footprint and show that an explicit, universal and deterministic construction achieves these limits to within small constant factors. maheri2025constructing?

2 Problem Definition and Setup↩︎

We begin with the hypergraph model.

2.1 Hypergraph Model↩︎

For given positive integers (\(n\), \(d\), \(N\)), we consider a hypergraph \(\mathcal{H}(\mathcal{V}, \mathbf{X})\), where \(\mathcal{V}=[n] \triangleq \{1, 2, \ldots, n\}\) is the vertex set, and where the hyperedge set \(\mathbf{X}\) is a subset of the ambient space \(\mathbf{A}\). In the \(d\)-uniform case, the ambient space takes the form \(\mathbf{A}=\mathbf{A}_{n,d}\), while in the general case, it takes the form of \(\mathbf{A}=\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\); the collection of all \(k\)-element subsets of \([n]\), from \(k=1\) to \(k=d\).

An edge partitioning of \(\mathbf{X}\) into \(N\) groups is a map from \(\mathbf{X}\) to a collection \(\{\mathbf{\Phi}_1, \mathbf{\Phi}_2, \ldots, \mathbf{\Phi}_N\}\) consisting of \(N\) groups that form a partition of \(\mathbf{X}\), where each hyperedge of \(\mathbf{X}\) is assigned to exactly one group, the groups are pairwise disjoint, and their union equals \(\mathbf{X}\). We denote by \(\boldsymbol{\mathcal{S}}_{\mathbf{X}}\) a specific edge partitioning scheme that produces such a partition.

For each group \(b \in [N]\), \(\alpha(\mathbf{\Phi}_b)\) is the set of distinct vertices appearing in at least one edge of \(\mathbf{\Phi}_b\), i.e., \[\alpha(\mathbf{\Phi}_b)=\{i \in [n] \mid \exists \mathbf{e} \in \mathbf{\Phi}_b, \quad i \in \mathbf{e} \}.\] This represents the vertex footprint of group \(b\).

2.2 Metrics and Objective↩︎

We evaluate partitioning schemes using two primary metrics that capture different aspects. First we have the aforementioned maximum vertex footprint (MVF), \[\pi_{\mathbf{X}} = \max_{b \in [N]} |\alpha(\mathbf{\Phi}_b)|\] which represents the maximum number of vertices that appear (across the edges in) a group \(\mathbf{\Phi}_b\), maximized across all groups \(b \in [N]\). Then we have the load balance factor, which is defined as \[\label{eq:32delta-def} \delta_{\mathbf{X}} \triangleq \frac{\max_{b \in [N]} |\mathbf{\Phi}_b|}{\lceil|\mathbf{X}|/N\rceil}\tag{3}\] and which will here measure the imbalance between the maximum group size and the ideal group size. Perfect balance corresponds to \(\delta_{\mathbf{X}} = 1\), while larger values indicate increasing imbalance. Our primary objective is to characterize the minimum achievable maximum vertex footprint over all partitioning schemes.

We present below the statistical model, which comes into the picture only for the converse.

2.3 Statistical Model↩︎

We consider a general probabilistic model for independently generating hyperedges from the ambient space \(\mathbf{A}\). Let us denote the corresponding probabilistic generating vector by \[\boldsymbol{\varphi}\triangleq (\varphi_{\mathbf{e}})_{\mathbf{e}\in \mathbf{A}}\] where each hyperedge \(\mathbf{e}\) may appear with its own probability \(\varphi_{\mathbf{e}}\) that can vary arbitrarily, but which, first for the \(d\)-uniform case, must satisfy

\[\label{eq:phi1} \varphi_{\mathbf{e}}\ge \varphi_{\mathrm{min}} = \varphi_{\mathrm{min}}^{u} \triangleq \min\left\{\frac{15nN(\log N+\frac{4}{5}\frac{\log (2n^z)}{n})}{{n \choose d}},1 \right\}\tag{4}\] while for the non-uniform case, it must satisfy \[\label{eq:phi2} \varphi_{\mathbf{e}}\ge \varphi_{\mathrm{min}}= \varphi_{\mathrm{min}}^{n} \triangleq \min\left\{\frac{13nN (\log N+\frac{12}{13}\frac{\log(2n^z)}{n})}{{\sum_{k=1}^{d}\binom{n}{k}}},1\right\}\tag{5}\] to mainly account for the larger size of the non-uniform ambient space. The above parameter \(z\geq 1\) calibrates, as we will see, the probability that the derived performance guarantees apply. To facilitate a unified presentation of the results, we are using \(\varphi_{\min}\) to mean \(\varphi_{\min}^{u}\) in the \(d\)-uniform setting and to mean \(\varphi_{\min}^{n}\) in the non-uniform setting.

2.3.0.1 Model generality

The above formulation does not impose any specific structural form on the probabilities \(\varphi_{\mathbf{e}}\). Instead, the vector \(\boldsymbol{\varphi}\) may represent an arbitrary statistical mechanism that satisfies the edge-independence assumption, while still inducing a broad range of structures across the observed hypergraph. Consequently, many commonly studied hypergraph models are encompassed by our framework, either directly or conditionally on the realization of their latent variables⁴. Representative examples include:

• Uniform iid model: \(\varphi_{\mathbf{e}}\) is the same for all \(\mathbf{e}\).

• Hypergraph stochastic block model (HSBM): \(\varphi_{\mathbf{e}}\) depends on the community labels of the vertices in \(\mathbf{e}\), with probabilities determined by block-interaction parameters.

• Degree-corrected or mixed-membership models: \(\varphi_{\mathbf{e}}\) depends on vertex-specific parameters or community-membership mixtures.

• Latent-space/geometric or kernel models: conditional on the latent variables associated with the vertices, \(\varphi_{\mathbf{e}}\) is determined by a kernel or similarity function of those latent variables.

2.4 Paper Organization↩︎

After Section 2 introduced the hypergraph edge-partitioning problem, the performance metrics of interest, and the probabilistic hypergraph model considered throughout the paper, Section 3 will present the main theoretical contributions. In this same section, we first establish a converse bound on the minimum achievable maximum vertex footprint through Lemma 1. We then present Theorem 1, which characterizes the optimality region of hypergraph edge partitioning under the considered independent edge sampling model. The section further includes Corollary 1, which specializes the result to hypergraphs of a given cardinality, as well as Corollaries 2 and 3 which strengthen the main characterization by deriving tighter converse bounds and tighter achievable gaps to optimality. Furthermore, Proposition 1 establishes that the proposed construction simultaneously achieves a near-optimal load-balance factor with high probability. Then, Section 3.3 provides examples, interpretations, and additional discussion that help illustrate the implications of the theoretical results and the resulting gaps to optimality.

Subsequently, Section 4 presents the interweaved-cliques design. We first construct partitions of the complete ambient spaces \(\mathbf{A}_{n,d}\) and \(\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\), then analyze their footprint properties, extend the construction to the desired number of groups, and finally refine the resulting partition to accommodate an arbitrary realized hyperedge set \(\mathbf{X}\).

Finally, Section 5 concludes the paper. The proofs of the main results are deferred to Appendix 6, while additional technical arguments and auxiliary results are provided in Appendix 7.

We now proceed to present the main results.

3 Main Results↩︎

We here derive the fundamental limits of our edge partitioning problem. We present the results for both the case of \(d\)-uniform hypergraphs and the general case of non-uniform hypergraphs together; however, the proofs for these cases are developed separately when necessary. Please recall that the ambient space \(\mathbf{A}\) will correspond to \(\mathbf{A}_{n,d}\) and \(\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\) in the cases of \(d\)-uniform and non-uniform hypergraphs, respectively. We now present lower and upper bounds on the optimal maximum vertex footprint \(\pi^\star_{\mathbf{X}}\), \[\label{eq:32opt32regime} \pi^\star_{\mathbf{X}} \triangleq\min_{\boldsymbol{\mathcal{S}}_{\mathbf{X}}} \left( \max_{b \in [N]} |\alpha(\mathbf{\Phi}_b)| \right)\tag{6}\] where the optimal (minimum) is taken over all⁵ \(N\)-edge partitioning schemes \(\boldsymbol{\mathcal{S}}_{\mathbf{X}}\).

For the following converse, \(\mathbf{X}\) is viewed as a realization of an independent random thinning of \(\mathbf{A}\), where each edge \(\mathbf{e}\in \mathbf{A}\) is retained independently with its own probability \(\varphi_{\mathbf{e}}\), satisfying 4 , 5 .

Let us now proceed with the converse on the optimal maximum vertex footprint, \(\pi_{\mathbf{X}}^{\star}\).

Let us now view our main theorem, under the same model where each hyperedge \(\mathbf{e} \in \mathbf{A}\) is included independently with probability \(\varphi_{\mathbf{e}}\) (cf. 4 , 5 ), and where \(\mathbf{X}\) denotes the resulting hyperedge set. We remind the reader that this model captures hypergraphs with various structural properties, and effectively entails cardinalities \(|\mathbf{X}| \gtrsim n N \log N\) which can be as low as linear in \(n\). Finally, we note that any constructive result entails an assumption of \(d\leq n/2\). For the trivial case of \(d>n/2\), the fundamental limits are clearly known, to within a factor of \(2\) automatically, since naturally, \(\pi \in [d,n] \subseteq (\frac{n}{2},n]\).

In the following, we will denote the derived lower bound as \(\pi_{\mathrm{LB}}\), where \(\pi_{\mathrm{LB}} \triangleq \frac{1}{2}\frac{n}{N^{1/d}}\) and \(\pi_{\mathrm{LB}} \triangleq \frac{1}{2\sqrt{2}}\frac{n}{N^{1/d}}\) for the uniform and non-uniform cases respectively.

The following corollary centers around the cardinality of the hypergraph \(\mathbf{X}\), where again each hyperedge \(\mathbf{e}\in\mathbf{A}\) is included independently with probability \(\varphi_{\mathbf{e}}\geq \varphi_{\min}\). The corollary reflects a scenario where one is given a hypergraph \(\mathbf{X}\), knows its size, and wonders what is the probability (under the model here) that an algorithm can exist that can yield a lower footprint than \(\pi_{\mathrm{LB}}\).

3.1 Tighter Bounds↩︎

The above results reveal what one could call an achievable partitioning gain \(n/\pi_{\mathbf{X}}\), which is shown to be very close to \(N^{1/d}\) and which is, with high probability, within a constant factor of at most \(8e \approx 22\) from the optimal (\(8\sqrt{2}e\approx 31\) for non-uniform hypergraphs). This constant gap is, in fact, partly due to basic approximations, such as the Stirling approximation, used to obtain concise closed-form expressions. The following two corollaries tighten the converse and achievability results, revealing even tighter gaps to optimal. We begin with a tighter converse.

We now identify tighter gaps to optimal.

3.2 Near-Optimal Load Balance Factor↩︎

We proceed with the following lemma, which shows that the load balance factor \(\delta_{\mathbf{X}}\), offered by the IC design, remains small with high probability. The lemma will hold under an independent thinning model where now the probability of edge inclusion is identical across all edges, i.e., where \(\varphi_{\mathbf{e}}=\varphi\) for every edge \(\mathbf{e}\). To facilitate a unified presentation of the result, we will use \(\varphi_{\min,\delta}\), where \(\varphi_{\min,\delta}\) is interpreted as \(\varphi_{\min,\delta}^{u} = \min\left\{ \frac{54N\log(4Nn^z)}{\binom{n}{d} - (2^{d+1})N},1\right\}\approx \frac{N\log (4Nn^z)}{\binom{n}{d}}\) (cf. 91 ) for \(d\)-uniform hypergraphs, and as \(\varphi_{\min,\delta}^{n} = \min\left\{\frac{54N\log(4Nn^z)}{\sum_{k=1}^{d}\binom{n}{k} - (2^{2d+1})N},1\right\} \approx \frac{N\log (4Nn^z)}{\sum_{k=1}^{d}\binom{n}{k}}\) (cf. 116 ) for non-uniform hypergraphs.

3.3 Examples and Remarks↩︎

The following remarks and examples aim to help the reader better understand the above results. The examples are in reference to the \(d\)-uniform setting.

4 Achievable Scheme: Interweaved Cliques Design↩︎

We now describe the Interweaved-Cliques design; a deterministic edge-partitioning scheme that first constructs a partition of a complete hyperedge universe \(\mathbf{A}\), and then refines this partition to the observed edge set \(\mathbf{X}\). The design, which will be presented for any \({n,d\leq \frac{n}{2}},N\leq \binom{\lfloor\sqrt{\frac{nd}{2}}\rfloor}{d}\) ⁶, will in the end produce \(N\) groups \(\mathbf{\Phi}_1,\dots,\mathbf{\Phi}_N\), such that \[\pi_{\mathbf{X}} =\max_{b \in [N]} |\alpha(\mathbf{\Phi}_b)|, \quad \text{and} \quad \delta_{\mathbf{X}} =\frac{\max_{b \in [N]} |\mathbf{\Phi}_b|}{\lceil|\mathbf{X}|/N\rceil}\] are minimized.

The construction will proceed in steps. In particular, in Section 4.1, we will present an \(N'\)-partition of \(\mathbf{A}_{n,d}\) (partition the ambient space into \(N'\) groups), for some carefully chosen \(N' \leq N\), while in Section 4.2 this \(N'\)-partition will be extended to the non-uniform ambient space \(\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\). Then in Section 4.3, we will provide, in Lemma 2, an analysis of important parameters of the above \(N'\)-partitions. Subsequently, in Section 4.4, we will extend the partitions of \(\mathbf{A}_{n,d}\) and \(\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\), from \(N'\) groups to the desired \(N\) groups, and we will present Lemma 3 that offers guarantees on \(\pi\) and \(\delta\) for these \(N\)-partitions, again still of the ambient space \(\mathbf{A}_{n,d}\) and \(\bigcup_{k=1}^{d} \mathbf{A}_{n,k}\). Finally, in Section 4.5, we will adapt the above \(N\)-partitions, to account for the actual \(\mathbf{X}\). We note here that the construction, for the uniform case, can be seen as a calibrated version of the original design in IC?, and parts are reproduced here; partly for completeness, and partly to facilitate the presentation of the non-uniform case.

4.1 \(N'\)-partition of \(\mathbf{A}_{n,d}\)↩︎

We first construct a partition \(\widetilde{\mathbb{P}}\) of the complete \(d\)-uniform hyperedge set \(\mathbf{A}_{n,d}\). The construction for this part, follows closely the steps in IC?, and is based on grouping the vertices into \(f\) families of vertices (to be described later on), where \[\label{eq:32f32def} f\triangleq\max\left\{r:\binom{r}{d}\leq N\right\}.\tag{7}\]

Each family contains \(s\) vertices. Let \(g = n-fs\). If \(f\mid n\), then \[\label{eq:32s32selection} s=\frac{n}{f}, \qquad g=0, \qquad \mathcal{E}=\emptyset\tag{8}\] else \[\label{eq:32s32selection2} s=\left\lfloor\frac{n}{f+d}\right\rfloor+1, \qquad g=n-fs\tag{9}\] where in the above, we consider a so-called ‘excluded set’ of \(g\) vertices⁷ \[\label{eq:32excluded} \mathcal{E}\triangleq [n]\setminus[n-g] = \{n-g+1,\ldots,n\}.\tag{10}\] We now partition the \(n-g=fs\) non-excluded vertices \([n-g]\), into \(f\) disjoint families \[\label{eq:Fis1} \mathcal{F}_i=\{(i-1)s+1,\ldots,is\}, \qquad i\in[f]\tag{11}\] leaving \(g\) vertices out, for now. At this point, we will, initially, produce \(N'\triangleq{f \choose d}\) intermediate edge groups \(\widetilde{\mathbf{\Phi}}_\sigma, \sigma\in\mathbf{\Sigma}\), where \[\label{eq:32N39intermediate} \qquad \mathbf{\Sigma}\triangleq \{\sigma\subseteq[f]:|\sigma|=d\}.\tag{12}\] In words, each \(\widetilde{\mathbf{\Phi}}_\sigma\) is labeled by a \(d\)-tuple from \([f]\). We will ‘allocate’ each group \(\widetilde{\mathbf{\Phi}}_\sigma\), with a vertex footprint \(\alpha(\widetilde{\mathbf{\Phi}}_\sigma)\) of the form \[\begin{align} \alpha(\widetilde{\mathbf{\Phi}}_\sigma) = \bigcup_{i\in\sigma}\mathcal{F}_i \end{align}\] involving the vertices that belong to the families indexed by \(\sigma\), and this will thus entail \[\label{eq:alphaPhiSigma} |\alpha(\widetilde{\mathbf{\Phi}}_\sigma)|=\sum_{i\in\sigma}|\mathcal{F}_i|=s\cdot d .\tag{13}\] We will see soon how the hyperedges are assigned to each \(\widetilde{\mathbf{\Phi}}_\sigma\).

At this point, for an edge \(\mathbf{e}\in \mathbf{A}_{n,d}\), we define its support family by \[\mathcal{B}(\mathbf{e})\triangleq \{j\in[f]:\mathbf{e}\cap \mathcal{F}_j\neq\emptyset\}\] and we let \(\beta_{\mathbf{e}} \triangleq|\mathcal{B}(\mathbf{e})|\), where the above \(\mathcal{B}(\mathbf{e})\) is simply the families of vertices that an edge \(\mathbf{e}\) intersects with. We first separate the edges according to whether they have full family support or not, thus creating \[\mathbf{A}_{\mathrm{full}}\triangleq \{\mathbf{e}\in \mathbf{A}_{n,d}:\beta_{\mathbf{e}}=d\}\] which is the set of edges that each intersects exactly one vertex from each of \(d\) distinct families. Then, each edge in \(\mathbf{A}_{\mathrm{full}}\), is assigned uniquely to the group indexed by its support \[\label{eq:32phi-full} \widetilde{\mathbf{\Phi}}^{(\mathrm{full})}_\sigma \triangleq \{\mathbf{e}\in \mathbf{A}_{\mathrm{full}}:\mathcal{B}(\mathbf{e})=\sigma\}, \qquad \sigma\in\binom{[f]}{d}.\tag{14}\] We remind ourselves that this partitions the hyperedges of \(\mathbf{A}_{\mathrm{full}}\), i.e., those edges in \(\mathbf{A}_{n,d}\) that have full support, and which involve no excluded vertices (no vertices from \(\mathcal{E}\)). This is the core of the design, and it will effectively define most or all the vertices associated to each group. We now proceed to distribute the remaining edges, i.e., those in \[\mathbf{A}_{\mathrm{rem}}\triangleq \mathbf{A}_{n,d}\setminus \mathbf{A}_{\mathrm{full}}\] into the \(N'={ f \choose d}\) intermediate groups. Please note that now we are allowing hyperedges that may also involve vertices from \(\mathcal{E}\).

Any edge \(\mathbf{t} \in \mathbf{A}_{\mathrm{rem}}\) will have an arbitrary number \(m_{\mathbf{t}}=|\mathbf{t} \cap \mathcal{E}|\) of vertices from the set \(\mathcal{E}\), and it will thus have \(d-m_{\mathbf{t}} = |\mathbf{t} \cap [n-g]|\) vertices from the \([n] \setminus\mathcal{E}\). It is easy to see that \[\label{eq:32valid32range32m} m_{\mathbf{t}}\in [0, \min\{d,g\}]\tag{15}\] and thus that \(d-m_{\mathbf{t}} \in [\max\{d-g,0\},d]\). We will henceforth, whenever there is no ambiguity, revert to the simpler notation \(m\) instead of \(m_{\mathbf{t}}\). We continue, and for every \(m\in [0, \min\{d,g\}]\), we define the set \[\label{eq:R95m44beta} \mathbf{R}_{m,\beta} \triangleq \left\{ \mathbf{t} \in \mathbf{A}_{\mathrm{rem}} \;\middle|\; |\mathcal{B}(\mathbf{t})| = \beta ,\;|\mathbf{t} \cap \mathcal{E}|=m \right\}\tag{16}\] which describes the edges \(\mathbf{t}\) that intersect exactly \(\beta\) families and also contain \(m\) excluded vertices from \(\mathcal{E}\). Notice that \(\beta\) can take values in the range \(\big[\lceil\frac{d-m}{s}\rceil, \min\{d-1,d-m\}\big]\) ⁸. If \(m=d\leq g\), then \(\beta =0\), which means that all the entries of \(\mathbf{t}\) are from \(\mathcal{E}\). Let us now partition \(\mathbf{A}_{\mathrm{rem}}\) as follows \[\mathbf{A}_{\mathrm{rem}}=\bigcup_{m=0}^{\min\{d, g\}}\bigcup_{\beta=\lceil\frac{d-m}{s}\rceil}^{\min\{d-1,d-m\}} \mathbf{R}_{m,\beta}.\] For each \(\mathcal{I}\in\binom{[f]}{\beta}\), let us first define \[\mathbf{R}_{\beta,\mathcal{I}} \triangleq \big\{\mathbf{t}\in\mathbf{A}_{\mathrm{rem}}\;\mid \mathcal{B}(\mathbf{t})=\mathcal{I},\; \mathbf{t}\in\bigcup_{m=0}^{\min\{d-\beta,g\}}\mathbf{R}_{m,\beta}\big\}\] to be the set of all \(d\)-tuples \(\mathbf{t} \in \mathbf{A}_{\mathrm{rem}}\) that intersect exactly all families in \(\mathcal{I}\), where in the above, \(\mathcal{B}(\mathbf{t})\) denotes the set of families that \(\mathbf{t}\) intersects. Let us now also define \(\mathbf{R}_{\beta}\triangleq\bigcup_{\mathcal{I}\in\binom{[f]}{\beta}}\mathbf{R}_{\beta,\mathcal{I}} \subset \mathbf{A}_{\mathrm{rem}}\) to be the set of all edges in \(\mathbf{A}_{\mathrm{rem}}\) that meet exactly \(\beta\) families. Furthermore, directly by applying the established ranges of parameters \(m\) (cf. 15 ), we can conclude that the range of \(\beta\) is \(\beta \in [\beta_{\mathrm{min}}, \beta_{\mathrm{max}}]\), where \(\beta_{\min} \;\triangleq\; \lceil \frac{d-\min\{d,g\}}{s} \rceil \;=\;\lceil \frac{\max\{0,d-g\}}{s} \rceil\) and \(\beta_{\max} \;\triangleq\; d-1.\) Our next step involves going through this range of \(\beta\). For each \(\beta \in [\beta_{\mathrm{min}}, \beta_{\mathrm{max}}]\), we partition each time the set \(\mathbf{R}_{\beta}\) into \(N'={f \choose d}\) groups. This partitioning is described in detail as follows.

For every group \(\sigma \in {[f] \choose d}\), we proceed to describe \(\widetilde{\mathbf{\Phi}}^{\mathrm{(rem)}}_{\sigma}\), which will be the set of all \(d\)-tuples from \(\mathbf{A}_{\mathrm{rem}}\) that will be allotted to the intermediate group labeled by \(\sigma\). For each \(\beta \in [\beta_{\mathrm{min}}, \beta_{\mathrm{max}}]\), the group \(\sigma\) has exactly \(\binom{d}{\beta}\) distinct subsets \(\mathcal{I}\in {[f] \choose \beta}\) of cardinality \(|\mathcal{I}|=\beta\). For each such \(\mathcal{I}\), let us consider the set \(\mathbf{R}_{\beta,\mathcal{I}}\) to be the set of all \(t_{\beta}\) distinct \(d\)-tuples from \(\mathbf{R}_{\beta}\) which intersect with \(\mathcal{I}\). For a \(d\)-tuple \(\mathbf{e}\), we say that \(\mathbf{e}\) is eligible for assignment to a group \(\widetilde{\mathbf{\Phi}}_\sigma\), if \(\mathcal{B}(\mathbf{e})\subset \sigma\), recalling also that for each \(\mathbf{e}\in \mathbf{R}_{\beta}\), there is one \(\mathcal{I} \in {[f] \choose \beta}\) such that \(\mathcal{I}= \mathcal{B}(\mathbf{e})\). Let us define the set of eligible groups for each \(\mathcal{I} \in {[f] \choose \beta}\), with cardinality \(\beta\), as \[\label{eq:32g95beta44I} \mathcal{G}_{\beta, \mathcal{I}}\triangleq \{\sigma \in {[f] \choose d}| \;\mathcal{I}\subseteq \sigma\}\tag{17}\] and let us also note that the number, denoted here as \(m_\beta\), of eligible groups, takes the form \[\label{eq:32m95beta} m_\beta \;\triangleq\; |\mathcal{G}_{\beta, \mathcal{I}}|=\binom{f-\beta}{d-\beta}.\tag{18}\] Now recall that \(t_\beta=|\mathbf{R}_{\beta, \mathcal{I}}|\), and let us introduce the notation \[\label{eq:32q95beta} q_\beta \;\triangleq\; \Big\lfloor\frac{t_\beta}{m_\beta}\Big\rfloor\tag{19}\] and \[\label{eq:32r95beta} r_\beta \;\triangleq\; t_\beta- q_\beta m_\beta, \qquad 0\le r_\beta < m_\beta.\tag{20}\] We now consider \(\mathbf{R}_{\beta,\mathcal{I}}\) in lexicographic order and denote the ordered list by \[\mathbf{R}^{\mathrm{lex}}_{\beta,\mathcal{I}} \;\triangleq\; \big( \mathbf{r}_{\beta,\mathcal{I}}^{(1)}, \mathbf{r}_{\beta,\mathcal{I}}^{(2)}, \dots, \mathbf{r}_{\beta,\mathcal{I}}^{(t_\beta)}\big)\] where \(\mathbf{r}_{\beta,\mathcal{I}}^{(\ell)}\) describes the \(\ell\)-th \(d\)-tuple in this lexicographic ordering. Subsequently, let us fix the lexicographic ordering of the \(m_\beta\) groups in \(\mathcal{G}_{\beta,\mathcal{I}}\), and let us denote this with \[\mathcal{G}_{\beta,\mathcal{I}}^{\mathrm{lex}} \;=\; \big(\sigma_1,\sigma_2,\dots,\sigma_{m_\beta}\big).\] We now partition \(\mathbf{R}^{\mathrm{lex}}_{\beta,\mathcal{I}}\) into the \(m_\beta\) groups \(\sigma_1,\dots,\sigma_{m_\beta}\). Since \(r_\beta=\lfloor \frac{t_\beta}{m_\beta}\rfloor\), each group receives either \(q_\beta\) or \(q_\beta+1\) \(d\)-tuples, which will mean that, in particular, \(r_\beta\) groups receive \(q_\beta+1\) \(d\)-tuples and the remaining \(m_\beta-r_\beta\) groups receive \(q_\beta\) \(d\)-tuples. Let us now define the index of \(\sigma\) (given a specific \(\mathcal{I} \subset \sigma\)) by \[J_{\beta,\mathcal{I}}(\sigma) \;\triangleq\; \{ j \;: \;\sigma=\sigma_j\text{ for some }j\in [m_\beta], \sigma_j \in \mathcal{G}_{\beta,\mathcal{I}}^{\mathrm{lex}} \}.\]

For \(\mathcal{I} \subset \sigma\) with \(J_{\beta,\mathcal{I}}(\sigma)=j\in\{1,\dots,m_\beta\}\), we now define the starting and ending indices of the block allocated to \(\sigma\), by \[\begin{align} s_{j,\beta,\mathcal{I}} &\;=\; (j-1)q_\beta+ \min(j-1,r_\beta) + 1,\tag{21}\\[4pt] e_{j,\beta,\mathcal{I}} &\;=\; j q_\beta + \min(j,r_\beta)\tag{22} \end{align}\] which gives us the final set \[\label{eq:allocated-set44C} \quad \mathbf{R}_{\beta,\mathcal{I},\sigma} \;=\; \big\{\, \mathbf{r}_{\beta,\mathcal{I}}^{(\ell)} \;:\; \ell = s_{j,\beta,\mathcal{I}},\; s_{j,\beta,\mathcal{I}}+1,\; \dots,\; e_{j,\beta,\mathcal{I}} \,\big\} \quad\tag{23}\] of allocated edges to intermediate group \(\sigma\), for this \(\mathcal{I}\). Now we go over all \(\mathcal{I}\) and \(\beta\), to combine the disjoint sets \(\mathbf{R}_{\beta, \mathcal{I}, \sigma}\), to get \[\label{eq:32phi95rem} \widetilde{\mathbf{\Phi}}_{\sigma}^{\mathrm{(rem)}}=\bigcup_{\beta=\beta_{\mathrm{min}}}^{\beta_{\mathrm{max}}}\bigcup_{\mathcal{I}\subset \sigma}\mathbf{R}_{\beta, \mathcal{I}, \sigma}.\tag{24}\]

Finally, for every \(\sigma \in {[f]\choose d}\), we combine the disjoint sets \(\widetilde{\mathbf{\Phi}}_{\sigma}^{(\mathrm{full})}\) in 14 and \(\widetilde{\mathbf{\Phi}}_{\sigma}^{\mathrm{(rem)}}\) in 24 , to get the entire set of hyperedges \[\label{eq:SubfunctionCase1} \widetilde{\mathbf{\Phi}}_{\sigma}=\widetilde{\mathbf{\Phi}}_{\sigma}^{(\mathrm{full})}\cup \widetilde{\mathbf{\Phi}}_{\sigma}^{\mathrm{(rem)}}\tag{25}\] allocated to group \(\sigma\). This gives us the partition \[\label{eq:32full32partition} \mathbf{A}_{n,d}= \bigcup\nolimits_{\sigma \in {[f] \choose d}}\widetilde{\mathbf{\Phi}}_{\sigma}\tag{26}\] of \(\mathbf{A}_{n,d}\) into \(N'={f \choose d}\) groups.

4.2 \(N'\)-partition of \(\bigcup_{k=1}^{d} \mathbf{A}_{n,k}\)↩︎

We now extend the above, to the case of \(\mathbf{A} = \bigcup_{k=1}^{d} \mathbf{A}_{n,k}\).

The same value of \(f\) in 7 is used, so that \(N'=\binom{f}{d}\). As before, if \(f\mid n\), we set \(s=n/f\); otherwise, we set \(s=\left\lfloor\frac{n}{f+d}\right\rfloor+1,\) and define again the set \(\mathcal{E}\) of (temporarily) excluded vertices as in 10 . In either case, each intermediate group is still indexed by some \(\sigma\in\binom{[f]}{d}\).

For \(k=d\), we follow the steps in Section 4.1 and partition \(\mathbf{A}_{n,d}\) into \(N'\) groups as follows \[\label{eq:32k61d} \mathbf{A}_{n,d}=\bigcup_{\sigma \in {[f]\choose d}}\widetilde{\mathbf{\Phi}}_{\sigma}^{d}.\tag{27}\] For the rest \(k\in[1,d-1]\), we will eventually partition \(\mathbf{A}_{n,k}\) as follows \[\label{eq:32An44k} \mathbf{A}_{n,k} = \bigcup_{\sigma\in\binom{[f]}{d}} \widetilde{\mathbf{\Phi}}^k_\sigma\tag{28}\] where the allocation will again be based on support families and \(\widetilde{\mathbf{\Phi}}^k_\sigma\) denotes the set of \(k\)-tuples from \(\mathbf{A}_{n,k}\) allotted to the group \(\sigma\). In particular, for \(\mathbf{e} \in \mathbf{A}_{n,k}\), we have \[\mathcal{B}({\mathbf{e}})=\{i\in[f]: \mathbf{e}\cap \mathcal{F}_i\neq\emptyset\}, \qquad \beta_{\mathbf{e}}=|\mathcal{B}({\mathbf{e}})|\] and again, if excluded vertices are present (\(g >0\)), we let \(m=|\mathbf{e}\cap \mathcal{E}|\); otherwise \(m=0\). For every \(m\in [0, \min\{k,g\}]\), we define the set \[\label{wbqofvrz} \mathbf{Q}_{m,\beta} \triangleq \left\{ \mathbf{e} \in \mathbf{A}_{n,k}\; : \; \beta_{\mathbf{e}} = \beta ,\;|\mathbf{e} \cap \mathcal{E}|=m \right\}\tag{29}\] which describes the set of all \(k\)-tuples \(\mathbf{e} \in \mathbf{A}_{n,k}\) that intersect exactly \(\beta\) families and have \(m\) excluded vertices from \(\mathcal{E}\). Notice that \(\beta\) can take values in the range \(\big[\lceil\frac{k-m}{s}\rceil, k-m\big]\), and if \(m=k\leq g\), then \(\beta =0\), which means that all the vertices of \(k\)-tuple \(\mathbf{e}\) are from \(\mathcal{E}\). We seek to partition \(\mathbf{A}_{n,k}\) as follows \[\mathbf{A}_{n,k}=\bigcup_{m=0}^{\min\{k, g\}}\bigcup_{\beta=\lceil\frac{k-m}{s}\rceil}^{k-m} \mathbf{Q}_{m,\beta}.\] Towards this, let us fix \(k\in [1, d-1]\), for any \(\beta \in [\lceil\frac{k}{s}\rceil, k]\) and for each \(\mathcal{I}\in\binom{[f]}{\beta}\), let us define \[\label{eq:Q95beta44I} \mathbf{Q}_{\beta,\mathcal{I}}^{k} \triangleq \big\{\mathbf{e}\in\mathbf{A}_{n,k}\;:\;\mathcal{B}(\mathbf{e})=\mathcal{I},\; \mathbf{e}\in\bigcup_{m=0}^{\min\{k-\beta,g\}}\mathbf{Q}_{m,\beta}\big\}\tag{30}\] to be the set of all \(k\)-tuples \(\mathbf{e} \in \mathbf{A}_{n,k}\) that intersect exactly all families in \(\mathcal{I}\) (again we recall that \(\mathcal{B}(\mathbf{e})\) denotes the set of families that \(\mathbf{e}\) intersects). It is relatively easy to see that the cardinality \(t_{\beta}^{k}\triangleq|\mathbf{Q}_{\beta,\mathcal{I}}^{k}|\) remains the same for any \(\mathcal{I}\in\binom{[f]}{\beta}\) (fixed \(\beta\) and \(k\)). Let us now also define \[\label{eq:Q95beta} \mathbf{Q}_{\beta}^{k}\triangleq\bigcup_{\mathcal{I}\in\binom{[f]}{\beta}}\mathbf{Q}_{\beta,\mathcal{I}}^{k} \subset \mathbf{A}_{n,k}\tag{31}\] to be the set of all \(k\)-tuples that meet exactly \(\beta\) families. Now, we follow a similar approach as that described in Section 4.1; for any \(k \in [1, d-1]\) and every group \(\sigma \in {[f] \choose d}\), we describe \(\widetilde{\mathbf{\Phi}}^{k}_{\sigma}\) – i.e., the set of all \(k\)-tuples allotted to the group \(\sigma\) from \(\mathbf{A}_{n,k}\) – as follows \[\label{eq:32phi9532k60d} \widetilde{\mathbf{\Phi}}_{\sigma}^{k}=\bigcup_{\beta=\beta_{\mathrm{min}}^{k}}^{\beta_{\mathrm{max}}^{k}}\bigcup_{\mathcal{I}\subset \sigma}\mathbf{Q}_{\beta, \mathcal{I}, \sigma}^{k}\tag{32}\] where \(\mathbf{Q}_{\beta, \mathcal{I}, \sigma}^{k}\) is a subset of \(\mathbf{Q}_{\beta, \mathcal{I}}^{k}\) allotted to \(\sigma\), and where \[\label{eq:beta95min} \beta_{\mathrm{min}}^{k} \;\triangleq\; \left\lceil \frac{k-\min\{k,g\}}{s} \right\rceil \;=\; \left\lceil \frac{\max\{0,k-g\}}{s} \right\rceil,\tag{33}\] \[\label{eq:beta95max} \beta_{\max}^{k} \;\triangleq\; k.\tag{34}\] At this point, group \(\widetilde{\mathbf{\Phi}}_{\sigma}, \;\sigma \in {[f]\choose d},\) will be formed as follows \[\label{eq:32group32sigma4432power32set} \widetilde{\mathbf{\Phi}}_{\sigma}=\bigcup_{k=1}^{d} \widetilde{\mathbf{\Phi}}_{\sigma}^{k}.\tag{35}\] Finally, combining 27 , 28 , and 35 , we have the desired partition \[\bigcup_{k=1}^{d}\mathbf{A}_{n,k}=\bigcup_{k=1}^{d}\bigcup_{\sigma \in {[f]\choose d}} \widetilde{\mathbf{\Phi}}_{\sigma}^{k}=\bigcup_{\sigma \in {[f]\choose d}}\bigcup_{k=1}^{d} \widetilde{\mathbf{\Phi}}_{\sigma}^{k}=\bigcup_{\sigma \in {[f]\choose d}} \widetilde{\mathbf{\Phi}}_{\sigma}.\]

4.3 Analysis of the \(N'\)-partition of \(\mathbf{A}_{n,d}\) and of \(\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\).↩︎

The following lemma quantifies the uniformity of the edge allocation across intermediate groups.

Now, continuing, we sum the bounds above, to get \[\begin{align} |\cup_{k=1}^{d} \widetilde{\mathbf{\Phi}}_{\sigma}^{k}|\le \sum_{k=1}^{d} \big( \frac{\binom{n}{k}}{\binom{f}{d}} + 2^{d} - d \big) &= \frac{\sum_{k=1}^{d} \binom{n}{k}}{\binom{f}{d}} + \sum_{k=1}^{d} (2^{d} - d) \tag{36}\\ &\le \frac{\sum_{k=1}^{d} \binom{n}{k}}{\binom{f}{d}} + 2^d d \tag{37} \end{align}\] where the transition from 36 to 37 follows because \(d\le 2^{d}\) for \(d\ge 1\).

In conclusion, the maximum group size for a hypergraph with rank at most \(d\), satisfies \[\max_{\sigma \in [N']} |\widetilde{\mathbf{\Phi}}_{\sigma}|=\max_{\sigma \in \binom{[f]}{d}} \left\{ |\cup_{k=1}^d \widetilde{\mathbf{\Phi}}_{\sigma}^{k}| \right\} \le \frac{\sum_{k=1}^{d} \binom{n}{k}}{\binom{f}{d}} + 2^{d} d\] and similarly \[\min_{\sigma \in [N']} |\widetilde{\mathbf{\Phi}}_{\sigma}|=\min_{\sigma \in \binom{[f]}{d}} \left\{ |\cup_{k=1}^d \widetilde{\mathbf{\Phi}}_{\sigma}^{k}| \right\} \ge \frac{\sum_{k=1}^{d} \binom{n}{k}}{\binom{f}{d}} - 2^{d} d .\] These will be used later on. We now continue to extend the partition \(\widetilde{\mathbb{P}}=\{\widetilde{\mathbf{\Phi}}_{\sigma}: \sigma \in {[f] \choose d}\}\) from \(N'={f\choose d}\) to \(N\) groups, for both the uniform and non-uniform cases.

4.4 Extending the Partition of \(\mathbf{A}_{n,d}\) and \(\bigcup_{k=1}^{d}\mathbf{A}_{n,k}\), from \(N'\) Groups to \(N\) Groups↩︎

Starting with the uniform case, let us recall (cf. 26 ) that we have already partitioned \(\mathbf{A}_{n,d}\) into \(N' = \binom{f}{d}\) disjoint⁹ groups \[\widetilde{\mathbf{\Phi}}_{\sigma_1}^{d},\dots,\widetilde{\mathbf{\Phi}}_{\sigma_{N'}}^{d}, \;\; \sigma_1,\dots,\sigma_{N'}\in\binom{[f]}{d}.\] Similarly, for the general non-uniform case, let us recall 28 , where \(\mathbf{A}_{n,k}\) is partitioned into \(N' = \binom{f}{d}\) disjoint groups \[\widetilde{\mathbf{\Phi}}_{\sigma_1}^{k},\dots,\widetilde{\mathbf{\Phi}}_{\sigma_{N'}}^{k}, \;\; \sigma_1,\dots,\sigma_{N'}\in\binom{[f]}{d}, \quad \text{for all} \;k\in [1,d].\] From now on, let us assume, without loss of generality, that the indices \(\sigma_1,\dots,\sigma_{N'}\) are in lexicographic order, and then proceed to simplify notation by writing \(\widetilde{\mathbf{\Phi}}^{k}_j=\widetilde{\mathbf{\Phi}}^{k}_{\sigma_j}\), for any \(j\in [N']\). This simply transitions to a scalar index for each group. For each \(k \in [1,d]\), let us declare ¹⁰ \[\widetilde{\mathbb{P}}^k\triangleq\{\widetilde{\mathbf{\Phi}}_{1}^{k}, \widetilde{\mathbf{\Phi}}_{2}^{k}, \ldots, \widetilde{\mathbf{\Phi}}_{N'}^{k}\}.\] Then, for each \(k\), we redistribute the edges of the above \(N'\) groups of \(\widetilde{\mathbb{P}}^k\), to now all \(N\) groups, as described in the following steps. First, let us define the variables \[\label{eq:32q44p44r} q\triangleq\big\lfloor\frac{N}{N'}\big\rfloor,\qquad p\triangleq\big\lceil\frac{N}{N'}\big\rceil,\qquad r\triangleq N\bmod N'\tag{38}\] noting that \(N=qN'+r,\) where \(p=q\;\text{if }r=0\), and \(p=q+1\;\text{if }r>0.\) At this point, we proceed with dividing up the edges of each of the first \(N'\) groups into different smaller parts, to be followed by the second step of redistributing some of these smaller parts to fill up the empty \(N-N'\) groups.

Step 1 – Dividing up (the edges of) each of the first \(N'\) groups

For each \(b\in[N']\), we define \[s_b\triangleq\begin{cases} p & \text{if } 1\le b\le r,\\[4pt] q & \text{if } r<b\le N' \end{cases}\] and we split each \(\widetilde{\mathbf{\Phi}}_b^{k}\) into \(s_b\) disjoint sub-parts using lexicographic ordering (we go through \(\widetilde{\mathbf{\Phi}}_b^{k}\) and we assign hyperedges, in a round-robin manner, to one of the \(s_b\) disjoint sub-parts, one after the other). This naturally yields sub-parts of equal sizes, plus or minus \(1\). We keep track of the exact size of each sub-part. We denote these sub-parts by \(\widetilde{\mathbf{\Phi}}_b^{k,(0)},\widetilde{\mathbf{\Phi}}_b^{k,(1)},\dots,\widetilde{\mathbf{\Phi}}_b^{k,(s_b-1)},\) where \(\widetilde{\mathbf{\Phi}}_b^{k}=\bigcup_{b'=0}^{s_b-1}\widetilde{\mathbf{\Phi}}_b^{k,(b')}.\)

Step 2 – Shifting sub-parts to extend to \(N\) groups

We then relabel these sub-parts to obtain the desired \(N\) groups. We define the new \(N\) groups \(\widetilde{\mathbf{\Phi}}_1^{k},\dots,\widetilde{\mathbf{\Phi}}_N^{k}\), by the indexing rule \[\label{eq:32extenstion} \widetilde{\mathbf{\Phi}}_{\,b + b'N'}^{k} \;\triangleq\;\widetilde{\mathbf{\Phi}}_b^{k,(b')}, \;\text{for } b\in[N'],\; b'\in\{0,\dots,s_b-1\}.\tag{39}\] This now gives us the partition \(\widetilde{\mathbb{P}}^{k}\) for all \(k \in [1,d],\) which takes the form \[\label{eq:32p95tilde} \widetilde{\mathbb{P}}^{k}=\{\widetilde{\mathbf{\Phi}}_1^{k},\dots,\widetilde{\mathbf{\Phi}}_N^{k}\}.\tag{40}\] As a result, we get \(\widetilde{\mathbb{P}}\) which has now been extended from \(N'\) designed groups to \(N\) desired groups \(\{\widetilde{\mathbf{\Phi}}_{1}, \widetilde{\mathbf{\Phi}}_{2}, \ldots, \widetilde{\mathbf{\Phi}}_{N}\}\), where \[\label{eq:32phi95b:1tod} \widetilde{\mathbf{\Phi}}_{b}=\bigcup_{k=1}^{d}\widetilde{\mathbf{\Phi}}_{b}^{k}, \quad b\in [N].\tag{41}\]

To evaluate the uniformity of the group sizes across the partition \(\widetilde{\mathbb{P}}\) of \(\bigcup_{k=1}^{d} \mathbf{A}_{n,k}\), we examine the balance parameter \(\delta\), which takes the form \[\delta = \frac{\max_{b \in [N]} |\widetilde{\mathbf{\Phi}}_{b}|}{\lceil\sum_{k=1}^{d} \binom{n}{k} / N\rceil}\] in the general case, and \[\delta = \frac{\max_{b \in [N]} |\widetilde{\mathbf{\Phi}}_{b}|}{\lceil \binom{n}{d} / N\rceil}\] in the specific case of uniform hypergraphs. This, together with \(\pi\), is captured in the following lemma¹¹.

4.5 Partition Refinement for \(\mathbf{X}\)↩︎

Let us recall that, up until now, up to Section 4.4, we have only provided a partition \(\widetilde{\mathbb{P}} = \{ \widetilde{\mathbf{\Phi}}_1, \widetilde{\mathbf{\Phi}}_2, \ldots, \widetilde{\mathbf{\Phi}}_N \}\) of \(\bigcup_{k=1}^{d} \mathbf{A}_{n,k}\) (or of \(\mathbf{A}_{n,d}\) in the \(d\)-uniform case). Now we must account for \(\mathbf{X}\). The vertex allocation is automatic; we simply maintain the exact vertex allocation given by the described partition of the complete hypergraph, and thus we maintain the same \(\pi\) guarantee that we have seen in Lemma 3.

For the edge allocation, we now convert \(\widetilde{\mathbb{P}}\) into a partition \[\begin{align} \label{eq:RefinedPartitionX1} \mathbf{X} = \mathbf{\Phi}_{1} \cup \cdots \cup \mathbf{\Phi}_{N} \end{align}\tag{43}\] of the specific edge set \(\mathbf{X} \subseteq \bigcup_{k=1}^{d} \mathbf{A}_{n,k}\) (or \(\mathbf{X} \subseteq \mathbf{A}_{n,d}\) in the uniform case), simply by assigning to each group \(b\in [N]\), the entries of the group \[\label{eq:32sampled32group32size} \mathbf{\Phi}_{b}=\widetilde{\mathbf{\Phi}}_b \cap \mathbf{X}.\tag{44}\] We must now account for the specific \(\delta_{\mathbf{X}}\). To do so, we define \[\label{eq:32random4432mu95max} \mu_b\triangleq| \mathbf{\Phi}_{b}|, \;b\in[N], \;\;\mu_{\min} \triangleq \min_{b\in[N]}\mu_b, \quad \mu_{\max} \triangleq \max_{b\in[N]}\mu_b\tag{45}\] where we see that \(\mu_b=|\mathbf{\Phi}_b|=|\bigcup_{k=1}^{d}\mathbf{\Phi}_b^{k}|\) (and in the uniform case, \(\mu_b=|\mathbf{\Phi}_b|=|\mathbf{\Phi}_b^{d}|\)). In both cases, the balance factor is \[\label{eq:32random4432delta95x44n} \delta_{\mathbf{X}} = \frac{\max_{b} \mu_b}{\lceil|\mathbf{X}|/N\rceil}.\tag{46}\]

While the refinement step in 43 , 44 is simple enough, it runs the risk of yielding a very large \(\delta_\mathbf{X}\), depending on \(\mathbf{X}\). Bounding \(\delta_{\mathbf{X}}\) is handled in Proposition 1, which shows that, under an independent thinning model with identical edge inclusion probability \(\varphi\geq \varphi_{\min,\delta}\), the IC design guarantees, with probability at least \(1-\tfrac{1}{n^z}\), a bounded load balance factor \(\delta_{\mathbf{X}}\leq 5\) for both \(d\)-uniform and non-uniform hypergraphs. At this point, we can also conclude that a notable feature of the proposed IC design is its extremely low computational complexity. The vertex placement is determined once and for all as an explicit deterministic function of \((n,d,N)\) and remains completely independent of the realized hypergraph. Thereafter, each hyperedge is assigned directly to a partition through a fixed deterministic mapping, requiring only the evaluation of a simple combinatorial rule. Consequently, the overall complexity is \(O(|\mathbf{X}|)\), which is optimal up to constant factors since every hyperedge must be inspected at least once.

5 Conclusions↩︎

Our results yield the following conclusions which hold for the problem of minimizing the MVF in hypergraph edge partitioning, under our general model where each hyperedge \(\mathbf{e} \in \mathbf{A}\) may appear independently with its own probability \(\varphi_{\mathbf{e}}\), forming sufficiently populated hypergraphs with \(|\mathbf{X}| \gtrsim nN\log N.\) A central conclusion of this work is that, over a broad class of probabilistic hypergraph models, the fundamental limits of hypergraph edge partitioning can be characterized up to explicit and small constant factors; Over a broad range of probabilistic hypergraph models, the optimal footprint is – with a very high probability \(1-\frac{1}{n^z}\) – within a small constant factor of \[\pi^{\bigstar}_{\mathbf{X}} = \frac{1}{2\sqrt{2}}\frac{n}{N^{1/d}}.\]

This is surprising, as it says that as long as \(|\mathbf{X}| \gtrsim nN\log N.\), the detailed structure of the hypergraph may not play a dominant role in determining the optimal MVF. While identifying structural features such as communities, clusters, dense regions, local connectivity patterns, and favorable matching opportunities, is still of paramount importance, our results suggest that, once the hypergraph is sufficiently populated, the optimal footprint is governed to a sizable extent by the combinatorial parameters \((n,d,N)\), with a comparatively limited dependence on the finer structural details of the hypergraph.

This also entails a strong form of universality. Classical hypergraph partitioning methods are often calibrated to the aforementioned specific structural properties of the input hypergraph. This calibration is most certainly important in practice. What we now know though is that a single, fixed, deterministic construction achieves a near-optimal performance uniformly across a broad range of models. Thus, both the fundamental limit and the achievable scheme exhibit a remarkable degree of universality, again suggesting that – in our setting, and under our assumptions – for footprint minimization, the detailed structure of the hypergraph may not carry abundant information, beyond what is already encoded in the underlying combinatorial parameters.

Our construction – which achieves a footprint within a constant factor of the optimum, over a broad class of probabilistic models – follows a simple philosophy: the vertex placement is fixed a priori and depends only on \((n,d,N)\), remaining completely independent of the realized hypergraph. This is perhaps the most surprising outcome of this work; That for the footprint minimization objective considered here, near-optimal performance can be achieved by a placement that depends only on \((n,d,N)\) and is completely independent of the realized hypergraph.

---

1. The authors are with the Communication Systems Department, EURECOM, Sophia Antipolis, France (e-mail: {maheri, karakkad, elia}eurecom.fr?).↩︎

2. This work was supported by the France 2030 ANR program “PEPR Networks of the Future” (ref. ANR-22-PEFT-0010).↩︎

3. There is a variety of such metrics. Another common variant – which, after normalization, serves as a lower bound on the MVF – is the average replication factor (ARF), measuring the average number of groups/partitions to which a vertex is assigned. One advantage of the MVF metric is that it admits a meaningful characterization independently of the balance parameter \(\delta_{\mathbf{X}}\), whereas the ARF depends strongly on it. Furthermore, the MVF captures a worst-case quantity, thus naturally reflecting communication and storage bottlenecks in distributed settings ajwani2023open?.↩︎

4. Models with latent variables (e.g., stochastic block, mixed-membership, latent-space, or geometric models) are encompassed conditionally on the realization of those latent variables, which induces edge-specific probabilities \(\varphi_{\mathbf{e}}\) and independent edge sampling. In more specific terms: a model, such as a geometric model, may shape arbitrarily the probabilities \(\varphi_{\mathbf{e}}\) with which each hyperedge \(\mathbf{e} \in \mathbf{A}\) appears, and after that, the sampling is done independently, edge after edge.↩︎

5. By all schemes, we refer to all edge partitioning schemes that assign each edge to exactly one of the \(N\) groups.↩︎

6. The condition on \(N\) is very loose, as it allows \(N\) to rise up to approximately \(\left(\frac{n}{2d}\right)^{d/2}\), which can far exceed \(n\). In the context of, for example, distributed computing, this would entail many more servers than files.↩︎

7. Think of these as leftover vertices, a result of parameter divisibility; if for example we have \(n=102\) vertices, and \(f=20\) vertex families, we will have \(g=2\) leftover vertices (vertices \(101\) and \(102\)), and these will be handled later on.↩︎

8. This is because \(\beta_{\mathbf{t}}\le d-1\) for any \(\mathbf{t} \in \mathbf{A}_{\mathrm{rem}}\).↩︎

9. Note that in the uniform case, when context allows, we will often use the simpler notation \(\widetilde{\mathbf{\Phi}}_{\sigma_i}\) to represent \(\widetilde{\mathbf{\Phi}}_{\sigma_i}^{d}\).↩︎

10. Note that in the uniform case, when context allows, we will often use the simpler notation \(\widetilde{\mathbb{P}}\) to represent \(\widetilde{\mathbb{P}}^d\).↩︎

11. Note that we are still at the point where we are partitioning the entire universe of hyperedges. We have not reached \(\mathbf{X}\) yet.↩︎

12. Our construction here has been slightly extended, compared to that in IC?, to now cover all cases of \(d\leq n/2\) (rather than \(d\leq n/32\) from IC?). It is a trivial exercise to see that the above bound \(\pi\leq sd+g = n-(f-d)s\leq 2sd\) carries over directly to our currently extended range of \(d\) (to have a closer look at this, please see Equation 109 in Appendix 7.1).↩︎