* [33] Kevin J. Lang, Michael W. Mahoney, and Lorenzo Orecchia.  Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow.  In Jan Vahrenhold, editor, Experimental Algorithms, Lecture Notes in Computer Science, pages 197–208, Berlin, Heidelberg, 2009\. Springer.
  * [34] Tom Leighton and Satish Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM, 46(6):787–832, November 1999.
  * [35] Pan Li and Olgica Milenkovic.  Inhomogeneous Hypergraph Clustering with Applications.  In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [36] Pan Li and Olgica Milenkovic.  Submodular Hypergraphs: P-Laplacians, Cheeger Inequalities and Spectral Clustering.  In Proceedings of the 35th International Conference on Machine Learning, pages 3014–3023. PMLR, July 2018.
  * [37] Pan Li and Olgica Milenkovic.  Submodular hypergraphs: p-laplacians, cheeger inequalities and spectral clustering.  In International Conference on Machine Learning, pages 3014–3023. PMLR, 2018.
  * [38] Anand Louis.  Cut-matching games on directed graphs.  arXiv preprint arXiv:1010.1047, 2010.
  * [39] Anand Louis.  Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 713–722, New York, NY, USA, June 2015. Association for Computing Machinery.
  * [40] Anand Louis.  Hypergraph markov operators, eigenvalues and approximation algorithms.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 713–722, 2015.
  * [41] Anand Louis and Yury Makarychev.  Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion.  Theory of Computing, 12(17):1–25, October 2016.
  * [42] Anand Louis, Prasad Raghavendra, and Santosh Vempala.  The Complexity of Approximating Vertex Expansion.  arXiv:1304.3139 [cs], November 2013.
  * [43] David W. Matula and Farhad Shahrokhi.  Sparsest cuts and bottlenecks in graphs.  Discrete Applied Mathematics, 27(1):113–123, May 1990.
  * [44] Mukund Narasimhan, Nebojsa Jojic, and Jeff A Bilmes.  Q-Clustering.  In Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
  * [45] Lorenzo Orecchia.  Fast Approximation Algorithms for Graph Partitioning using Spectral and Semidefinite-Programming Techniques.  PhD thesis, EECS Department, University of California, Berkeley, May 2011\.
  * [46] Lorenzo Orecchia, Konstantinos Ameranis, Charalampos Tsourakakis, and Kunal Talwar.  Practical almost-linear-time approximation algorithms for hybrid and overlapping graph clustering.  In International Conference on Machine Learning, pages 17071–17093. PMLR, 2022.
  * [47] Lorenzo Orecchia, Konstantinos Ameranis, Charalampos Tsourakakis, and Kunal Talwar.  Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph Clustering.  In Proceedings of the 39th International Conference on Machine Learning, pages 17071–17093. PMLR, June 2022.
  * [48] Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K Vishnoi.  Approximating the exponential, the lanczos method and an o (m)-time spectral algorithm for balanced separator.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1141–1160, 2012.
  * [49] Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi.  On partitioning graphs via single commodity flows.  In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 461–470, New York, NY, USA, May 2008. Association for Computing Machinery.
  * [50] Thatchaphol Saranurak and Di Wang.  Expander Decomposition and Pruning: Faster, Stronger, and Simpler, December 2021.
  * [51] Jonah Sherman.  Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut, August 2009.
  * [52] Alistair Sinclair and Mark Jerrum.  Approximate counting, uniform generation and rapidly mixing Markov chains.  Information and Computation, 82(1):93–133, July 1989.
  * [53] Daniel A. Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pages 81–90, New York, NY, USA, June 2004. Association for Computing Machinery.
  * [54] Daniel A Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81–90, 2004.
  * [55] Nate Veldt, Austin R. Benson, and Jon Kleinberg.  Minimizing Localized Ratio Cut Objectives in Hypergraphs.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’20, pages 1708–1718, New York, NY, USA, August 2020. Association for Computing Machinery.
  * [56] Nate Veldt, Austin R. Benson, and Jon Kleinberg.  Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components, October 2021.
  * [57] J.Y. Zien, M.D.F. Schlag, and P.K. Chan.  Multilevel spectral hypergraph partitioning with arbitrary vertex sizes.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(9):1389–1399, September 1999.

##  Appendix A An Optimization View on Submodular Hypergraph Partitioning

In this section, we prove some technical lemmata used in the body of the
paper. We begin with a proof of Fact 7.

###### Proof of Fact 7.

Symmetry of $\delta$ follows from definition. To show that $\delta$ is
submodular, let $S,T\subseteq V$. We have one of two cases:

  1. 1.

$F(S)\leq F(\overline{S})$ and $F(T)\leq F(\overline{T})$, or
$F(\overline{S})\leq F(S)$ and $F(\overline{T})\leq F(T)$,

  2. 2.

$F(S)\leq F(\overline{S})$ and $F(\overline{T})\leq F(T)$, or
$F(\overline{S})\leq F(S)$ and $F(T)\leq F(\overline{T})$.

For Case 1, we may assume without loss of generality that $F(S)\leq
F(\overline{S})$ and $F(T)\leq F(\overline{T})$. We then have:

$\displaystyle\delta(S\cup T)+\delta(S\cap T)$ $\displaystyle=\min\\{F(S\cup
T),\;F(\overline{S}\cap\overline{T})\\}+\min\\{F(S\cap
T),F(\overline{S}\cup\overline{T})\\}$ $\displaystyle\leq F(S\cup T)+F(S\cap
T)$ $\displaystyle\leq F(S)+F(T)=\delta(S)+\delta(T).$

Similarly, for Case 2, we may assume $F(S)\leq F(\overline{S})$ and
$F(\overline{T})\leq F(T)$. We then have:

$\displaystyle\delta(S\cup T)+\delta(S\cap T)$ $\displaystyle=\min\\{F(S\cup
T),\;F(\overline{S}\cap\overline{T})\\}+\min\\{F(S\cap
T),F(\overline{S}\cup\overline{T})\\}$ $\displaystyle\leq F(S\cup
T)+F(\overline{S}\cup\overline{T})$ $\displaystyle\leq
F(S)+F(\overline{T})=\delta(S)+\delta(T).$

Showing that for every $S,T\subseteq V$:

$\delta(S\cup T)+\delta(S\cap T)\leq\delta(S)+\delta(T),$

and hence $\delta$ is submodular as needed. ∎

Let us next show that the ratio-cut improvement problem is equivalent to (RC-
NonCvx) introduced in Section 4. We first require that the Lovász extension is
unaffected by a shift of the input by $\boldsymbol{1}$.

######  Lemma 15.

Suppose $\delta_{h}:2^{h}\rightarrow\mathbb{R}$ is a monotone submodular cut
function. For any $u\in\mathbb{R}$,

$\bar{\delta}_{h}(\mathbf{x}+u\cdot\boldsymbol{1})=\bar{\delta}_{h}(\mathbf{x}).$

###### Proof.

Since $\delta_{h}$ is a monotone submodular cut function, there exists a non-
decreasing submodular function $F_{h}:2^{h}\rightarrow\mathbb{R}$ such that
$F_{h}(\varnothing)=0$ and $\delta_{h}(S)=\min\\{F_{h}(S),F_{h}(\bar{S})\\}$.
Observe then that if $\mathbf{y}\in\mathcal{B}(\delta_{h})$ is in the base
polytope, we have

$\sum_{i\in
h}y_{i}\leq\delta_{h}(h)=\min\\{F_{h}(h),F_{h}(\varnothing)\\}=0\,.$

This implies that for any $u\in\mathbb{R}$, the Lovász extension of
$\delta_{h}$ satisfies:

$\bar{\delta}_{h}(\mathbf{x}+u\cdot\boldsymbol{1})=\max_{\mathbf{y}\in\mathcal{B}(\delta_{h})}\langle\mathbf{y},\mathbf{x}+u\cdot\boldsymbol{1}\rangle=\max_{\mathbf{y}\in\mathcal{B}(\delta_{h})}\langle\mathbf{y},\mathbf{x}\rangle=\bar{\delta}_{h}(\mathbf{x}),$

since $\mathbf{y}\in\mathcal{B}(\delta_{h})$ implies
$\langle\mathbf{y},\boldsymbol{1}\rangle=0$. ∎

###### Proof of Lemma 1.

Observe that the denominator of the ratio-cut objective is a monotone
submodular cut function applied over the entire vertex set

$\delta_{\bm{\mu}}(S)=\min\\{\bm{\mu}(S),\bm{\mu}(\bar{S})\\},$

Consequently, for every $S\subseteq V$:

$\Psi_{G}(S)=\frac{\sum_{h\in E}w_{h}\delta_{h}(S\cap
h)}{\min\\{\bm{\mu}(S),\bm{\mu}(\bar{S})\\}}=\frac{\delta_{G}(S)}{\delta_{\bm{\mu}}(S)}={\overline{\delta}_{G}(\boldsymbol{1}^{S})\over\overline{\delta}_{\bm{\mu}}(\boldsymbol{1}^{S})},$

which gives:

$\Psi_{G}^{*}\geq\min_{\mathbf{x}\in\mathbb{R}^{n}}{\overline{\delta}_{G}(\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(\mathbf{x})}.$

We now prove the opposite inequality by showing the second part of the lemma.
By Lemma 15, the value of the ratio in the right-hand side of (RC-NonCvx) is
invariant under shifting all the coordinates by a fixed constant. Furthermore,
both the numerator and the denominator of the right-hand side of (RC-NonCvx)
are homogeneous and hence their ratio is invariant under scaling $\mathbf{x}$
by a constant, i.e., for any $u\in\mathbb{R}$:

${\overline{\delta}_{G}(u\cdot\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(u\cdot\mathbf{x})}={u\cdot\overline{\delta}_{G}(\mathbf{x})\over
u\cdot\overline{\delta}_{\bm{\mu}}(\mathbf{x})}={\overline{\delta}_{G}(\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(\mathbf{x})}.$

Hence, for any $\mathbf{x}$, by letting $\hat{\mathbf{x}}$ be defined as:

$\hat{x_{i}}={x_{i}-\min_{j}x_{j}\over\max_{j,k}(x_{j}-x_{k})},$

we have $\max_{i}\hat{x}_{i}=1$, $\min_{i}\hat{x}_{i}=0$, and:

${\overline{\delta}_{G}(\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(\mathbf{x})}={\overline{\delta}_{G}(\hat{\mathbf{x}})\over\overline{\delta}_{\bm{\mu}}(\hat{\mathbf{x}})}.$

We then have, as per Fact 4:

${\overline{\delta}_{G}(\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(\mathbf{x})}={\overline{\delta}_{G}(\hat{\mathbf{x}})\over\overline{\delta}_{\bm{\mu}}(\hat{\mathbf{x}})}={\operatorname*{\mathbb{E}}_{t\sim[0,1]}[\delta_{G}(S_{t}(\hat{\mathbf{x}}))]\over\operatorname*{\mathbb{E}}_{t\sim[0,1]}[\delta_{\bm{\mu}}(S_{t}(\hat{\mathbf{x}}))]}.$

Hence, there must exist some $t\in[0,1]$ such that:

${\overline{\delta}_{G}(\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(\mathbf{x})}\geq{\delta_{G}(S_{t}(\hat{\mathbf{x}}))\over\delta_{\bm{\mu}}(S_{t}(\hat{\mathbf{x}}))}.$

This gives:

$\min_{\mathbf{x}\in\mathbb{R}^{n}}{\overline{\delta}_{G}(\mathbf{x})\over\overline{\delta}_{\bm{\mu}}(\mathbf{x})}=\Psi_{G}^{*},$

as needed for the first part of the lemma. Moreover, computing and checking
all of the sets $\\{S_{t}(\mathbf{x})\\}_{t\in[0,1]}$ only requires time
$O(n\log n)$ for sorting the entries of $\mathbf{x}$ and time
$O(\mathsf{sp}(G)+|V|)$ for evaluating the numerator and denominator. ∎

A critical step towards deploying the cut-matching game was to restrict our
attention to monotone submodular cut functions, for which Theorem 5 provides a
specific geometric characterization. Towards proving this lemma, we first
demonstrate that the base polytope of a monotone submodular cut function
$\delta_{h}$ is enclosed within a scaling of the symmetric submodular
polyhedron of $F$.

######  Lemma 16.

Suppose $\delta_{h}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{F(S),F(\bar{S})\\}$ where $F:2^{h}\rightarrow\mathbb{R}$ is
a non-decreasing submodular function such that $F(\varnothing)=0$ and
$F(\\{i\\})>0$ for all $i\in V$. Let $\mathbf{y}\in\mathcal{B}(\delta_{h})$.
For all $A\subseteq h$, we have

$\bigg{\lvert}\sum_{i\in A}y_{i}\bigg{\rvert}\leq\delta_{h}(A)$

###### Proof.

Observe that since $\mathbf{y}\in\mathcal{B}(\delta_{h})$, we immediately have

$\sum_{i\in A}y_{i}\leq\delta_{h}(A)$

On the other hand, since $\sum_{i\in h}y_{i}=\delta_{h}(h)=0$, we have

$\sum_{i\in
A}y_{i}=-\sum_{i\in\bar{A}}y_{i}\geq-\delta_{h}(\bar{A})=-\delta_{h}(A)$

as required. ∎

We are now ready to prove Theorem 5.

###### Proof of Theorem 5.

First, suppose $\mathbf{y}\in\mathcal{P}_{\textup{sym}}(F)$, and fix any
$S\subseteq h$. Note that:

$\sum_{i\in S}y_{i}\leq\sum_{i\in S}\lvert y_{i}\rvert\leq F(S).$

Simultaneously, since $\langle\mathbf{y},\boldsymbol{1}\rangle=0$, we have:

$\sum_{i\in S}y_{i}=-\sum_{i\in\bar{S}}y_{i}\leq\sum_{i\in\bar{S}}\lvert
y_{i}\rvert\leq F(\bar{S}).$

Consequently, we have $\sum_{i\in
S}y_{i}\leq\min\\{F(S),F(\bar{S})\\}=\delta_{h}(S)$, giving
$\mathcal{P}_{\textup{sym}}(F)\subseteq\mathcal{B}(\delta_{h})$.

Now, suppose $\mathbf{y}\in\mathcal{B}(\delta_{h})$, and fix any $S\subseteq
h$. Let $S^{+}=\\{i\in S:y_{i}\geq 0\\}$, and $S^{-}=\\{i\in S:y_{i}<0\\}$.
Observe

$\sum_{i\in S}\lvert y_{i}\rvert=\sum_{i\in S^{+}}y_{i}-\sum_{i\in
S^{-}}y_{i}\leq\left\lvert\sum_{i\in
S^{+}}y_{i}\right\rvert+\left\lvert\sum_{i\in
S^{-}}y_{i}\right\rvert\leq\delta_{h}(S^{+})+\delta_{h}(S^{-}),$

where the last inequality follows by Lemma 16. However, this means:

$\displaystyle\delta_{h}(S^{+})+\delta_{h}(S^{-})$
$\displaystyle=\min\\{F(S^{+}),F(\bar{S^{+}})\\}+\min\\{F(S^{-}),F(\bar{S^{-}})\\}$
$\displaystyle\leq F(S^{+})+F(S^{-})$ $\displaystyle\leq 2\cdot F(S),$

since both $S^{+},S^{-}\subseteq S$ and $F$ is non-decreasing. Consequently,
$\sum_{i\in S}\lvert y_{i}\rvert\leq 2\cdot F(S)$ allowing us to conclude
$\mathcal{B}(\delta_{h})\subseteq\mathcal{P}_{\textup{sym}}(2\cdot F)$ as
required. The lowerbound to the Lovász extension
$\bar{\delta}_{h}(\mathbf{x})=\max_{\mathbf{y}\in\mathcal{B}(\delta_{h})}\langle\mathbf{y},\mathbf{x}\rangle$
is given by $\mathcal{P}_{\textup{sym}}(F)\subseteq\mathcal{B}(\delta_{h})$.
On the other hand,
$\mathcal{B}(\delta_{h})\subseteq\mathcal{P}_{\textup{sym}}(2\cdot F)$ implies
the upperbound:

$\max_{\mathbf{y}\in\mathcal{B}(\delta_{h})}\langle\mathbf{y},\mathbf{x}\rangle\leq\max_{\begin{subarray}{c}\mathbf{y}\in\mathcal{P}_{\textup{sym}}(2\cdot
F)\\\
\langle\mathbf{y},\boldsymbol{1}\rangle=0\end{subarray}}\langle\mathbf{y},\mathbf{x}\rangle=\max_{\begin{subarray}{c}\frac{1}{2}\cdot\mathbf{y}\in\mathcal{P}_{\textup{sym}}(F)\\\
\langle\mathbf{y},\boldsymbol{1}\rangle=0\end{subarray}}\langle\mathbf{y},\mathbf{x}\rangle=2\cdot\max_{\begin{subarray}{c}\mathbf{y}\in\mathcal{P}_{\textup{sym}}(F)\\\
\langle\mathbf{y},\boldsymbol{1}\rangle=0\end{subarray}}\langle\mathbf{y},\mathbf{x}\rangle,$

as required. ∎

We now prove Theorem 7. This requires the notion of factor graph introduced in
Section 2.

###### Proof Theorem 7.

Consider the hypergraph flow as a flow over the factor graph $\hat{G}.$ By a
standard application of dynamic trees (see for example Lemma 3.8 in [51]) to
the computation of flow-path decompositions [2] over $\hat{G}$ , we can
compute, in time $\tilde{O}(|\hat{E}_{G})=\tilde{O}(\mathsf{sp}(G))$, a graph
$H=(V,E_{H},\mathbf{w}^{H})$ such that there exist hypergraph flows
$\\{\mathbf{Y}^{e}\\}_{e\in E_{H}}$ in $G$ with the following properties:

  * •

$\sum_{e\in E_{H}}\mathbf{Y}^{e}=\mathbf{Y},$

  * •

For any $e\in E_{H}$, for any factor graph edge $\\{i,h\\}$, the flow
$(\mathbf{Y}^{e}_{h})_{i}$ has the same sign as $(\mathbf{Y}_{h})_{i}$. In
particular:

$\sum_{e\in E_{H}}\lvert\mathbf{Y}^{e}\rvert=|\mathbf{Y}|$ (17)

  * •

For all $e=\\{i,j\\}\in E^{H}$, we have
$\operatorname{dem}_{i}(\mathbf{Y})\geq 0$ and
$\operatorname{dem}_{j}(\mathbf{Y})<0.$ The flow $\mathbf{Y}^{e}$ routes
$w^{H}_{e}$ units of flow between vertex $i$ and vertex $j$, i.e.,

$\operatorname{dem}(\mathbf{Y}^{e})=w^{H}_{e}({\bf 1}_{i}-{\bf 1}_{j}).$

The last point proves the required statements about the bipartiteness of $H$
and its degrees. To complete the proof, we verify that
$H\preceq_{\operatorname{cong}_{G}(Y)}G$. For every hyperedge $h\in E_{G}$, we
have by Equation 17 and the absoluteness of $\|\cdot\|_{*,F_{h}}$:

$\left\|\sum_{e\in
E_{H}}|\mathbf{y}^{e}_{h}|\right\|_{*,F_{h}}=\left\||\mathbf{y}_{h}|\right\|_{*,F_{h}}=\left\|\mathbf{y}_{h}\right\|_{*,F_{h}}=w^{G}_{h}\operatorname{cong}_{h}(\mathbf{Y})\leq
w^{G}_{h}\operatorname{cong}_{G}(\mathbf{Y}).$

∎

##  Appendix B Local Relaxations of Minimum Ratio-cut Over Hypergraphs

###  B.1 Comparison to the Cut Improvement of Andersen & Lang

In this section, we briefly show that our formulation of the ratio-cut
improvement problem in Definition 7 generalizes the definition of the modified
quotient cut score, introduced by Andersen and Lang [5], to potentially non-
integral seed vectors (rather than cut seeds) and to arbitrary hypergraphs
(rather than graphs). Consider the following seed vector. Let $A\subseteq V$
be a cut, and define the vector $\mathbf{s}^{A,\bar{A}}\in\mathbb{R}^{V}$ to
be

$\mathbf{s}^{A,\bar{A}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\boldsymbol{1}^{A}-\nicefrac{{\mu(A)}}{{\mu(\bar{A})}}\cdot\boldsymbol{1}^{\bar{A}}\,.$
(18)

Assuming $\mu(A)\leq\mu(\bar{A})$, note that
$\langle\mathbf{s}^{A,\bar{A}},\boldsymbol{1}\rangle_{\bm{\mu}}=0$ and
$\lVert\mathbf{s}^{A,\bar{A}}\rVert_{\infty}\leq 1$, so that
$\mathbf{s}^{A,\bar{A}}$ is a valid seed vector. With this choice of seed
vector, the ratio-cut improvement objective on a graph $G$ becomes:

$\Psi_{G,\mathbf{s}^{A,\bar{A}}}(S)=\frac{\sum_{e\in
E}w_{h}\cdot\delta_{e}(S)}{\left\lvert\mu(A\cap
S)-\frac{\mu(A)}{\mu(\bar{A})}\cdot\mu(\bar{A}\cap S)\right\rvert},$

which is equal to the _modified quotient cut score_ considered by Andersen and
Lang.

###  B.2 Dual to the ratio-cut improvement problem

In this section we prove Lemma 4.

###### Proof of Lemma 4.

Let us proceed with taking the conjugate dual. Starting with (CI-Primal):

$\displaystyle\min_{\begin{subarray}{c}\mathbf{x}\in\mathbb{R}^{V}\\\
\langle\mathbf{s},\mathbf{x}\rangle_{\mu}=1\end{subarray}}\sum_{h\in
E}w_{h}\cdot\bar{\delta}_{h}(\mathbf{x})$
$\displaystyle=\min_{\mathbf{x}\in\mathbb{R}^{V}}\sum_{h\in
E}w_{h}\cdot\bar{\delta}_{h}(\mathbf{x})+\max_{\alpha\in\mathbb{R}}\Big{(}1-\langle\mathbf{s},\mathbf{x}\rangle_{\mu}\Big{)}$
$\displaystyle=\min_{\mathbf{x}\in\mathbb{R}^{V}}\max_{\alpha\in\mathbb{R}}\bigg{\\{}\alpha+\sum_{h\in
E}w_{h}\cdot\bar{\delta}_{h}(\mathbf{x})-\big{\langle}\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\mathbf{x}\big{\rangle}\bigg{\\}}\,.$

Recall that the Lovász extension is given by

$\bar{\delta}_{h}(\mathbf{x})=\max_{\mathbf{f}\in\mathcal{B}(\delta_{h})}\langle\mathbf{f},\mathbf{x}\rangle\,,$

and hence:

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{V}}\max_{\alpha\in\mathbb{R}}\bigg{\\{}\alpha+\sum_{h\in
E}w_{h}\cdot\bar{\delta}_{h}(\mathbf{x})-\big{\langle}\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\mathbf{x}\big{\rangle}\bigg{\\}}$
$\displaystyle=\min_{\mathbf{x}\in\mathbb{R}^{V}}\max_{\alpha\in\mathbb{R}}\bigg{\\{}\alpha+\sum_{h\in
E}\max_{\mathbf{f}_{h}\in
w_{h}\cdot\mathcal{B}(\delta_{h})}\langle\mathbf{f}_{h},\mathbf{x}\rangle-\big{\langle}\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\mathbf{x}\big{\rangle}\bigg{\\}}$
$\displaystyle=\min_{\mathbf{x}\in\mathbb{R}^{V}}\max_{\begin{subarray}{c}\alpha\in\mathbb{R},\mathbf{f}_{h}\in\mathbb{R}^{V}\\\
\mathbf{f}_{h}\in
w_{h}\cdot\mathcal{B}(\delta_{h})\end{subarray}}\bigg{\\{}\alpha+\sum_{h\in
E}\langle\mathbf{f}_{h},\mathbf{x}\rangle-\big{\langle}\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\mathbf{x}\big{\rangle}\bigg{\\}}$
$\displaystyle=\min_{\mathbf{x}\in\mathbb{R}^{V}}\max_{\begin{subarray}{c}\alpha\in\mathbb{R},\mathbf{f}_{h}\in\mathbb{R}^{V}\\\
\mathbf{f}_{h}\in
w_{h}\cdot\mathcal{B}(\delta_{h})\end{subarray}}\bigg{\\{}\alpha+\bigg{\langle}\sum_{h\in
E}\mathbf{f}_{h}-\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\,\mathbf{x}\bigg{\rangle}\bigg{\\}}\,.$

Strong duality always holds when the feasible region is polyhedron. Hence, we
have:

$\min_{\mathbf{x}\in\mathbb{R}^{V}}\max_{\begin{subarray}{c}\alpha\in\mathbb{R},\mathbf{f}_{h}\in\mathbb{R}^{V}\\\
\mathbf{f}_{h}\in
w_{h}\cdot\mathcal{B}(\delta_{h})\end{subarray}}\bigg{\\{}\alpha+\bigg{\langle}\sum_{h\in
E}\mathbf{f}_{h}-\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\,\mathbf{x}\bigg{\rangle}\bigg{\\}}=\max_{\begin{subarray}{c}\alpha\in\mathbb{R},\mathbf{f}_{h}\in\mathbb{R}^{V}\\\
\mathbf{f}_{h}\in
w_{h}\cdot\mathcal{B}(\delta_{h})\end{subarray}}\alpha+\min_{\mathbf{x}\in\mathbb{R}^{V}}\bigg{\langle}\sum_{h\in
E}\mathbf{f}_{h}-\alpha\big{(}\bm{\mu}\circ\mathbf{s}\big{)},\,\mathbf{x}\bigg{\rangle},$

which is equivalent to the required linear program. ∎

###  B.3 Approximate Ratio-Cut Improvement: Proof of Theorem 8

In this section, we address the problem of obtaining an $\epsilon$-approximate
primal-dual solution for $(G,\mathbf{s})$. This makes up the core
implementation of the matching player we use in the algorithm guaranteed by
Theorem 9 and Corollary 1. Firstly, we will show in the next section that
there are efficient algorithms that allow us to find $\epsilon$ primal-dual
solutions that work for arbitrary choices of $\delta_{h}$, leveraging recent
results by Axiotis et al. [8] and Ene et al. [24].

Then, in the section that follows, we will show that when the objective
functions $\delta_{h}$ are all standard hypergraph cut functions (i.e.
$\delta_{h}=\delta_{h}^{\mathsf{cut}}$ for every $h\in E$), the problem can be
solved in almost-linear time. We do so by solving a sequence of mixed
capacitated maximum flow problems. These are simply maximum flow problems over
an undirected graph in which both edges and vertices can have capacity
constraints. Our algorithm leverages the fact that one can find an approximate
solution to this type of problem in almost-linear time following a recent
result of Bernstein et al. [12].

####  B.3.1 Solvers for Arbitrary Monotone Submodular Cut Functions

In this section, we discuss how to obtain an $\epsilon$-approximate primal-
dual solution, given input $(G,\mathbf{s})$ where $G$ is equipped with an
arbitrary mscf $\\{\delta_{h}\\}_{h\in E}$.

The first step is to reduce the problem from optimization to feasibility via
binary search. Let $\alpha^{*}=\Psi^{*}_{G,\mathbf{s}}$ be the optimal value
of $\eqref{eq.rc-improve.primal}$. In the feasiblity version, for a fixed
$\alpha\geq 0,$ we consider the problem:

$\exists\mathbf{x}:\sum_{h\in
E}w_{h}\cdot\bar{\delta}_{h}(\mathbf{x})-\alpha\cdot\langle\mathbf{s},\mathbf{x}\rangle_{\mu}<0$
(19)

By the properties of the Lovász extension, this is equivalent to considering:

$\exists S\subseteq V:\sum_{h\in E}w_{h}\cdot\bar{\delta}_{h}({\bf
1}_{S})-\alpha\cdot\langle\mathbf{s},{\bf 1}_{S}\rangle_{\mu}<0$ ($\alpha$-CI-
Primal-Feasiblity)

The following fact is a simple consequence of the evenness of $\delta_{h}$
(Fact 5).

######  Fact 8.

Problem ($\alpha$-CI-Primal-Feasiblity) is feasible if and only if
$\alpha\geq\alpha^{*}.$

$\min_{T\subseteq V}\sum_{h\in
E}w_{h}\cdot\delta_{h}(T)-\alpha\cdot\langle\mathbf{s},{\bf
1}_{S}\rangle_{\mu}<0$ ($\alpha$-CI-Primal)

We note that for any given choice of $\alpha$, the above problem is an
instance of a decomposable submodular function minimization problem. That is,
it’s the minimization of a submodular function which can be written as the sum
of simpler submodular functions.

In the case in which $\\{\delta_{h}\\}_{h\in E}$ are arbitrary monotone
submodular cut functions, we consider two parameter settings: one in which the
rank of each hyperedge is bounded by some constant and one in which it is not.
For these two settings, we will solve the above two problems exactly using the
algorithms of Axiotis et al. and Ene et al. respectively.

For the algorithm of Ene et al. we require access to the following for every
$h\in H$:

  1. 1.

A _value oracle_ , which on input a subset $S\subseteq V$ returns
$\delta_{h}(S)$,

  2. 2.

A _quadratic minimization oracle_ $\mathcal{O}_{h}(\mathbf{w})$, which on
input $\mathbf{w}$ returns the solution to the problem:

$\min_{\mathbf{y}\in\mathcal{B}(\delta_{h})}\lVert\mathbf{y}+\mathbf{w}\rVert_{2}^{2}.$

The running time of the algorithm of Ene et al. is upperbounded by:

$\mathcal{O}\left(|V|\cdot\sum_{h\in
E}\Theta_{h}\log\left({|V|\cdot\max_{h}w_{h}}\right)\right),$

where $\Theta_{h}$ is the running time of a quadratic minimization oracle for
the function $\delta_{h}$. This running time bound follows from Corollary 3.6
in [24] with $\epsilon={1\over n}$.

In the case of bounded rank, we require a _linear optimization oracle_
$\mathcal{O}_{h}$ for each $h\in E$ which, on input any vector
$\mathbf{w}\in\mathbb{R}^{V}$ supported on $|h|$, finds a set $S$ minimizing
$\delta_{h}(S)-\mathbf{w}(S)$ in time $T_{h}$. Given this, we can get an exact
solution in time :

$\tilde{O}\left(\max_{h\in E}|h|^{2}\left(\sum_{h\in
E}|h|^{2}T_{h}+T_{\mathsf{flow}}\left(n,n+\sum_{h\in
E}|h|^{2}\right)\right)\right),$

where $T_{\mathsf{flow}}(n,m)$ is the time required to solve an instance of
the maximum flow problem in a graph with $n$ vertices and $m$ edges. Note that
since we are running the above algorithm in the case in which $|h|$ is at most
some constant, its running time becomes:

$\tilde{O}\left(\sum_{h\in
E}T_{h}+T_{\mathsf{flow}}\left(n,n+|E|\right)\right).$

This result follows from Theorem 1.1 with $\epsilon={1\over n}$.

In both cases the algorithm outputs both an optimal primal and an optimal dual
solution $\operatorname{dem}(\mathbf{Y})=\alpha\mu\circ\mathbf{s}$ and
$\mathbf{Y}\in\bigoplus_{h\in E}\mathbb{R}^{h}$ to the problem above.

We can then do binary search over the choice of $\alpha$ in the range
$[1/\mu(V),\sum_{h\in E}w_{h}]$, to find a value of $\alpha$ such that the
algorithms finds a cut $A$ such that:

$\Psi_{G,\mathbf{s}}(A)\leq 2\alpha^{*},$

and a hypergraph flow $\mathbf{Y}\in\bigoplus_{h\in E}\mathbb{R}^{h}$ such
that:

$\left(1-{\epsilon\over
8}\right){\alpha^{*}}\cdot(\bm{\mu}\circ\mathbf{s})\leq\operatorname{dem}(\mathbf{Y})\leq\alpha^{*}(\bm{\mu}\circ\mathbf{s}),$

so that $\mathbf{Y}$ and $A$ make up an $\epsilon$-approximate primal-dual
solution. Since the range of possible values for $\alpha$ is
$[1/\mu(V),\sum_{h\in E}w_{h}]$, we can get the above guarantees by running
the above algorithms at most:

$\mathcal{O}(\log|V|+\log\mu(V)+\max_{h}\log w_{h})$

times.

####  B.3.2 A Fast Algorithm for the Standard Cut Function

In this subsection, we focus on finding an $\epsilon$-approximate primal-dual
solution for the case in which the cut function chosen is the standard
hypergraph cut function, i.e. $\delta_{h}=\delta_{h}^{\mathsf{cut}}$ for all
$h\in E$. We will do this by constructing a (2-uniform) flow graph
$G_{\mathsf{flow}}$ and running on it an approximate maximum flow algorithm,
and then turning the output of this algorithm into an $\epsilon$-approximate
primal-dual solution for $(G,\mathbf{s})$.

$+1$$+1$$+1$$-1$$-2$$1$$1$$1$$1$$2$ Figure 2: The figure above shows the
interpretation of a vector $\mathbf{y}_{h}$ in the (CI-
Dual-$\alpha$-Feasibility) problem as a flow in a star graph. On the left
side, we drew a hyperedge $h$ of $G$ and the values of $\mathbf{y}_{h}(i)$ for
$i\in h$, and on the right side we draw its interpretation as a a flow through
a star graph which has replaced the hyperedge. Note how the amount of flow
entering the newly-introduced factor vertex equals the amount of flow exiting
it.

Under this assumption, consider the following feasibility problem parametrized
by $\alpha$ corresponding to (CI-Dual):

Find
$\displaystyle\mathbf{Y}=\\{\mathbf{y}_{h}\\}_{h\in\mathbb{R}^{h}}\in\bigoplus_{h\in
E}\mathbb{R}^{h}$ (CI-Dual-$\alpha$-Feasibility) s.t. $\displaystyle\sum_{h\in
E}\mathbf{y}_{h}\leq\alpha\cdot\big{(}\bm{\mu}\circ\mathbf{s}\big{)}$
$\displaystyle\mathbf{y}_{h}\in w_{h}\cdot\mathcal{B}(\delta_{h})$
$\displaystyle\forall\,h\in E$

We will produce an $\epsilon$-approximate primal-dual solution for
$(G,\mathbf{s})$ by finding an approximately feasible point
$\mathbf{Y}\in\bigoplus_{h\in E}\mathbb{R}^{h}$ for the above program for a
suitable choice of $\alpha$. In particular, $\mathbf{Y}$ will satisfy the last
constraint exactly and the first constraint approximately.

The problem asks one to find a vector $\mathbf{y}_{h}$ for each hyperedge of
$G$. The last constraint in the program enforces: $\mathbf{y}_{h}\in
w_{h}\cdot\mathcal{B}(\delta_{h}^{\mathsf{cut}})$. Following the definition of
$\delta_{h}^{\mathsf{cut}}$ and of the base polytope, it is easy to see that
the vectors $\mathbf{y}_{h}$ satisfying this constraint are those vectors such
that:

  1. 1.

$\sum_{i\in h}\mathbf{y}_{h}(i)=0$,

  2. 2.

and $\sum_{i\in h}|\mathbf{y}_{h}(i)|\leq 2\cdot w_{h}$.

This allows us to interpret each $\mathbf{y}_{h}(i)$ as an amount of flow that
is leaving vertex $i$ through hyperedge $h$, and the constraints ensure that
the total flow going through any hyperedge is not dissipated (item 2 above)
and is at most $w_{h}$ (item 3 above).

In this way, $\mathbf{Y}$ corresponds to a flow routed in the factor graph
$\hat{G}$ of $G$ (See Figure 2, and the Preliminaries Section discussion on
hypergraph flows). Under this interpretation, the first constraint in CI-
Dual-$\alpha$-Feasibility asks one to route a specific demand in the factor
graph, equal to $\alpha\cdot\bm{\mu}_{i}\cdot\mathbf{s}_{i}$ for every $i\in
V$, while the second constraint imposes flow conservation constraints and
vertex-capacity constraints on the factor vertices. We will actually not
enforce that the exact demand imposed by the first constraint is met, but
rather that we route a sufficiently high amount of demand to meet the
requirements of an $\epsilon$-approximate primal-dual solution. In this
setting, the above problem can be cast as a mixed edge-vertex capacitated
single-commodity maximum flow problem in a graph $G_{\mathsf{flow}}$ purpose-
built starting from the factor graph $\hat{G}$ to enforce the above
constraints.

Armed with this perspective, we now give an algorithm (Algorithm B.3.2 below)
which on input $(G,\mathbf{s})$, constructs a flow graph $G_{\mathsf{flow}}$
which can be used to find an $\epsilon$-approximate primal-dual solution
$(A,\mathbf{Y})$ for $(G,\mathbf{s})$ by applying the algorithm of Bernstein
et al. [12]

Algorithm 5 Flow Graph Construction Parameters: $\alpha>0$,
$G=(V,E,\mathbf{w},\bm{\mu})$, and $\mathbf{s}\in\mathbb{R}^{V}$ satisfying
$\langle\mathbf{s},\boldsymbol{1}\rangle_{\mu}=0$ and
$\lVert\mathbf{s}\rVert_{\infty}\leq 1$. Do: 1. Starting with
$G_{\mathsf{flow}}=\hat{G}=(V\cup E,\hat{E})$, construct a flow network as
follows (see Figure 3): • Add source vertex $s$, and sink vertex $t$
(Note the distinction between the source vertex $s$ and the seed vector
$\mathbf{s}$). • For each $i\in V$ s.t. $\mathbf{s}_{i}\geq 0$, add an edge
between $s$ and $i$ to $\hat{E}$ with capacity
$\alpha\bm{\mu}_{i}\cdot\cdot\mathbf{s}_{i}$.
(So that for any feasible flow
$\mathbf{f}\in\mathbb{R}^{E(G_{\mathsf{flow}})}$,
$|\mathbf{f}_{si}|<\alpha\cdot\bm{\mu}_{i}\cdot\mathbf{s}_{i}$). • For each
$j\in V$ s.t. $\mathbf{s}_{j}<0$, add an edge between $t$ and $j$ to $\hat{E}$
with capacity $\alpha\cdot\bm{\mu}_{j}\cdot\mathbf{s}_{j}$
(So that for any feasible flow
$\mathbf{f}\in\mathbb{R}^{E(G_{\mathsf{flow}})}$,
$|\mathbf{f}_{tj}|<\alpha\cdot\bm{\mu}_{j}\cdot\mathbf{s}_{j}$). • For each
factor vertex representing $h\in E$, enforce a vertex capacity constraint of
$w_{h}$. 2. Return $G_{\mathsf{flow}}$.

In order to solve the feasibility problem, Algorithm B.3.2 builds the
following flow network $G_{\mathsf{flow}}$. Starting from $\hat{G}=(V\cup
E,\hat{E})$ the factor graph representation of $G$, we add a vertex capacity
constraint of value ${w_{h}}$ on each factor vertex representing a hyperedge
$h\in E$. We then seek to use a single commodity flow to route multiple
demands placed on variable vertices $i\in V$ given by the vector
$\alpha\cdot\bm{\mu}\circ\mathbf{s}\in\mathbb{R}^{V}$. Routing this demand can
be done via standard flow reduction techniques which works as follows. Add a
source vertex $s$ and sink vertex $t$ to $G_{\mathsf{flow}}$. For every $i\in
V$ such that $\mathbf{s}_{i}\geq 0$, add an undirected edge $si$ with a
capacity constraint $\alpha\cdot\bm{\mu}_{i}\cdot\mathbf{s}_{i}$. For every
$j\in V$ such that $\mathbf{s}_{j}<0$, add an undirected edge $jt$ with a
capacity constraint of $\alpha\cdot\bm{\mu}_{j}\cdot\mathbf{s}_{j}$. Finally,
route a maximum flow from $s$ to $t$, and let $\mathbf{f}_{ih}$ to be the
amount of flow sent on each edge $ih\in\hat{E}$.

$G$$\hat{G}$$G_{\text{flow}}$$s$$t$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure
3: An illustration of the construction of the maximum flow instance
corresponding to (CI-Dual-$\alpha$-Feasibility). On the left is the original
hypergraph $G$. The middle of the figure shows the factor graph. The maximum
flow algorithm is run on the graph $G_{\mathsf{flow}}$ on the right. In this
graph only the dashed edges (in red) and the white (non-solid) vertices have
finite capacity constraints which depend on the values of
$\bm{\mu}_{i}\cdot\mathbf{s}_{i}$ and the values of $w_{h}$ respectively.
Here, we assume that we are given an $\mathbf{s}$ such that $\mathbf{s}_{1}>0$
and $\mathbf{s}_{2}>0$, but $\mathbf{s}_{3}<0$, $\mathbf{s}_{4}<0$ and
$\mathbf{s}_{5}<0$.

We note that, since we are enforcing vertex constraints, the algorithm
involves solving a mixed edge-vertex-capacitated version of the undirected
maximum flow problem, and that this version of the problem is solved by [12].

On input a mixed capacitated flow network $G_{\mathsf{flow}}$, we can use the
Algorithm of Bernestein et al. to route find a flow in the network of value
$(1-\epsilon)f$, as well as an s-t mixed vertex-edge cut of capacity at most
$(1+\epsilon)f$, where $f$ is the value of the maximum flow in
$G_{\mathsf{flow}}$. Note that for the case of the $G_{\mathsf{flow}}$
returned by Algorithm B.3.2, the mixed vertex-edges cut returned by the
algorithm must be comprised entirely of factor vertices (i.e. vertices that
arose from hyperedges in $G$) and edges connecting $V$ to $s$ or $t$, since
these are the only objects with finite capacity.

We argue now that obtaining a $(1-\epsilon)$-approximate solution of the kind
guaranteed by Bernstein et al. , suffices to return an $\epsilon$-approximate
primal-dual solution on input $(G,\mathbf{s})$.

Note that, when $G_{\mathsf{flow}}$ is constructed with a choice of $\alpha$
that is smaller than $\Psi_{G,\mathbf{s}}^{*}$, the value of the maximum flow
is $\alpha$ and the minimum cut is just given by $\\{\mathbf{s}\\}\subseteq
V(G^{\mathsf{flow}})$. On the other hand, when the value of $\alpha$ used to
construct $G^{\mathsf{flow}}$ is larger than $\Psi_{G,\mathbf{s}}^{*}$, the
value of the maximum flow is at returned by Bernstein et al. is at least
$(1-\epsilon)\alpha$.

Like we did in the previous section, we will perform binary search for a value
of $\alpha$ in the range $[1/\mu(V),\sum_{h\in E}w_{h}]$, to find a value of
$\alpha$ such that the algorithms finds a cut $A$ such that the algorithm
approximate maxflow algorithm routes at least
$(1-\epsilon)\eta\alpha\lVert\mathbf{s}\rVert_{1,\mu}$ units of flow in
$G_{\mathsf{flow}}$, and returns it together with a cut $T$ of a capacity:

$\operatorname{cap}(T)=(1+\epsilon)\eta\alpha{\lVert\mathbf{s}\rVert_{1,\mu}\over
2}$

for some choice of $\eta$ and some accuracy parameter $\epsilon$. We then have
the following:

######  Lemma 17.

In the setting described above, we have:

$\langle{\mathbf{s},{\bf
1}_{T}}\rangle_{\bm{\mu}}\geq{\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over
2}\left(1-(1+\epsilon)\eta\right).$

###### Proof.

We have:

$\displaystyle\alpha\left((\bm{\mu}\circ\mathbf{s})(S\cap\overline{T})-(\bm{\mu}\circ\mathbf{s})(\overline{S}\cap{T})\right)\leq{(1+\epsilon)\eta\alpha\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over
2},$

which gives:

$\left((\bm{\mu}\circ\mathbf{s})(S\cap\overline{T})-(\bm{\mu}\circ\mathbf{s})(\overline{S}\cap{T})\right)\leq{(1+\epsilon)\eta\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over
2},$

which in turn implies:

${\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over 2}-(\bm{\mu}\circ\mathbf{s})(S\cap
T)-(\bm{\mu}\circ\mathbf{s})(\overline{S}\cap{T})\leq{(1+\epsilon)\eta\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over
2}.$

From the above, we obtain:

$\lVert\mathbf{s}\rVert_{1,\bm{\mu}}-\langle{\mathbf{s},{\bf
1}_{T}}\rangle_{\bm{\mu}}\leq(1+\epsilon)\eta\lVert\mathbf{s}\rVert_{1,\bm{\mu}},$

yielding the wanted result. ∎

Lemma 17 implies that:

$\displaystyle\Psi_{G}(T\cap V)\leq{\sum_{h\in
E}w_{h}\delta_{h}^{\mathsf{cut}}(T\cap V)\over|\langle{\mathbf{s},{\bf
1}_{T}}\rangle_{\bm{\mu}}|}\leq{\operatorname{cap}(T)\over|\langle{\mathbf{s},{\bf
1}_{T}}\rangle_{\bm{\mu}}|}\leq{(1+\epsilon)\eta\alpha\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over|\langle{\mathbf{s},{\bf
1}_{T}}\rangle_{\bm{\mu}}|}\leq{(1+\epsilon)\eta\alpha\lVert\mathbf{s}\rVert_{1,\bm{\mu}}\over{\lVert\mathbf{s}\rVert_{1,\bm{\mu}}}\left(1-(1+\epsilon)\eta\right)}\leq
2\alpha.$

for small enough values of $\eta$ and $\epsilon$. This in particular
guarantees that flow and cut pair $(\mathbf{Y},T\cap V)$ built by taking the
output of the algorithm of Bernstein et al. on $G^{\mathsf{flow}}$, and
restricting it to $G$ is a valid $\epsilon$-approximate primal-dual response.

##  Appendix C An $O(\log n)$-Approximation via Generalized Cut-Matching Games

In this section, we include additional details from our construction of an
$O(\log n)$-approximation algorithm for minimum ratio-cut based on the
generalized cut-matching game.

###  C.1 Updating the vector embedding via mirror descent

We now describe the operation of Mirror Descent in the context of online
linear optimization over the set of density matrices [26]. Using known
performance guarantees, we then prove Lemmata 7 and 8 as stated in Section
5.2.2.

Let $\Delta_{n\times
n}=\\{\mathbf{X}\succeq\mathbf{0}:\operatorname*{\textup{tr}}\mathbf{X}=1\\}$
be the set of $n\times n$ density matrices. Online linear optimization
considers the following game played over $T$ rounds. In each round $t$, a
player plays a single action $\mathbf{X}_{t}\in\Delta_{n\times n}$, receives a
feedback matrix $\mathbf{F}\in\Delta_{n\times n}$, and incurs a loss of
$\langle\mathbf{X}_{t},\mathbf{F}_{t}\rangle$. The regret minimization problem
asks for a sequence of actions which minimize the regret: the difference
between total loss incurred by the player, and the loss suffered by the best
fixed action $\mathbf{U}\in\Delta_{n\times n}$ in hindsight:

$\min_{\mathbf{X}_{1},\ldots,\mathbf{X}_{T}\in\Delta_{n\times
n}}\,\max_{\mathbf{U}\in\Delta_{n\times
n}}\bigg{\\{}\sum_{t=1}^{T}\langle\mathbf{X}_{t},\mathbf{F}_{t}\rangle-\sum_{t=1}^{T}\langle\mathbf{U},\mathbf{F}_{t}\rangle\bigg{\\}}.$

A standard approach towards minimizing regret is to use Mirror Descent. This
corresponds setting

$\mathbf{X}_{t+1}=\operatorname*{\arg\\!\min}_{\mathbf{X}\in\Delta_{n\times
n}}\Big{\\{}D_{\psi}(\mathbf{X},\mathbf{X}_{t})+\eta\cdot\langle\mathbf{X},\mathbf{F}_{t}\rangle\Big{\\}}.$

where $\psi:\Delta_{n\times n}\rightarrow\mathbb{R}$ is a regularization
function, that is to be specified, and $D_{\psi}(\cdot,\cdot)$ is the Bregman
Divergence associated with $\psi$.

$D_{\psi}(\mathbf{Z},\mathbf{X})\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\psi(\mathbf{Z})-\big{(}\psi(\mathbf{X})+\langle\nabla\psi(\mathbf{X}),\mathbf{Z}-\mathbf{X}\rangle\big{)}\,.$

When $\psi$ is taken to be the Von Neumann entropy, i.e.
$(\mathbf{X})=-\langle\mathbf{X},\log\mathbf{X}\rangle$, $\mathbf{X}_{t+1}$
becomes the following.

$\mathbf{X}_{t+1}=\frac{\exp\big{(}-\eta\sum_{k=1}^{t}\mathbf{F}_{k}\big{)}}{\operatorname*{\textup{tr}}\exp\big{(}-\eta\sum_{k=1}^{t}\mathbf{F}_{k}\big{)}},$

This choice of update is also known as the Matrix Multiplicative Weight Update
[6], and enjoys the following regret guarantee.

######  Theorem 14 (Theorem 3.1 from [3]).

Suppose $\mathbf{X}_{1},\ldots,\mathbf{X}_{T}\in\Delta_{n\times n}$ are
matrices output by update-embedding using the Von Neumann entropy regularizer,
and $\mathbf{F}_{1},\ldots,\mathbf{F}_{T}$ is a sequence of losses such that:

$\mathbf{F}_{t}\succeq-\frac{1}{\eta}\cdot\mathbf{I}_{n}$

for all $t\in[T]$. Then, for any $\mathbf{U}\in\Delta_{n\times n}$, we have:

$\frac{1}{T}\sum_{t=1}^{T}\langle\mathbf{F}_{t},\mathbf{U}\rangle\geq\frac{1}{T}\sum_{t=1}^{T}\langle\mathbf{F}_{t},\mathbf{X}_{t}\rangle-\frac{\eta}{T}\sum_{t=1}^{T}\langle\lvert\mathbf{F}_{t}\rvert,\mathbf{X}_{t}\rangle\cdot\lVert\mathbf{F}_{t}\rVert_{\mathsf{spec}}-\frac{\log
n}{\eta T}$

where if
$\mathbf{F}_{t}=\sum_{i=1}^{n}\lambda_{i}\cdot\mathbf{v}_{i}\mathbf{v}_{i}^{\top}$,
then
$\lvert\mathbf{F}_{t}\rvert=\sum_{i=1}^{n}\lvert\lambda_{i}\rvert\cdot\mathbf{v}_{i}\mathbf{v}_{i}^{\top}$.

Using this regret guarantee, we can now prove Lemma 7.

###### Proof of Lemma 7.

Using the regret bound in Theorem 14 with feedback matrices
$\mathbf{F}_{t}=\mathcal{L}_{\bm{\mu}}(D_{t})$, we have

$\frac{1}{T}\sum_{t=1}^{T}\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{U}\rangle\geq\frac{1}{T}\sum_{t=1}^{T}\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle-\frac{\eta}{T}\sum_{t=1}^{T}\langle\lvert\mathcal{L}_{\bm{\mu}}(D_{t})\rvert,\mathbf{X}_{t}\rangle\cdot\lVert\mathcal{L}_{\bm{\mu}}(D_{t})\rVert_{\mathsf{spec}}-\frac{\log
n}{\eta T}$

Since $D_{t}$ is an $\epsilon$-approximate matching action, we have that
$D_{t}$ is at most $\bm{\mu}\circ\lvert\mathbf{s}\rvert$-regular. Since
$\lVert\mathbf{s}\rVert_{\infty}\leq 1$, we have that $D_{t}$ is at most
$\bm{\mu}$-regular and hence
$\mathbf{0}\preceq\mathcal{L}_{\bm{\mu}}(D_{t})\preceq 2\cdot\mathbf{I}$. Our
regret bound reduces to:

$\frac{1}{T}\sum_{t=1}^{T}\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{U}\rangle\geq\frac{1-2\eta}{T}\sum_{t=1}^{T}\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle-\frac{\log
n}{\eta T}\,.$

holding for every $\mathbf{U}\in\Delta_{n\times n}$, and $\eta>0$. Now take
$H_{T}=\frac{1}{T}\sum_{t=1}^{T}D_{t}$. We have

$\big{\langle}\mathcal{L}_{\bm{\mu}}(H_{T}),\mathbf{U}\big{\rangle}=\bigg{\langle}\frac{1}{T}\sum_{t=0}^{T}\mathcal{L}_{\bm{\mu}}(D_{t}),\,\mathbf{U}\bigg{\rangle}=\frac{1}{T}\sum_{t=0}^{T}\big{\langle}\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{U}\big{\rangle}\geq\frac{1-2\eta}{T}\sum_{t=1}^{T}\big{\langle}\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\big{\rangle}-\frac{\log
n}{T\eta}\,.$

Choosing $\mathbf{U}=\mathbf{u}\mathbf{u}^{\top}$ where $\mathbf{u}$ is the
normalized eigenvector of $\mathcal{L}_{\bm{\mu}}(H_{t})$ corresponding to
$\lambda_{2}\big{(}\mathcal{L}_{\bm{\mu}}(H_{t})\big{)}$ gives the desired
bound. ∎

Let us now prove the properties required by Lemma 8 regarding the vector
embedding $\big{\\{}\mathbf{v}^{(t)}_{i}\big{\\}}_{i\in V}$ associated with
the matrix $\mathbf{X}_{t}$ generated by update-embedding.

###### Proof of Lemma 8.

Let $\mathbf{X}_{t}=\mathbf{V}_{t}\mathbf{V}_{t}^{\top}$ where the $i$-th row
of $\mathbf{V}\in\mathbb{R}^{n\times n}$ is given by $\mathbf{v}_{i}$. To see
item (1), observe that $\mathbf{X}_{t}\in\Delta_{n\times n}$ implies
$\operatorname*{\textup{tr}}\mathbf{X}_{t}=1$ and hence

$\sum_{i\in
V}\lVert\mathbf{v}_{i}\rVert_{2}^{2}=\operatorname*{\textup{tr}}\mathbf{V}_{t}\mathbf{V}_{t}^{\top}=\operatorname*{\textup{tr}}\mathbf{X}_{t}=1$

To see item (2), observe that

$\bigg{\lVert}\sum_{i\in
V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i}\bigg{\rVert}_{2}^{2}=\bigg{\langle}\sum_{i\in
V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i},\,\sum_{i\in
V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i}\bigg{\rangle}=\sum_{i,j\in
V}\sqrt{\mu_{i}\mu_{j}}\cdot\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle=\langle\mathbf{X}_{t},\bar{\bm{\mu}}\bar{\bm{\mu}}^{\top}\rangle$

where $\bar{\bm{\mu}}_{i}=\sqrt{\mu_{i}}$. Now, since
$\bar{\bm{\mu}}\in\operatorname*{\textup{kern}}\mathcal{L}_{\bm{\mu}}(D_{t})$
for every $t$, we have that
$\bar{\bm{\mu}}\in\operatorname*{\textup{kern}}\mathbf{X}_{t}$ as well.
Consequently,

$\langle\mathbf{X}_{t},\bar{\bm{\mu}}\bar{\bm{\mu}}^{\top}\rangle=0$

and since $\big{\lVert}\sum_{i\in
V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i}\big{\rVert}_{2}^{2}=0$, we can conclude
$\sum_{i\in V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i}={\bf 0}$ as required. ∎

###  C.2 Rounding a robustly separated set

We now complete the argument that round-cut outputs a robustly separated set
when the given vector embedding is balanced. We begin by recalling a fact
about uniformly sampled vectors on the sphere.

######  Lemma 18.

Given $\mathbf{v}\in\mathbb{R}^{d}$, and $\mathbf{g}$ a uniformly sampled
random vector in $\mathcal{S}^{d-1}$, the following hold.

  1. 1.

$\operatorname*{\mathbb{E}}_{\mathbf{g}}\langle\mathbf{g},\mathbf{v}\rangle^{2}=\frac{\lVert\mathbf{v}\rVert^{2}}{d}$

  2. 2.

For any $\delta>\frac{d}{16}$, we have
$\Pr_{\mathbf{g}}\Big{(}\langle\mathbf{g},\mathbf{v}\rangle^{2}\geq\delta\cdot\frac{\lVert\mathbf{v}\rVert^{2}}{d}\Big{)}\leq
e^{-\delta/4}$.

We also require a lemma proved in [45] which states that, with constant
probability, one can extract two balanced partitions where projection lengths
are well separated when projecting along a random direction.

######  Lemma 19 (Lemma 5.5.6 item (3) of [45]).

Given a set $V$ such that $\lvert V\rvert=n$, and a
$\big{(}3,\frac{1}{10}\big{)}$-balanced embedding $\\{\mathbf{v}_{i}\\}_{i\in
V}\subseteq\mathbb{R}^{d}$, let
$r_{i}=\sqrt{d}\cdot\langle\mathbf{g},\mathbf{v}_{i}\rangle$ for a
$\mathbf{g}\in\mathcal{S}^{d-1}$ and each $i\in V$. Assume, without loss of
generality, that $r_{1}\geq\ldots\geq r_{n}$. Then, there exists an absolute
constant $r>0$ such that, with $O(1)$ probability over a uniformly random
choice of $\mathbf{g}\in\mathcal{S}^{d-1}$, there exists $1\leq a<b\leq n$
satisfying the following:

  1. 1.

$\bm{\mu}(\\{1,\ldots,a\\})\geq\frac{1}{3}\cdot\bm{\mu}(V)$,

  2. 2.

$\bm{\mu}(\\{b,\ldots,n\\})\geq\frac{1}{3}\cdot\bm{\mu}(V)$,

  3. 3.

$\big{(}r_{a}-r_{b}\big{)}^{2}\geq
r\cdot\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})$.555We note that in [45],
the variance of the vector embedding is normalized to be 1, and hidden in the
$\Omega_{b}(1)$ term.

Using the above two lemmata, we can now prove that round-cut produces a
robustly separated set in the balanced case.

###### Proof of Lemma 9.

Define $\mathcal{E}_{1}$ to be the event where there exists $1\leq a<b\leq n$
such that the following hold simultaneously: (1)
$\bm{\mu}(\\{1,\ldots,a\\})\geq\frac{1}{3}\cdot\bm{\mu}(V)$, (2)
$\bm{\mu}(\\{b,\ldots,n\\})\geq\frac{1}{3}\cdot\bm{\mu}(V)$, and (3)
$(r_{a}-r_{b})^{2}\geq\frac{r}{\bm{\mu}(V)}$. Next, for a constant $c_{1}>0$
to be chosen subsequently, and any $i,j\in V$, define the event
$\mathcal{E}_{2}(i,j)$ as

$\mathcal{E}_{2}(i,j)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\Big{\\{}(r_{i}-r_{j})^{2}<\big{(}4c_{1}\cdot\log
n\big{)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\Big{\\}}\qquad\textup{and}\qquad\mathcal{E}_{2}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\bigcap_{i,j\in V}\mathcal{E}_{2}(i,j).$

To begin, we observe that if $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ occur
jointly, then choosing the sweep cut $S=\\{1,\ldots,a\\}$ gives an
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated set with $T=\\{b,\ldots,n\\}$, and, consequently, executing step (1)
of round-cut outputs a robustly separated set in the balanced case.

The first requirement in demonstrating $S$ is a robustly separated is
immediately satisfied by item (2) defining event $\mathcal{E}_{1}$ since
$\bm{\mu}(T)\geq\frac{1}{3}\cdot\bm{\mu}(V)$. For the second requirement,
event $\mathcal{E}_{2}$ implies that

$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}>\frac{(r_{i}-r_{j})^{2}}{4c_{1}\cdot\log
n}$

holds for all $i\in S$, and $j\in T$. Item (3) defining event
$\mathcal{E}_{1}$ then determines:

$\frac{(r_{i}-r_{j})^{2}}{4c_{1}\cdot\log n}\geq
r\cdot\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})\cdot\frac{1}{4c_{1}\cdot\log
n}=\frac{r}{\bm{\mu}(V)}\cdot\frac{1}{4c_{1}\cdot\log n}\,.$

Finally, item (1) in event $\mathcal{E}_{1}$ implies that
$\frac{1}{\bm{\mu}(V)}\geq\frac{1}{3\bm{\mu}(S)}$ and hence:

$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\frac{r}{\bm{\mu}(V)}\cdot\frac{1}{4c_{1}\cdot\log
n}\geq\frac{1}{\bm{\mu}(S)}\cdot\frac{r}{12c_{1}\cdot\log
n}=\frac{1}{\bm{\mu}(S)}\cdot\Omega\bigg{(}\frac{1}{\log n}.\bigg{)}$

Let us next bound the probability that $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$
occur jointly. By Lemma 19, there exists a constant $p>0$ such that
$\Pr_{\mathbf{g}}(\mathcal{E}_{1})=p$ and hence
$\Pr_{\mathbf{g}}\big{(}\overline{\mathcal{E}_{1}}\big{)}=1-p$. By Lemma 18,
we have

$\displaystyle\Pr_{\mathbf{g}}\big{(}\overline{\mathcal{E}_{2}(i,j)}\big{)}$
$\displaystyle=\Pr_{\mathbf{g}}\Big{(}(r_{i}-r_{j})^{2}\geq\big{(}4c_{1}\cdot\log
n\big{)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\Big{)}$
$\displaystyle=\Pr_{\mathbf{g}}\bigg{(}\langle\mathbf{g},\mathbf{v}_{i}-\mathbf{v}_{j}\rangle^{2}\geq\big{(}4c_{1}\cdot\log
n\big{)}\cdot\frac{\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}}{d}\bigg{)}\leq\frac{1}{n^{c_{1}}}$

Performing a union bound over $\overline{\mathcal{E}_{1}}$ and
$\overline{\mathcal{E}_{2}(i,j)}$ for each $i,j\in V$ derives

$\Pr_{\mathbf{g}}\big{(}\mathcal{E}_{1}\cap\mathcal{E}_{2}\big{)}\geq
p-\binom{n}{2}\frac{1}{n^{c_{1}}}\geq p-\frac{1}{n^{c_{1}-2}}=\Omega(1)$

for $c_{1}$ large enough. We conclude that with constant probability, a single
execution of step (1) in round-cut outputs a
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated set. Repeating step (1) $O(\log n)$ times and performing another
union bound then allows us to conclude round-cut produces a robustly separated
set with probability $1-o_{n}\big{(}\frac{1}{n}\big{)}$. ∎

##  Appendix D An $O\big{(}\sqrt{\log n}\big{)}$-Approximation via Metric
Embeddings

In this section, we prove the technical results used in to obtain the
$O(\sqrt{\log n})$-approximation algorithm in Theorem 4. To begin, we complete
the proof that the vector program (RC-Metric) is, up to a factor of 2, a
relaxation of the original problem.

###### Proof of Theorem 11.

Given any cut $(S,\overline{S})$ with $\mu(S)\leq\mu(\overline{S})$, for each
$i\in V$, set the vector embedding of the vertices to

$\mathbf{v}_{i}=\begin{cases}\begin{pmatrix}\sqrt{\frac{\mu(V)}{\mu(S)\mu(\bar{S})}}&0&\ldots&0\end{pmatrix}^{\top}&\mbox{if
}i\in S\\\ {\bf 0}&\mbox{otherwise.}\end{cases}$

Assign the length vectors as follows:

$\bm{\ell}^{h}=\frac{\mu(V)}{\mu(S)\mu(\bar{S})}\cdot\begin{cases}{\bf
1}^{S\cap h}&\text{if }F_{h}(S\cap h)\leq F_{h}(\bar{S}\cap h),\\\ {\bf
1}^{\bar{S}\cap h}&\text{otherwise.}\end{cases}$

Then, $(\\{\bm{\ell}^{h}\\}_{h\in E},\\{\mathbf{v}_{i}\\}_{i\in V})$ is a
feasible solution to the vector program as, for $i\in S\cap h$ and
$j\in\bar{S}\cap h$:

$\|\mathbf{v}_{i}-\mathbf{v}_{j}\|^{2}=\frac{\mu(V)}{\mu(S)\mu(\bar{S})}=\bm{\ell}^{h}_{i}+\bm{\ell}^{h}_{j}.$

Furthermore, this solution has objective value:

$\sum_{h\in
E}w_{h}\|\bm{\ell}_{h}\|_{F}=\frac{\mu(V)}{\mu(S)\mu(\bar{S})}\cdot\sum_{h\in
E}w_{h}\min\\{\|{\bf 1}^{S\cap h}\|_{F},\|{\bf 1}^{\bar{S}\cap h}\|_{F}\\}\leq
2\cdot\frac{\sum_{h\in E}w_{h}\delta_{h}(S\cap
h)}{\min\\{\mu(S),\mu(\bar{S})\\}}=2\Psi_{G}(S).$

∎

We now prove the technical Lemma 14 required by our rounding argument.

###### Proof of Lemma 14.

Let $Y=\operatorname{diag}(\mathbf{y})$, then the above statement is
equivalent to proving that there exists some $\nu\in\mathbb{R}$ such that:

$\min_{\nu\in\mathbb{R}}\|Y^{-1}(\mathbf{x}-\nu 1)\|_{\infty}\leq 1.$

We have:

$\displaystyle\min_{\nu\in\mathbb{R}}\|Y^{-1}(\mathbf{x}-\nu 1)\|_{\infty}$
$\displaystyle=\min_{\nu\in\mathbb{R}}\max_{\|\mathbf{z}\|_{1}\leq
1}\langle\mathbf{z},Y^{-1}(\mathbf{x}-\nu
1)\rangle=\min_{\nu\in\mathbb{R}}\max_{\|Y\mathbf{z}\|_{1}\leq
1}\langle\mathbf{z},\mathbf{x}-\nu 1\rangle=\max_{\|Y\mathbf{z}\|_{1}\leq
1}\min_{\nu\in\mathbb{R}}\langle\mathbf{z},\mathbf{x}-\nu 1\rangle$
$\displaystyle=\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq 1\\\
\mathbf{z}\perp 1\end{subarray}}\langle\mathbf{z},\mathbf{x}\rangle.$

For any $\mathbf{z}$, let
$Z^{+}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\\{i:z_{i}>0\\}$ and
$Z^{-}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\\{i:z_{i}<0\\}$. The above orthogonality constraint, implies:

$-\sum_{i\in Z^{-}}z_{i}=\sum_{i\in Z^{+}}z_{i},$

so that the positive entries of $\mathbf{z}$ can be charged to the negative
entries of $\mathbf{z}$, i.e. there exists some choice of non-negative numbers
$\\{w_{i,j}\\}_{(i,j)\in Z^{+}\times Z^{-}}$ such that:

$\forall i\in Z^{-}:\sum_{j\in Z^{+}}w_{i,j}=|z_{i}|\hskip 14.22636pt\text{
and }\hskip 14.22636pt\forall j\in Z^{+}:\sum_{i\in Z^{-}}w_{i,j}=|z_{j}|.$

This gives:

$\displaystyle\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq 1\\\
\mathbf{z}\perp 1\end{subarray}}\langle\mathbf{z},\mathbf{x}\rangle$
$\displaystyle=\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq 1\\\
\mathbf{z}\perp 1\end{subarray}}\bigg{\\{}\sum_{i\in
Z^{+}}|z_{i}|x_{i}-\sum_{j\in
Z^{-}}|z_{j}|x_{j}\bigg{\\}}=\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq
1\\\ \mathbf{z}\perp 1\end{subarray}}\bigg{\\{}\sum_{i\in Z^{+}}\sum_{j\in
Z^{-}}w_{i,j}x_{i}-\sum_{j\in Z^{-}}\sum_{i\in Z^{+}}w_{i,j}x_{j}\bigg{\\}}$
$\displaystyle=\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq 1\\\
\mathbf{z}\perp 1\end{subarray}}\bigg{\\{}\sum_{(i,j)\in Z^{+}\times
Z^{-}}w_{i,j}(x_{i}-x_{j})\bigg{\\}}\leq\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq
1\\\ \mathbf{z}\perp 1\end{subarray}}\bigg{\\{}\sum_{(i,j)\in Z^{+}\times
Z^{-}}w_{i,j}|x_{i}-x_{j}|\bigg{\\}}$
$\displaystyle\leq\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq 1\\\
\mathbf{z}\perp 1\end{subarray}}\bigg{\\{}\sum_{(i,j)\in Z^{+}\times
Z^{-}}w_{i,j}(y_{i}+y_{j})\bigg{\\}}=\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq
1\\\ \mathbf{z}\perp 1\end{subarray}}\bigg{\\{}\sum_{i\in
Z^{+}}|z_{i}|y_{i}+\sum_{j\in Z^{-}}|z_{j}|y_{j}\bigg{\\}}$
$\displaystyle\leq\max_{\begin{subarray}{c}\|Y\mathbf{z}\|_{1}\leq 1\\\
\mathbf{z}\perp 1\end{subarray}}\|Y\mathbf{z}\|_{1}\leq 1,$

which yields the desired result. ∎


# Chain conditions for rings with enough idempotents with applications to
category graded rings

Patrik Lundström  University West, Department of Engineering Science, SE-46186
Trollhättan, Sweden<EMAIL_ADDRESS>
###### Abstract.

We obtain criteria for when a ring with enough idempotents is left/right
artinian or noetherian in terms of local criteria defined by the associated
complete set of idempotents for the ring. We apply these criteria to object
unital category graded rings in general and, in particular, to the class of
skew category algebras. Thereby, we generalize results by Nastasescu-van
Oystaeyen, Bell, Park and Zelmanov from the group graded case to groupoid, and
in some cases category, gradings.

###### 2010 Mathematics Subject Classification:

16W50, 16S35,20L05

##  1\. Introduction

Throughout this article all rings are associative but not necessarily unital.
If a ring $S$ is unital, then we always assume that $S$ is nonzero and that
$1_{S}$ denotes the multiplicative unit of $S$. Recall that a ring is called
left/right _artinian (noetherian)_ if it satisfies the the descending
(ascending) chain condition on its poset of left/right ideals. The main
purpose of the present article is to establish criteria for artiniarity and
noetherianity for rings with enough idempotents (see Theorem 1). The secondary
purpose is to apply this result to the setting of category graded rings and
thereby obtaining similar results for this class of rings (see Theorems 2-4).

Here is an outline of the article. In Section 2, we analyze chain conditions
for the class of rings with enough idempotents, introduced by Fuller in [4]
(see Definition 6). To this end, we consider of rings with complete sets of
idempotents $\\{e_{i}\\}_{i\in I}$ which are, what we call, _strong_ (see
Definition 10). By this we mean that for all $i,j\in I$ with $e_{i}Se_{j}$
nonzero or $e_{j}Se_{i}$ nonzero, then $e_{i}\in e_{i}Se_{j}Se_{i}$ and
$e_{j}\in e_{j}Se_{i}Se_{j}$. We establish the following:

######  Theorem 1.

Suppose $S$ is a ring with enough idempotents and let $\\{e_{i}\\}_{i\in I}$
be a complete set of idempotents for $S$.

  1. (1)

If $S$ is left/right artinian (noetherian), then $I$ is finite and for every
$i\in I$ the ring $e_{i}Se_{i}$ is left/right artinian (noetherian).

  2. (2)

Suppose $\\{e_{i}\\}_{i\in I}$ is strong. Then $S$ is left/right artinian
(noetherian) if and only if $I$ is finite and for every $i\in I$ the ring
$e_{i}Se_{i}$ is left/right artinian (noetherian).

In Section 3, we state our conventions on categories and groupoids (see
Definition 13). We also introduce the class of _hom-set strong_ categories
(see Definition 15). This is a class of categories which strictly contains the
class of groupoids (see Example 17).

In Section 4, we consider the class of object unital category (and groupoid)
graded rings (for our conventions on graded rings, see Definition 19). We use
Theorem 1 and results from the group graded case by Nastasescu-van Oystaeyen
[10] (see Theorem 25) and Bell [1] (see Theorem 27), to establish the
following:

######  Theorem 2.

Suppose $G$ is a groupoid and let $S$ be a ring which is strongly $G$-graded
and object unital.

  1. (1)

Let $G$ be torsion-free. Then $S$ is left/right artinian if and only if
$G_{0}$ is finite and for every $a\in G_{0}$ the ring $S_{a}$ is left/right
artinian and $S_{G(a)}$ is finitely generated as a left/right $S_{a}$-module.

  2. (2)

Let $G$ be polycyclic-by-finite. Then $S$ is left/right noetherian if and only
if $G_{0}$ is finite and for every $a\in G_{0}$ the ring $S_{a}$ is left/right
noetherian.

For the definitions of the classes of torsion-free and polycyclic-by-finite
groupoids, see Definitions 24 and 26.

In Section 5, we analyse chain conditions for skew category algebras which are
defined by skew category systems of unital rings (see Definition 28). Using a
result by Park [13] (see Theorem 32) from the setting of skew group rings, and
the results established in Section 4, we prove the following:

######  Theorem 3.

Suppose $G$ is a groupoid and let $\alpha=\\{\alpha_{g}:R_{d(g)}\to
R_{c(g)}\\}_{g\in G_{1}}$ be a skew category system of unital rings. Then the
associated skew category algebra $R*_{\alpha}G$ is left/right artinian if and
only if $G$ is finite and for for every $a\in G_{0}$ the ring $R_{a}$ is is
left/right artinian.

Note that Theorem 3 already was obtained in [12] using a different method. In
Section 5, we also show the following theorem, using a result by Zelmanov [15]
(see Theorem 33) and the results in Section 4.

######  Theorem 4.

Suppose $G$ is a hom-set strong category and let $T$ be a unital ring. Then
the associated category ring $T[G]$ is left/right artinian if and only if $T$
is left/right artinian and $G$ is finite.

Theorems 2-4 generalize classical results from the group graded case to the
groupoid (and in the case of the last theorem category) graded situation.

##  2\. Rings with enough idempotents

In this section, we analyze chain conditions for the class of rings with
enough idempotents. To this end, we introduce the class of rings with complete
sets of idempotents which are, what we call, _strong_. At the end of this
section, we prove Theorem 1. Throughout this article, we put
$\mathbb{N}:=\\{1,2,3,\ldots\\}$. For the rest of the section, $R$ and $S$
denote rings. For the convenience of the reader, we first gather some well
known results that we will use later.

######  Proposition 5.

The following assertions hold.

  1. (1)

Suppose $M$ is a left/right $S$-module and let $R\subseteq S$. If $M$ is
artinian (noetherian) as a left/right $R$-module, then $M$ is artinian
(noetherian) as a left/right $S$-module.

  2. (2)

Suppose $R$ is a direct summand of the left/right $R$-module $S$. Then, for
any right/left ideal $I$ of $R$, the equality $IS\cap R=IR$ (or $SI\cap R=RI$)
holds. In particular, if $S$ is right/left artinian (noetherian) and $R$ is
unital, then $R$ is right/left artinian (noetherian).

  3. (3)

Suppose $n\in\mathbb{N}$ and let $R_{1},\ldots,R_{n}$ be rings. Then
$R_{1}\times\cdots\times R_{n}$ is left/right artinian (noetherian) if and
only if all of the rings $R_{1},\ldots,R_{n}$ are left/right artinian
(noetherian).

  4. (4)

Suppose $R$ is unital and let $M$ be a left (right) $R$-module. Let
$n\in\mathbb{N}$ and suppose $M_{1},\ldots,M_{n}$ are left/right
$R$-submodules of $M$ such that $M=M_{1}\oplus\cdots\oplus M_{n}$. Then $M$ is
left/right artinian (noetherian) if and only if all of the modules
$M_{1},\ldots,M_{n}$ are left/right artinian (noetherian).

###### Proof.

See a standard book on the theory of rings and modules e.g. [14]. ∎

######  Definition 6.

Recall from [4] that $S$ is said to have _enough idempotents_ if there exists
a set $\\{e_{i}\\}_{i\in I}$ of nonzero orthogonal idempotents in $S$, called
a _complete set of idempotents_ for $S$, such that $S=\oplus_{i\in
I}Se_{i}=\oplus_{i\in I}e_{i}S$. For the rest of this section, $S$ denotes a
ring with enough idempotents where $\\{e_{i}\\}_{i\in I}$ is a fixed complete
set of idempotents for $S$. Given $i,j\in I$, we use the notation
$S_{ij}:=e_{i}Se_{j}$ and $S_{i}:=S_{ii}$. We also put $S_{0}:=\oplus_{i\in
I}S_{i}$.

######  Proposition 7.

If $S$ is left/right artinian (noetherian), then $I$ is finite.

###### Proof.

Suppose $I$ is infinite. Then we may assume that $\mathbb{N}\subseteq I$.

Define a set of left ideals $\\{I_{i}\\}_{i\in\mathbb{N}}$ of $S$ by
$I_{i}=Se_{i}+Se_{i+1}+Se_{i+2}+\cdots$ for $i\in\mathbb{N}$. Then $e_{i}\in
I_{i}\setminus I_{i+1}$ and thus $I_{i}\supsetneq I_{i+1}$ for all
$i\in\mathbb{N}$. Therefore $S$ is not left artinian.

Define a set of right ideals $\\{J_{i}\\}_{i\in\mathbb{N}}$ of $S$ by
$J_{i}=e_{i}S+e_{i+1}S+e_{i+2}S+\cdots$ for $i\in\mathbb{N}$. Then $e_{i}\in
J_{i}\setminus J_{i+1}$ and thus $J_{i}\supsetneq J_{i+1}$ for all
$i\in\mathbb{N}$. Therefore $S$ is not right artinian.

Define a set of left ideals $\\{K_{i}\\}_{i\in\mathbb{N}}$ of $S$ by
$K_{i}=Se_{1}+Se_{2}+\cdots+Se_{i}$ for $i\in\mathbb{N}$. Then $e_{i+1}\in
K_{i+1}\setminus K_{i}$ and thus $K_{i}\subsetneq K_{i+1}$ for all
$i\in\mathbb{N}$. Therefore $S$ is not left noetherian.

Define a set of right ideals $\\{L_{i}\\}_{i\in\mathbb{N}}$ of $S$ by
$L_{i}=e_{1}S+e_{2}S+\cdots+e_{i}S$ for $i\in\mathbb{N}$. Then $e_{i+1}\in
L_{i+1}\setminus L_{i}$ and thus $L_{i}\subsetneq L_{i+1}$ for all
$i\in\mathbb{N}$. Therefore $S$ is not right noetherian. ∎

######  Proposition 8.

Suppose $S$ is left/right artinian (noetherian) and $i\in I$. Then the ring
$S_{i}$ is left/right artinian (noetherian).

###### Proof.

From Proposition 7 it follows that $S_{0}$ is unital with
$1_{S_{0}}=\sum_{j\in I}e_{j}$. Since $S_{0}$ is a direct summand of $S$ as a
right/left $S_{0}$-module it follows from Proposition 5(2) that $S_{0}$ is
left/right artinian (noetherian). By Proposition 5(3) the ring $S_{i}$ is
left/right artinian (noetherian). ∎

######  Proposition 9.

Given $S$ and $\\{e_{i}\\}_{i\in I}$ the following properties are equivalent:

  1. (1)

$\forall(i,j,k)\in I\times I\times I$ if two of the additive groups $S_{ij}$,
$S_{jk}$ and $S_{ik}$ are nonzero, then the third one is also nonzero and
$S_{ij}S_{jk}=S_{ik}$;

  2. (2)

$\forall(p,q)\in I\times I$ if one of the additive groups $S_{pq}$ and
$S_{qp}$ is nonzero, then the other one is also nonzero and
$S_{pq}S_{qp}=S_{p}$;

  3. (3)

$\forall(p,q)\in I\times I$ if one of the additive groups $S_{pq}$ and
$S_{qp}$ is nonzero, then the other one is also nonzero and $e_{p}\in
S_{pq}S_{qp}$.

###### Proof.

(1)$\Rightarrow$(2): Suppose (1) holds and take $(p,q)\in I\times I$.

  * •

Case 1: $S_{pq}\neq\\{0\\}$. Since $S_{p}\neq\\{0\\}$ it follows from (1),
with $i=p$, $j=q$ and $k=p$, that $S_{qp}\neq\\{0\\}$ and
$S_{pq}S_{qp}=S_{p}$.

  * •

Case 2: $G(q,p)\neq\\{0\\}$. Since $S_{q}\neq\\{0\\}$ it follows from (1),
with $i=q$, $j=p$ and $k=q$, that $S_{pq}\neq\\{0\\}$ and
$S_{qp}S_{pq}=S_{q}$.

(2)$\Rightarrow$(1): Suppose (2) holds and take $(i,j,k)\in I\times I\times
I$.

  * •

Case 1: $S_{ij}\neq\\{0\\}$ and $S_{jk}\neq\\{0\\}$. By (2) we get that
$\\{0\\}\neq S_{j}=S_{j}S_{j}=S_{ji}S_{ij}S_{jk}S_{kj}\subseteq
S_{ji}S_{ik}S_{kj}$. Therefore $S_{ik}\neq\\{0\\}$. By (2) again we get that
$S_{ik}=S_{ik}S_{k}=S_{ik}S_{kj}S_{jk}\subseteq S_{ij}S_{jk}\subseteq S_{ik}$.
Thus $S_{ij}S_{jk}=S_{ik}$.

  * •

Case 2: $S_{ij}\neq\\{0\\}$ and $S_{ik}\neq\\{0\\}$. By (2) we get that
$\\{0\\}\neq S_{i}=S_{i}S_{i}=S_{ij}S_{ji}S_{ik}S_{ki}\subseteq
S_{ij}S_{jk}S_{ki}$. Therefore $S_{jk}\neq\\{0\\}$. The same calculation as in
Case 1 shows that $S_{ij}S_{jk}=S_{ik}$.

  * •

Case 3: $S_{ik}\neq\\{0\\}$ and $S_{jk}\neq\\{0\\}$. By (2) we get that
$\\{0\\}\neq S_{k}=S_{k}S_{k}=S_{ki}S_{ik}S_{kj}S_{jk}\subseteq
S_{ki}S_{ij}S_{jk}$. Therefore $S_{jk}\neq\\{0\\}$. The same calculation as in
Case 1 shows that $S_{ij}S_{jk}=S_{ik}$.

(2)$\Leftrightarrow$(3): This is clear since $e_{p}\in S_{p}$ for all $p\in
I$. ∎

######  Definition 10.

If $S$ and $\\{e_{i}\\}_{i\in I}$ satisfy any of the three equivalent
properties in Proposition 9, then we say that $\\{e_{i}\\}_{i\in I}$ is a
_strong_ complete set of idempotents for $S$.

######  Proposition 11.

Let $\\{e_{i}\\}_{i\in I}$ be a strong complete set of idempotents for $S$.
Suppose $S_{ij}\neq\\{0\\}$ for some $i,j\in I$.

  1. (1)

The poset of left (right) ideals of $S_{i}$ ($S_{j}$) is isomorphic to the
poset of left (right) $S_{j}$-submodules of $S_{ji}$ ($S_{ij}$).

  2. (2)

The ring $S_{i}$ ($S_{j}$) is left (right) artinian/noetherian if and only if
the left $S_{j}$-module (right $S_{i}$-module) $S_{ji}$ is
artinian/noetherian.

###### Proof.

We show the “left” part of the proof and leave the “right” part to the reader.
Since (2) obviously follows from (1) it is enough to show (1). Define maps
$\alpha:\\{\mbox{left ideals of $S_{i}$}\\}\to\\{\mbox{left $S_{j}$-submodules
of $S_{ji}$}\\}$ and $\beta:\\{\mbox{left $S_{j}$-submodules of
$S_{ji}$}\\}\to\\{\mbox{left ideals of $S_{i}$}\\}$ by $\alpha(I)=e_{j}SI$ and
$\beta(M)=e_{i}SM$ for left ideals $I$ of $S_{i}$ and left $S_{j}$-submodules
$M$ of $S_{ji}$. Then, clearly, $\alpha$ and $\beta$ are well defined
inclusion preserving maps. Take a left ideal $I$ of $S_{i}$ and a left
$S_{j}$-submodule $M$ of $S_{ji}$. By Proposition 9 we get that
$\beta(\alpha(I))=\beta(e_{j}SI)=S_{ij}S_{ji}I=S_{i}I=I$ and
$\alpha(\beta(M))=\alpha(e_{i}SM)=S_{ji}S_{ij}M=S_{j}M=M$. This proves (1). ∎

######  Proposition 12.

Let $\\{e_{i}\\}_{i\in I}$ be a finite strong complete set of idempotents for
$S$. Suppose that for every $i\in I$ the ring $S_{i}$ is left/right artinian
(noetherian). Then $S$ is left/right artinian (noetherian).

###### Proof.

We show the “left” part of the proof and leave the “right” part to the reader.
Take $i,j\in I$. By Proposition 11(2) it follows that the left $S_{j}$-module
$S_{ji}$ is artinian (noetherian). By Proposition 5(1) it follows that
$S_{ji}$ is artinian (noetherian) as a left $S_{0}$-module. Since $I$ is
finite, it follows from Proposition 5(4) that $S=\oplus_{k,l\in I}S_{kl}$ is
artinian (noetherian) as a left $S_{0}$-module. By Proposition 5(1), $S$ is
left artinian (noetherian). ∎

### Proof of Theorem 1

The “only if” statements follow from Proposition 7 and Proposition 8. The ”if”
statement follows from Proposition 12. ∎

##  3\. Hom-set strong categories

In this section, we state our conventions on categories and groupoids. We
introduce the class of hom-set strong categories and we show that this class
strictly contains the class of groupoids. At the end of the section, we show a
finiteness result for hom-set strong categories.

######  Definition 13.

For the rest of this article, unless otherwise stated, we let $G$ denote a
small category. Recall that this means that the collection of objects in $G$,
denoted by $G_{0}$, and the collection of morphisms in $G$, denoted by
$G_{1}$, are sets. The domain and codomain of $g\in G_{1}$ is denoted by
$d(g)$ and $c(g)$ respectively; we indicate this by writing $g:d(g)\to c(g)$.
Given $a,b\in G_{0}$ we let $G(a,b)$ denote the set of morphisms $b\to a$. We
put $G(a):=G(a,a)$ for $a\in G_{0}$. We always regard $G_{0}$ as a subset of
$G_{1}$. Therefore, we denote the identity morphism $a\to a$ by $a$. We put
$G_{2}:=\\{(g,h)\in G_{1}\times G_{1}\mid d(g)=c(h)\\}$. If $(g,h)\in G_{2}$,
then the composition of $g$ and $h$ is written as $gh$. We say that $G$ is
finite if $G_{1}$, and hence also $G_{0}$, is finite. Recall that a category
$G$ is said to be a _groupoid_ if all morphisms in $G$ are isomorphisms. In
that case, the inverse of a morphism $g:a\to b$ in $G$ is denoted by
$g^{-1}:b\to a$.

######  Proposition 14.

For a category $G$, the following properties are equivalent:

  1. (1)

$\forall(a,b,c)\in G_{0}\times G_{0}\times G_{0}$ if two of the sets $G(a,b)$,
$G(b,c)$ and $G(a,c)$ are nonempty, then the third set is nonempty and
$G(a,b)G(b,c)=G(a,c)$;

  2. (2)

$\forall(x,y)\in G_{0}\times G_{0}$ if one of the sets $G(x,y)$ and $G(y,x)$
is nonempty, then the other set is nonempty and $G(x,y)G(y,x)=G(x)$;

  3. (3)

$\forall(x,y)\in G_{0}\times G_{0}$ if one of the sets $G(x,y)$ and $G(y,x)$
is nonempty, then the other set is nonempty and $x\in G(x,y)G(y,x)$.

###### Proof.

(1)$\Rightarrow$(2): Suppose (1) holds and take $(x,y)\in G_{0}\times G_{0}$.

  * •

Case 1: $G(x,y)\neq\emptyset$. Since $G(x,x)\neq\emptyset$ it follows from
(1), with $a=x$, $b=y$ and $c=a$, that $G(y,x)\neq\emptyset$ and
$G(x,y)G(y,x)=G(x)$.

  * •

Case 2: $G(y,x)\neq\emptyset$. Since $G(y,y)\neq\emptyset$ it follows from
(1), with $a=y$, $b=x$ and $c=y$, that $G(x,y)\neq\emptyset$ and
$G(y,x)G(x,y)=G(y)$.

(2)$\Rightarrow$(1): Suppose (2) holds and take $(a,b,c)\in G_{0}\times
G_{0}\times G_{0}$.

  * •

Case 1: $G(a,b)\neq\emptyset$ and $G(b,c)\neq\emptyset$. Then $G(a,c)\supseteq
G(a,b)G(b,c)\neq\emptyset$ so that $G(a,c)\neq\emptyset$. From (2), with $x=c$
and $y=b$, we get that $G(c,b)\neq\emptyset$ and $G(c,b)G(b,c)=G(c)$. Thus
$G(a,c)=G(a,c)G(c)=G(a,c)G(c,b)G(b,c)\subseteq G(a,b)G(b,c)\subseteq
G(a,c)\Rightarrow G(a,b)G(b,c)=G(a,c)$.

  * •

Case 2: $G(a,b)\neq\emptyset$ and $G(a,c)\neq\emptyset$. From (2), with $x=a$
and $y=b$, it follows that $G(b,a)\neq\emptyset$. Thus $G(b,c)\supseteq
G(b,a)G(a,c)\neq\emptyset$ and hence $G(b,c)\neq\emptyset$. A calculation
similar to Case 1 gives $G(a,b)G(b,c)=G(a,c)$.

  * •

Case 3: $G(a,c)\neq\emptyset$ and $G(b,c)\neq\emptyset$. From (2), with $x=c$
and $y=b$, it follows that $G(b,c)\neq\emptyset$. Thus $G(a,b)\supseteq
G(a,c)G(c,b)\neq\emptyset$ and hence $G(a,b)\neq\emptyset$. A calculation
similar to Case 1 gives $G(a,b)G(b,c)=G(a,c)$.

(2)$\Leftrightarrow$(3): This is clear since $x\in G(x)$ for all $x\in G_{0}$.
∎

######  Definition 15.

If a category $G$ satisfies any of the equivalent properties in Proposition
14, then we say that $G$ is a _hom-set strong_ category.

######  Proposition 16.

If $G$ is a groupoid, then $G$ is a hom-set strong category.

###### Proof.

This follows from Proposition 14(3) and the fact that for every morphism
$g:b\to a$ in $G$ the relation $a=gg^{-1}\in G(a,b)G(b,a)$ holds. ∎

######  Example 17.

Not all hom-set strong categories are groupoids. Indeed, let $M$ be a monoid
with identity element $1$. Take a nonempty set $X$. We now define the category
$MX$ in the following way. As set of objects in $MX$ we take $X$. As morphisms
in $MX$ we take all triples $g=(m,x,y)$, for $x,y\in X$, where we put $d(g)=y$
and $c(g)=x$. The composition of $g=(m,x,y)$ with $h=(n,y,z)$, for $m,n\in M$
and $x,y,x\in X$, is defined as $gh=(mn,x,z)$. Then, for all $x,y\in X$, the
set $MX(x,y)$ is nonempty and $(1,x,x)=(1,x,y)(1,y,x)\in MX(x,y)MX(y,x)$.
Thus, by Proposition 14(3), it follows that $MX$ is a hom-set strong category.
On the other hand, it is easily checked that $MX$ is a groupoid if and only if
$M$ is a group.

######  Proposition 18.

Suppose $G$ is a hom-set strong category. Then $G$ is finite if and only if
$G_{0}$ is finite and for every $a\in G_{0}$ the monoid $G(a)$ is finite.

###### Proof.

The “only if” statement is clear. Now we show the “if” statement. Suppose
$G_{0}$ is finite and let all monoids $G(a)$, for $a\in G_{0}$, be finite.
Take different $c,d\in G_{0}$ with $G(c,d)\neq\emptyset$. By Proposition 14(3)
there are $p:c\to d$ and $q:d\to c$ such that $pq=c$. Define maps
$\alpha:G(c,d)\to G(c)$ and $\beta:G(c)\to G(c,d)$ by $\alpha(g)=qg$, for
$g\in G(c,d)$, and $\beta(h)=ph$, for $h\in G(c)$. Then $\beta\alpha={\rm
id}_{G(c,d)}$, which, in particular, implies that $\alpha$ is injective. Since
$G(c)$ is finite this implies that $G(c,d)$ is finite. Thus, since $G_{0}$ is
finite, we get that $G_{1}=\cup_{a,b\in G_{0}}G(a,b)$ is finite. ∎

##  4\. Hom-set-strongly category graded rings

In this section, we study the class of object unital category (and groupoid)
graded rings. At the end of the section, we prove Theorem 2.

######  Definition 19.

For the rest of this section, we let $S$ denote a ring which is _$G$ -graded_.
Recall from [6, 7] that this means that there for every $g\in G_{1}$ is an
additive subgroup $S_{g}$ of $S$ such that $S=\bigoplus_{g\in G_{1}}S_{g}$ and
for all $g,h\in G_{1}$, the inclusion $S_{g}S_{h}\subseteq S_{gh}$ holds, if
$(g,h)\in G_{2}$, and $S_{g}S_{h}=\\{0\\}$, otherwise. Note that if $H$ is a
subcategory of $G$ then $S_{H}:=\oplus_{h\in H_{1}}S_{h}$ is a subring of $S$.
Following [2, 3] (see also [8]) we say that the $G$-grading on $S$ is object
unital if for all $a\in G_{0}$ the ring $S_{a}$ is unital and for all $g\in
G_{1}$ and all $s\in S_{g}$ the equalities $1_{S_{c(g)}}s=s1_{S_{d(g)}}=s$
hold. In that case, $S$ is a ring with enough idempotents with
$\\{1_{S_{a}}\\}_{a\in G_{0}}$ as a complete set of idempotents and the
following equality holds for all $a,b\in G_{0}$:

(1) $1_{S_{a}}S1_{S_{b}}=S_{G(a,b)}.$

Following [6] we say that $S$ is _strongly $G$-graded_ if for all $(g,h)\in
G_{2}$, the equality $S_{g}S_{h}=S_{gh}$ holds.

######  Proposition 20.

Suppose $G$ is a hom-set strong category and let $S$ be an object unital
$G$-graded ring. Then the following properties are equivalent:

  1. (1)

$\forall(a,b,c)\in G_{0}\times G_{0}\times G_{0}$ if two of the groups
$S_{G(a,b)}$, $S_{G(b,c)}$ and $S_{G(a,c)}$ are nonzero, then the third is
also nonzero and $S_{G(a,b)}S_{G(b,c)}=S_{G(a,c)}$;

  2. (2)

$\forall(p,q)\in G_{0}\times G_{0}$ if one of the groups $S_{G}(p,q)$ and
$S_{G(q,p)}$ is nonzero, then the other one is also nonzero and
$S_{G(p,q)}S_{G(q,p)}=S_{G(p)}$;

  3. (3)

$\forall(p,q)\in I\times I$ if one of the groups $S_{G(p,q)}$ and $S_{G(q,p)}$
is nonzero, then the other one is also nonzero and $1_{S_{p}}\in
S_{G(p,q)}S_{G(q,p)}$;

  4. (4)

The set $\\{1_{S_{a}}\\}_{a\in G_{0}}$ is a strong complete set of idempotents
for $S$.

###### Proof.

This follows from Proposition 9, Proposition 14 and equation (1). ∎

######  Definition 21.

Suppose $G$ is a hom-set strong category and let $S$ be an object unital
$G$-graded ring. If $S$ satisfies any of the equivalent properties in
Proposition 20, then we say that $S$ is _hom-set-strongly_ $G$-graded.

######  Theorem 22.

Suppose $S$ is an object unital $G$-graded ring.

  1. (1)

If $S$ is left/right artinian (noetherian), then $G_{0}$ is finite and, for
every $a\in G_{0}$, the ring $S_{G(a)}$ is left/right artinian (noetherian).

  2. (2)

Suppose $G$ is a hom-set strong category and let $S$ be hom-set-strongly
$G$-graded. Then $S$ is left/right artinian (noetherian) if and only if
$G_{0}$ is finite and $S_{G(a)}$ is left/right artinian (noetherian) for all
$a\in G_{0}$.

###### Proof.

This follows from Theorem 1 and Proposition 20. ∎

######  Proposition 23.

Suppose $S$ is an object unital $G$-graded ring. If $G$ is a groupoid, then
$S$ is hom-set-strongly $G$-graded.

###### Proof.

Suppose $G$ is a groupoid. By Proposition 16 $G$ is hom-set strong. Take
$p,q\in G_{0}$. We consider two cases. Case 1: $S_{G(p,q)}\neq\\{0\\}$. Then
there is $g:q\to p$ with $S_{g}\neq\\{0\\}$. Since $S$ is strongly $G$-graded
it follows that $1_{S_{p}}\in S_{p}=S_{g}S_{g^{-1}}\subseteq
S_{G(p,q)}S_{G(q,p)}$. Thus $S_{G(q,p)}\neq\\{0\\}$. Case 2:
$S_{G(q,p)}\neq\\{0\\}$. By a calculation similar to the one in Case 1 it
follows that $S_{G(p,q)}\neq\\{0\\}$ and that $1_{S_{p}}\in
S_{G(p,q)}S_{G(q,p)}$. By Proposition 20(3) it follows that $S$ is hom-set-
strongly $G$-graded. ∎

######  Definition 24.

Recall that a group is called _torsion-free_ if the only element in the group
of finite order is the identity. More generally, we say that a groupoid $G$ is
torsion-free if for every $a\in G_{0}$ the group $G(a)$ is torsion-free.

######  Theorem 25.

Suppose $H$ is a torsion-free group with identity element 1 and let $T$ be a
unital and $H$-graded ring. Then $T$ is left/right artinian if and only if
$T_{1}$ is left/right artinian and $T$ is finitely generated as a left/right
$T_{1}$-module.

###### Proof.

This is [10, Cor. 9.6.2] (see also [5, Thm. 1.2]). ∎

######  Definition 26.

Recall that a group is called _polycyclic-by-finite_ if it has a finite length
subnormal series with each factor a finite group or an infinite cyclic group.
More generally, we say that a groupoid $G$ is polycyclic-by-finite if for
every $a\in G_{0}$ the group $G(a)$ is polycyclic-by-finite.

######  Theorem 27.

Suppose $H$ is a polycyclic-by-finite group with identity element 1 and let
$T$ be a unital and strongly $H$-graded ring. Then $T$ is left/right
noetherian if and only if $T_{1}$ is left/right noetherian.

###### Proof.

See [1, Prop. 2.5] and in a slightly more general case [5, Thm. 1.1] ∎

### Proof of Theorem 2

This follows from Theorem 22, Proposition 23, Theorem 25 and Theorem 27. ∎

##  5\. Skew category algebras

In this section, we apply the previous results to analyse chain conditions for
skew category algebras which are defined by skew category systems of unital
rings. At the end of the section, we prove Theorems 3 and 4.

######  Definition 28.

For the rest of the article, let $R=\\{R_{a}\\}_{a\in G_{0}}$ be a collection
of unital rings and let $\alpha=\\{\alpha_{g}:R_{d(g)}\to R_{c(g)}\\}_{g\in
G_{1}}$ be a collection of ring isomorphisms. Following [9] we say that
$\alpha$ is a _skew category system_ if $\alpha$ is a functor from $G$ to the
category of unital rings, that is, if $\alpha(gh)=\alpha(g)\alpha(h)$ for all
$(g,h)\in G_{2}$. Again following [9], we say that the associated _skew
category algebra_ of $G$ over $R$, denoted by $R*_{\alpha}G$, is the set of
formal finite sums of elements of the form $rg$ for $r\in R_{c(g)}$ and $g\in
G_{1}$. The addition in $R*_{\alpha}G$ is defined by the relations
$rg+r^{\prime}g=(r+r^{\prime})g$ for $r,r^{\prime}\in R_{c(g)}$ and $g\in
G_{1}$. The multiplication in $R*_{\alpha}G$ is defined by the additive
extensions of the relations $rg\cdot r^{\prime}h=r\alpha_{g}(r^{\prime})gh$,
for $r\in R_{c(g)},r^{\prime}\in R_{c(h)}$ and $(g,h)\in G_{2}$, and $rg\cdot
r^{\prime}h=0$, when $g,h\in G_{1}$ but $(g,h)\notin G_{2}$. The ring
$R*_{\alpha}G$ is $G$-graded if we put $(R*_{\alpha}G)_{g}=R_{c(g)}g$ for
$g\in G_{1}$. In fact, with this grading, $R*_{\alpha}G$ is strongly
$G$-graded. Also $R*_{\alpha}G$ is object unital since for each $a\in G_{0}$,
the ring $(R*_{\alpha}G)_{a}=R_{a}a$ is unital with $1_{R_{a}a}=1_{R_{a}}a$.
If $G$ is a groupoid (group, monoid), then $R*_{\alpha}G$ is called a skew
groupoid (group, monoid) algebra of $G$ over $R$. If all the rings in $R$
coincide with a ring $T$ and the ring isomorphisms in $\alpha$ are identity
maps, then $R*_{\alpha}G$ is called a _category algebra_ of $G$ over $T$ and
is denoted by $T[G]$. In that case, if $G$ is groupoid (group, monoid), then
$T[G]$ is called a groupoid (group, monoid) algebra of $G$ over $T$. If $a\in
G_{0}$, then we put $\alpha(a)=\\{\alpha_{g}:R_{d(g)}\to R_{c(g)}\\}_{g\in
G(a)}$.

######  Proposition 29.

If $R*_{\alpha}G$ is left/right artinian (noetherian), then $G_{0}$ is finite
and, for every $a\in G_{0}$, the skew monoid ring $R_{a}*_{\alpha(a)}G(a)$ is
left/right artinian (noetherian).

###### Proof.

This follows from Theorem 22(1). ∎

######  Proposition 30.

The set $\\{1_{R_{a}}a\\}_{a\in G_{0}}$ is a strong complete set of
idempotents for $R*_{\alpha}G$ if and only if the category $G$ is hom-set
strong. In that case, the ring $R*_{\alpha}G$ is hom-set-strongly $G$-graded.

###### Proof.

Put $S=R*_{\alpha}G$.

Suppose $\\{1_{R_{a}}a\\}_{a\in G_{0}}$ is a strong complete set of
idempotents for $S$ and take $(x,y)\in G_{0}\times G_{0}$ such that one of the
sets $G(x,y)$ and $G(y,x)$ is nonempty.

  * •

Case 1: $G(x,y)\neq\emptyset$. Then
$1_{R_{x}}xS1_{R_{y}}y=S_{G(x,y)}\neq\\{0\\}$. By Proposition 9(3) it follows
that $S_{G(y,x)}=1_{R_{y}}yS1_{R_{x}}x\neq\\{0\\}$ and $1_{R_{x}}x\in
S_{G(x,y)}S_{G(y,x)}$. Thus, in particular, $x\in G(x,y)G(y,x)$.

  * •

Case 2: $G(y,x)\neq\emptyset$. By an argument similar to the one used in Case
1 it follows that $G(x,y)\neq\emptyset$ and $y\in G(y,x)G(x,y)$.

By Proposition 14(3) it follows that $G$ is hom-set strong.

Suppose that $G$ is hom-set strong and take $(p,q)\in G_{0}$ such that one of
the additive groups $1_{R_{p}}pS1_{R_{q}}q=S_{G(p,q)}$ and
$1_{R_{q}}qS1_{R_{p}}p=S_{G(q,p)}$ is nonzero.

  * •

Case 1: $S_{G(p,q)}\neq\\{0\\}$. Then $G(p,q)\neq\emptyset$. Proposition 14(3)
implies that $G(q,p)\neq\emptyset$ and $p\in G(p,q)G(q,p)$. Thus
$1_{R_{p}}p\in S_{G(p,q)}S_{G(q,p)}$.

  * •

Case 2: $S_{G(p,q)}\neq\\{0\\}$. By an argument similar to the one used in
Case 1 it follows that $G(p,q)\neq\emptyset$ and $q\in G(q,p)G(p,q)$ and
$1_{R_{q}}q\in S_{G(q,p)}S_{G(p,q)}$.

By proposition 9(3) it follows that $\\{1_{R_{a}}a\\}_{a\in G_{0}}$ is a
strong complete set of idempotents for $S$. The last statement follows from
Proposition 20. ∎

######  Proposition 31.

Suppose $G$ is hom-set strong. Then $R*_{\alpha}G$ is left/right artinian
(noetherian) if and only if $G_{0}$ is finite and, for every $a\in G_{0}$, the
skew monoid ring $R_{a}*_{\alpha(a)}G(a)$ is left/right artinian (noetherian).

###### Proof.

This follows from Theorem 22(2) and Proposition 30. ∎

For the rest of the article, $T$ denotes a fixed unital ring.

######  Theorem 32.

Suppose $H$ is a group and let $\alpha:H\to{\rm Aut}(T)$ be a group
homomorphism. Then the associated skew group ring $T*_{\alpha}H$ is left/right
artinian if and only if $H$ is finite and $T$ is left/right artinian.

###### Proof.

This is a result by Park [13, Thm. 3.3] ∎

######  Theorem 33.

Suppose $M$ is a monoid. Then the monoid algebra $T[M]$ is left/right artinian
if and only if $M$ is finite and $T$ is left/right artinian.

###### Proof.

This is a result by Zelmanov [15, Corollary at p. 562]. ∎

######  Proposition 34.

If the category algebra $T[G]$ is left/right artinian, then $T$ is left/right
artinian and $G$ is finite.

###### Proof.

This follows from Theorem 33 and Propositions 18 and 29. ∎

### Proof of Theorem 3 and Theorem 4

This follows from Proposition 31, Theorem 32, Theorem 33 and Proposition 34. ∎

## References

  * [1] A. D. Bell, Localization and Ideal Theory in Noetherian Strongly Group-Graded Rings, J. Algebra 105, 76–115 (1987).
  * [2] J. Cala, P. Lundström and H. Pinedo, Object-unital groupoid graded rings, crossed products and separability, Comm. in Algebra, 49:4, 1676–1696 (2021).
  * [3] J. Cala, P. Lundström and H. Pinedo, Graded modules over object-unital groupoid graded rings, Comm. in Algebra, 50:2, 444–462 (2022).
  * [4] K. R. Fuller, On rings whose left modules are direct sums of finitely generated modules, Proc. Amer. Math. Soc. 54, 39–44 (1976).
  * [5] D. Lännström. Chain conditions for epsilon-strongly graded rings with applications to Leavitt path algebras. Algebr. Represent. Theory 23 no. 4, 1707–1726 (2020).
  * [6] P. Lundström, The category of groupoid graded modules, Colloq. Math. 100(4), 195–211 (2004).
  * [7] P. Lundström, Crossed product algebras defined by separable extensions, J. Algebra 283, 723–737 (2005).
  * [8] P. Lundström and J. Öinert, Miyashita action in strongly groupoid graded rings, Internat. Electronic J. Algebra 11, 46–63 (2012).
  * [9] P. Lundström and J. Öinert, Skew category algebras associated with partially defined dynamical systems, Internat. Journal of Mathematics, 23(4) (2012), pp. 16.
  * [10] C. Nastasescu and F. van Oystaeyen, Methods of graded rings, Springer Lecture Notes (2004).
  * [11] P. Nystedt and J. Öinert, Simple skew category algebras associated with minimal partially defined dynamical systems, Discrete and Continuous Dynamical Systems - Series A (DCDS-A), 33(9), 4157–4171 (2013).
  * [12] P. Nystedt, J. Öinert and H. Pinedo, Artinian and noetherian partial skew groupoid rings _J. of Algebra_ , 503, 433–452 (2018).
  * [13] J. K. Park, Artinian skew group rings, _Proc. Amer. Math. Soc_ 75, no. 1, 1–7 (1979).
  * [14] L. H. Rowen, _Ring Theory. Vol. I_. Pure and Applied Mathematics, 127. Academic Press, Inc., Boston, MA (1988).
  * [15] E.I. Zelmanov, Semigroup algebras with identities, Sibirsk. Mat. Zh. 18(4) 787–798 (1977).