# Cycle Matroids of Graphings: From Convergence to Duality

Kristóf Bérczi MTA-ELTE Matroid Optimization Research Group and HUN-REN–ELTE
Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, and HUN-REN Alfréd Rényi Institute of Mathematics, Budapest,
Hungary. Email<EMAIL_ADDRESS>Márton Borbényi Department of
Computer Science, Eötvös Loránd University and HUN-REN Alfréd Rényi Institute
of Mathematics, Budapest, Hungary. Email<EMAIL_ADDRESS>László
Lovász HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary.
Email<EMAIL_ADDRESS>László Márton Tóth
HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary. Email:
<EMAIL_ADDRESS>
###### Abstract

A recent line of research has concentrated on exploring the links between
analytic and combinatorial theories of submodularity, uncovering several key
connections between them. In this context, Lovász initiated the study of
matroids from an analytic point of view and introduced the cycle matroid of a
graphing [18]. Motivated by the limit theory of graphs, the authors introduced
a form of right-convergence, called quotient-convergence, for a sequence of
submodular setfunctions, leading to a notion of convergence for matroids
through their rank functions [3].

In this paper, we study the connection between local-global convergence of
graphs and quotient-convergence of their cycle matroids. We characterize the
exposed points of the associated convex set, forming an analytic counterpart
of matroid base-polytopes. Finally, we consider dual planar graphings and show
that the cycle matroid of one is the cocycle matroid of its dual if and only
if the underlying graphings are hyperfinite.

Keywords: Cycle matroid, Duality, Exposed points, Graphings, Matroid limits,
Cost

###### Contents

  1. 1 Introduction
    1. 1.1 Limit theory
    2. 1.2 Fractional bases
    3. 1.3 Matroids beyond the hyperfinite
    4. 1.4 Duality
    5. 1.5 Other notions of cycle matroids on infinite graphs
  2. 2 Preliminaries
    1. 2.1 Submodular setfunctions and matroids
    2. 2.2 Graphings and hyperfiniteness
    3. 2.3 Local and local-global convergence
    4. 2.4 Quotient-convergence of setfunctions
    5. 2.5 Cost
  3. 3 Connection to sparse graph limits
    1. 3.1 Continuity for local-global convergence
    2. 3.2 Non-continuity for local convergence
  4. 4 Exposed minorizing measures and hyperfinite spanning forests
    1. 4.1 Exposed points
    2. 4.2 Weakly exposed points
  5. 5 Duality
    1. 5.1 Duality for hyperfinite planar graphings
    2. 5.2 A matroid attaining the cost
    3. 5.3 Free versus wired spanning forests

##  1 Introduction

Cycle matroids bridge graph theory and matroid theory by providing matroid
theoretic counterparts of graph concepts such as cycles, cuts, and spanning
trees, thus leading to a powerful framework for understanding and solving
various combinatorial and optimization problems. The matroidal perspective
allows for a deeper analysis of graph properties and leads to efficient
algorithms in network design, electrical engineering, and operations research.

_Graphings_ are bounded degree graphs on standard probability measure spaces,
serving as limit objects in sparse graph limit theory, see Subsection 2.2 for
the definition. Recently, Lovász [18] initiated the study of cycle matroids
from an analytic point of view and introduced the cycle matroid of a graphing
$\mathcal{G}=(X,E,\mu)$ by defining its rank function as

$\rho_{\mathcal{G}}(F)=1-\mathbb{E}_{x}\left[\frac{1}{|V(\mathcal{G}^{F}_{x})|}\right],$
(1)

where $F\subseteq E$ is Borel, $x$ is a $\mu$-random vertex of $\mathcal{G}$
and $\mathcal{G}^{F}_{x}$ denotes its connected component in the graphing
$\mathcal{G}^{F}=(X,F,\mu)$. It was shown that $\rho_{\mathcal{G}}$ is an
increasing submodular setfunction on the Borel subsets of $E$. It is not
difficult to verify that this definition generalizes the normalized rank of
the cycle matroid of a finite graph.

This raises several questions about cycle matroids of graphings. How to define
and describe their bases, cycles, and other basic properties known from the
finite case? Does the convergence of a sequence of finite graphs to a graphing
imply convergence of the corresponding matroids (in the sense introduced in
[3])? Does duality of matroids play any role? In this paper, we provide some
answers to these questions. We develop the limit theory of these matroids,
study their bases, and investigate how they behave under duality of planar
graphings. We give some background on earlier work on cycle matroids of
infinite graphs in Subsection 1.5.

###  1.1 Limit theory

Our first result connects local-global convergence of graphs with quotient-
convergence of the rank function of cycle matroids, defined in [3]. We give a
short definition, but refer to Subsection 2.4 for the setup and a precise
formulation. A _$k$ -quotient_ of a setfunction $\varphi$ on a set-algebra
$(J,\mathcal{B})$ is $\varphi\circ F^{-1}$, where $F:J\to[k]$ is a measurable
map. We denote by $Q_{k}(\varphi)$ the set of $k$-quotients of $\varphi$. A
sequence of setfunctions $(\varphi_{1},\varphi_{2},\dots)$ _quotient
converges_ to $\varphi$, denoted $\varphi_{n}\rightarrowtail\varphi$, if
$Q_{k}(\varphi)\to Q_{k}(\varphi)$ in the Hausdorff distance for all
$k\in\mathbb{N}$.

######  Theorem 1.1.

Let $(G_{1},G_{2},\dots)$ be a sequence of finite graphs with all degrees
bounded by $D$ that converges to the graphing $\mathcal{G}$ in the local-
global sense. Let $r_{G_{n}}$ denote the rank function of the cycle matroid of
$G_{n}$. Then

$\frac{r_{G_{n}}}{|V(G_{n})|}\rightarrowtail\rho_{\mathcal{G}}$

in the sense of quotient-convergence of submodular setfunctions.

We also exhibit an example showing that assuming local convergence of $G_{n}$
is not enough.

######  Theorem 1.2.

There exists a sequence $(H_{1},H_{2},\dots)$ of finite graphs with all
degrees bounded by $D$ that converges to a graphing $\mathcal{G}$ in the local
sense, however

$\frac{r_{H_{n}}}{|V(H_{n})|}\centernot\rightarrowtail\rho_{\mathcal{G}}.$

###  1.2 Fractional bases

For a finite matroid $M=(E,r)$ with ground set $E$ and rank function $r$, the
set of fractional bases

$C_{M}=\left\\{x\in\mathbb{R}^{E}~{}\Big{|}~{}x\geq 0,\ \sum_{e\in A}x(a)\leq
r(A)\text{ for }A\subseteq E,\ \sum_{e\in E}x(e)=r(E)\right\\}$

forms an integral polytope whose vertices are exactly the bases of $M$, called
the _base-polytope_ of $M$. For the cycle matroid of a connected graph, this
means that among fractional spanning trees, the extreme ones are genuine
spanning trees.

In the analytic setting developed by Lovász [19], the analogue of a base-
polytope is the set of _basic minorizing finitely additive measures_. In
particular, for a graphing $\mathcal{G}=(X,E,\mu)$, this gives

$C_{\mathcal{G}}=\text{bmm}^{+}(\rho_{\mathcal{G}})=\big{\\{}\alpha\textrm{
finitely additive measure on $E$}~{}\big{|}~{}\alpha\leq\rho_{\mathcal{G}},\
\alpha(E)=\rho_{\mathcal{G}}(E)\big{\\}}.$

A vertex of a convex polytope generalizes to the infinite setting in several
ways. A point $v$ of the convex set $C$ is _extreme_ if it cannot be written
as $v=\frac{1}{2}(u+w)$, where $u,w\in C\backslash\\{v\\}$. The point $v$ is
_exposed_ if there is a supporting hyperplane $H$ through $v$ such that $H\cap
C=\\{v\\}$. This property depends on the topology of the ambient vector space;
in this paper, we mean that $H$ is defined by the inner product with a
function in $L^{1}(E)$. An exposed point is necessarily extreme, but not the
other way around; see Section 4 for further comments.

An _essential spanning forest_ of a graphing $\mathcal{G}$ is an acyclic
subset $T$ of the edges that forms a spanning tree in finite components of
$\mathcal{G}$, and contains only infinite $T$-components in the infinite
$\mathcal{G}$-components. Note that $T$ might contain several components in an
infinite component of $\mathcal{G}$, but all of those are required to be
infinite; this is why $T$ is called a spanning forest instead of a spanning
tree. As a generalization of the finite case, we prove the following.

######  Theorem 1.3.

Let $\mathcal{G}$ be a graphing. Then, the exposed points of $C_{\mathcal{G}}$
are exactly the hyperfinite essential spanning forests of $\mathcal{G}$.

The following question remains open.

######  Question 1.4.

Are all extreme points of $C_{\mathcal{G}}$ exposed, and therefore hyperfinite
spanning forests?

###  1.3 Matroids beyond the hyperfinite

While the definition of the cycle matroid via (1) is a consistent
generalization of the finite notion, it does have a drawback: the rank of the
full edge set is at most 1. This is natural for finite graphs, as spanning
trees have average degree slightly below 2. For graphings, however, spanning
trees can have higher average degree. The notion of _cost_ is designed to
measure the minimal amount of edges needed to generate the connected
components of a graphing; see the precise definition in Subsection 2.5. It
seems natural to ask if one can come up with a notion of cycle matroid whose
total rank is equal to the cost.

######  Question 1.5.

Is there a notion of the cycle matroid of a graphing $\mathcal{G}$ with
submodular rank function $\varphi_{\mathcal{G}}$ such that
$\varphi_{\mathcal{G}}(E)=\textrm{cost}(\mathcal{G})$?

A positive answer to this question would not invalidate $\rho_{\mathcal{G}}$,
rather complement it. See e.g. Theorems 1.9 and 1.10 below, where we use ideas
from [7] to give a positive answer for a certain class of planar graphings.

To further justify the study of $\rho_{\mathcal{G}}$, we highlight that even
though $\rho_{\mathcal{G}}$ only sees spanning forests that are hyperfinite,
it still carries a lot of information about the graphing. In the finite case,
Whitney proved that every 3-connected graph is uniquely determined by its
cycle matroid. In an upcoming work [2], we study analogous problems for
graphings.

######  Question 1.6.

Under what assumptions does $\rho_{\mathcal{G}}$ determine the graphing
$\mathcal{G}$ (up to measure zero)?

As a first step in this direction, we could show that $\rho_{\mathcal{G}}$
already determines acyclic graphings with minimum degree 3 up to _isomorphism_
in the following sense: For a graphing $\mathcal{G}$ and an acyclic graphing
$\mathcal{T}$ of minimum degree 3, if
$\rho_{\mathcal{G}}\cong\rho_{\mathcal{T}}$ then
$\mathcal{G}\cong\mathcal{T}$. In both cases, $\cong$ means that there exists
a measure preserving bijection between the ground spaces, up to measure zero,
that maps one structure to the other.

###  1.4 Duality

Duality is an important concept of matroid theory, and it lines up nicely with
duality of finite planar graphs: the dual of a cycle matroid of an (embedded)
planar graph is the cycle matroid of its planar dual. The question naturally
arises: Does an analogous statement hold for planar graphings?

The notion of a _planar graphing_ takes some work to set up. We postpone this
to Section 5, where we give an informal introduction and refer to [1] and [7]
for a rigorous treatment. For now, we only say that in a planar graphing, the
connected components are _planar maps_ , i.e. they are endowed with a
specified planar embedding. We assume that these planar maps have no
accumulation points in the plane. We also want to point out that the notion of
a “dual graph” is not completely evident when infinite faces are present [24,
25].

When we talk about a pair of dual graphings $\mathcal{G}$ and
$\mathcal{G}^{*}$, it is assumed, informally speaking, that the components of
$\mathcal{G}^{*}$ are, _as planar maps_ , the duals of the components of
$\mathcal{G}$. For simplicity, we exclude infinite faces, we assume that
components are $2$-vertex-connected to avoid edges that are only adjacent to
one face, and that the maximum size of the faces is bounded to make sure that
both $\mathcal{G}$ and $\mathcal{G}^{*}$ have bounded degree. For a dual pair,
there is a Borel bijection $\sigma:~{}E(\mathcal{G})\to E(\mathcal{G}^{*})$
such that the image of the star of a vertex of $\mathcal{G}$ is a facial cycle
in $\mathcal{G}^{*}$ and vice versa. We also note that the hyperfiniteness of
$\mathcal{G}$ and $\mathcal{G}^{*}$ are equivalent [1, Example 3.11,
Proposition 3.12].

######  Remark 1.7.

The above assumptions are made solely to avoid technical difficulties, not
because they are necessary for the results presented here. Our aim in this
paper is to showcase how duality works, and these assumptions allow us to do
so with minimal distraction. The aforementioned works [7] and [1] demonstrate
that, with dedicated treatment, such technical questions can be addressed to
prove theorems for planar graphings without these restrictions.

The dual of the cycle matroid, called the _cocyclic_ matroid of $\mathcal{G}$,
can be defined for any (not necessarily planar) graphing by its rank function

$\rho^{D}_{\mathcal{G}}(A)=\rho_{\mathcal{G}}(E\setminus
A)+\tilde{\mu}(A)-\rho_{\mathcal{G}}(E),$

where $\tilde{\mu}$ denotes the edge measure of $\mathcal{G}$. Our first
result here shows that in the hyperfinite case duality works as in the finite
case.

######  Theorem 1.8.

Let $\mathcal{G}$ and $\mathcal{G}^{*}$ be a hyperfinite pair of dual planar
graphings. Then, $\rho^{D}_{\mathcal{G}}=\rho_{\mathcal{G}^{*}}$ and
$\rho^{D}_{\mathcal{G}^{*}}=\rho_{\mathcal{G}}$.

However, when $\mathcal{G}$ and $\mathcal{G}^{*}$ are not hyperfinite, the two
matroids do not coincide. This is the case for example if the components of
$\mathcal{G}$ and $\mathcal{G}^{*}$ are dual hyperbolic tilings. We can
actually exploit this phenomenon to give a partial positive answer to Question
1.5.

######  Theorem 1.9.

Let $\mathcal{G}$ and $\mathcal{G}^{*}$ be a non-hyperfinite pair of dual
planar graphings. Then, $\rho^{D}_{\mathcal{G}^{*}}\neq\rho_{\mathcal{G}}$.
Moreover, $\rho^{D}_{\mathcal{G}^{*}}(E)$ is a submodular function on
$E(\mathcal{G})$ that attains the cost, i.e.

$\rho^{D}_{\mathcal{G}^{*}}(E)=\textrm{cost}(\mathcal{G}).$

Note that planar graphings are treeable [7], so if they are not hyperfinite,
their cost is strictly more than $1$. Both submodular functions
$\rho_{\mathcal{G}}$ and $\rho^{D}_{\mathcal{G}^{*}}$ are natural to consider,
as supported by the following result.

######  Theorem 1.10.

Let $\mathcal{G}$ and $\mathcal{G}^{*}$ be a pair of dual planar graphings.
Let $<$ be an arbitrary Borel total order on the edges. The Wired Maximal
Spanning Forest $\mathcal{T}^{<}_{w}$ is an exposed point of
$\text{bmm}^{+}(\rho_{\mathcal{G}})$, while the Free Maximal Spanning Forest
$\mathcal{T}^{<}_{f}$ is an exposed point of
$\text{bmm}^{+}(\rho^{D}_{\mathcal{G}^{*}})$.

In [1, Theorem 1 (15)], it was shown that a unimodular random map is
hyperfinite if and only if the wired and free maximal spanning forests
coincide. In our setup, this can be interpreted as
$\mathcal{T}^{<}_{f}=\mathcal{T}^{<}_{w}$ in the special case when
$\mathcal{G}$ is an (edge) Bernoulli graphing over the unimodular random
planar map, and $<$ is the natural ordering on the edges given by the edge-
labeling.

###  1.5 Other notions of cycle matroids on infinite graphs

In this paper we study the cycle matroids of graphings, as graphings are
natural limit objects in the context of sparse graph limits. It is equally
natural to extend the notion of cycle matroid to infinite graphs without a
measurable structure, for example connected locally finite graphs. There has
been an extensive line of research on this topic. Although it is not directly
related to our results, we mention some of the highlights.

Probably the simplest notion for infinite graphs is the finitary cycle matroid
whose circuits are exactly the finite cycles. However, an unfortunate feature
of finitary matroids is that excluding infinite circuits spoils duality. As a
workaround, Bruhn, Diestel, Kriesell, Pendavingh and Wollan [6] proposed five
equivalent sets of axioms leading to a non-finitary theory of infinite
matroids. These axioms were in fact shown to be equivalent to the notion of
B-matroids introduced by Higgs [11]. Using these axioms, Bruhn and Diestel [5]
provided further examples by defining the circuits of the matroid to be the
edge sets of topological circuits of compactifications of infinite graphs
obtained by adding the space of ends to the graph. Later, Bowler, Carmesin and
Christian [4] introduced a class of infinite cycle matroids that unifies
previous constructions.

##  2 Preliminaries

###  2.1 Submodular setfunctions and matroids

A setfunction $\varphi\colon\mathcal{B}\to\mathbb{R}$ on a set-algebra
$(J,\mathcal{B})$ is _submodular_ if $\varphi(X)+\varphi(Y)\geq\varphi(X\cap
Y)+\varphi(X\cup Y)$ holds for $X,Y\in\mathcal{B}$. One of the most basic
examples of a submodular function is the rank function of a matroid. A
_matroid_ $M=(E,r)$ is defined by its finite _ground set_ $E$ and its _rank
function_ $r\colon 2^{E}\to\mathbb{Z}_{+}$ that satisfies the so-called _rank
axioms_ : (R1) $r(\emptyset)=0$, (R2) $X\subseteq Y\Rightarrow r(X)\leq r(Y)$,
(R3) $r(X)\leq|X|$, and (R4) $r(X)+r(Y)\geq r(X\cap Y)+r(X\cup Y)$. Note that
axiom (R4) requires submodularity of the rank function. A set $X\subseteq E$
is called _independent_ if $r(X)=|X|$ and _dependent_ otherwise. The
_circuits_ of the matroid are formed by its inclusionwise dependent sets,
while maximal independent sets are called _bases_. The rank axioms imply that
any two bases have the same cardinality. For further details on matroids, the
reader is referred to [22].

###  2.2 Graphings and hyperfiniteness

We give the basic definitions for completeness, but point to [17, Chapters 18
and 21] for a thorough introduction. Let $(X,\mu)$ be a Borel probability
space. A _graphing_ is a graph $\mathcal{G}$ with $V(\mathcal{G})=X$ and Borel
edge set $E(\mathcal{G})\subseteq X\times X$, in which all degrees are finite,
and

$\int_{A}\deg_{B}(x)\ d\mu(x)=\int_{B}\deg_{A}(x)\ d\mu(x)$ (2)

for all measurable sets $A,B\subseteq X$, where $\deg_{S}(x)$ is the number of
edges from $x\in X$ to $S\subseteq X$. The assumption (2) allows one to
meaningfully define the _edge measure_ $\tilde{\mu}$ on $X\times X$ by setting

$\tilde{\mu}(A\times B)=\int_{B}\deg_{A}(x)\ d\mu(x)$

on product sets, and extending by Caratheodory’s theorem. The measure
$\tilde{\mu}$ is concentrated on $E(\mathcal{G})$. A graphing $\mathcal{G}$ is
_hyperfinite_ if, for every $\varepsilon>0$, there is a Borel set $S\subseteq
E(\mathcal{G})$ with $\tilde{\mu}(S)\leq\varepsilon$ such that every connected
component of $E\setminus S$ is finite. An acyclic graphing is called a
_treeing_. A treeing is hyperfinite exactly when its components have $0$, $1$,
or $2$ ends.

###  2.3 Local and local-global convergence

Intuitively, a sequence $(G_{1},G_{2},\dots)$ of finite graphs is said to be
_locally_ (or _Benjamini-Schramm_) _convergent_ if the local behaviour around
a random vertex of $G_{n}$ converges as $n\to\infty$. Formally, let
$r\in\mathbb{N}$ denote our radius of sight, and $\alpha$ denote a rooted,
connected graph of radius $r$. The _local statistics_ $P_{r}(G,\alpha)$ of a
finite graph $G$ are the probabilities
$\mathbb{P}_{v}\big{[}B_{G}(v,r)\cong\alpha\big{]}$, where the vertex $v\in
V(G)$ is chosen uniformly at random, $B_{G}(v,r)$ denotes the $r$-ball around
$v$ in $G$, and the isomorphism has to respect the root. One can define
$P_{r}(G,\alpha)$ analogously for a graphing $\mathcal{G}$, with the random
vertex being chosen according to $\mu$. A sequence $(G_{1},G_{2},\dots)$ of
finite graphs converges locally to a graphing $\mathcal{G}$ if the local
statistics converge, i.e. $P_{r}(G_{n},\alpha)\to P_{r}(\mathcal{G},\alpha)$
for all $r$ and $\alpha$.

Local-global convergence is a more refined notion of convergence, see [10] for
an introduction. We use a colored version of the neighborhood statistics. For
a fixed vertex-coloring $c\colon V(G)\to[k]$, the _colored neighborhood
statistics_ $P_{r}(G,c,\alpha)$ is obtained as before: we choose a vertex
$v\in V(G)$ uniformly at random, and then consider its colored
$r$-neighborhood $\big{(}B_{G}(v,r),c|_{B_{G}(r,v)}\big{)}$. Then the
probabilities $P_{r}[G,c]=\big{(}P_{r}(G,c,\alpha)\big{)}_{\alpha}$ form a
distribution on the set of rooted, colored, connected graphs $\alpha$ of
radius at most $r$. Let $Q_{k,r}(G)$ denote the (finite) set of possible
colored neighborhood statistics we can obtain by different colorings:

$Q_{k,r}(G)=\big{\\{}P_{r}[G,c]~{}\big{|}~{}c\colon V(G)\to[k]\big{\\}}.$

The set $Q_{k,r}(\mathcal{G})$ is defined analogously for a graphing, with the
assumption that the coloring $c\colon V(\mathcal{G})\to[k]$ is required to be
Borel. The sequence $G_{n}$ locally-globally converges to $\mathcal{G}$, if
$Q_{k,r}(G_{n})\to Q_{k,r}(\mathcal{G})$ in the Hausdorff distance. The local-
global convergence of $G_{n}$ means that for any $r,k\in\mathbb{N}$ and
$\varepsilon>0$, there is a threshold such that, for $i$ large enough, the
colored neighborhood distribution $P_{r}[G_{i},c]$ for any $k$-coloring $c$
can be approximately modeled on $\mathcal{G}$. That is, we can find some Borel
coloring $c^{\prime}$ of $\mathcal{G}$ such that $P_{r}[G_{i},c]$ and
$P_{r}[\mathcal{G},c^{\prime}]$ are $\varepsilon$-close. Vice versa, Borel
colorings of $\mathcal{G}$ can be approximately modeled on $G_{i}$.

###  2.4 Quotient-convergence of setfunctions

The quotient-convergence of setfunctions was introduced in [3]. Let
$\varphi\colon\mathcal{B}\to\mathbb{R}$ be a setfunction on a set-algebra
$(J,\mathcal{B})$ with $\varphi(\emptyset)=0$. The $k$-quotient set
$Q_{k}(\varphi)$ is then defined as the set of all quotients of $\varphi$ on
$[k]$, that is, the set of all setfunctions $\varphi\circ F^{-1}$ where
$F\colon J\to[k]$ is a measurable map. Note that $Q_{k}(\varphi)$ is a subset
of $\mathbb{R}^{2^{k}}$, with the two coordinates $\varphi\circ
F^{-1}(\emptyset)=0$ and $\varphi\circ F^{-1}(J)=\varphi(J)$ being fixed. The
_quotient profile_ of $\varphi$ is defined as the sequence
$(Q_{1}(\varphi),Q_{2}(\varphi),\dots)$, while the sequence of closures
$(\overline{Q}_{1}(\varphi),\overline{Q}_{2}(\varphi),\dots)$ is the closed
quotient profile of $\varphi$. A sequence $(\varphi_{1},\varphi_{2},\dots)$ of
setfunctions on set-algebras
$(J_{1},\mathcal{B}_{1}),(J_{2},\mathcal{B}_{2}),\dots$ is quotient-convergent
if for every positive integer $k$, the quotient sets
$(Q_{k}(\varphi_{1}),Q_{k}(\varphi_{2}),\dots)$ form a Cauchy sequence in the
Hausdorff distance $d_{{\text{\rm Haus}}_{2^{k}}}$ on the $2^{k}$-dimensional
Euclidean space. The sequence $(\varphi_{1},\varphi_{2},\dots)$ quotient-
converges to $\varphi$ for some setfunction $\varphi$ if the sequence
$(Q_{k}(\varphi_{1}),Q_{k}(\varphi_{2}),\dots)$ converges to $Q_{k}(\varphi)$
in the Hausdorff distance, denoted by $\varphi_{n}\rightarrowtail\varphi$. For
a finite _measurable partition_ $\mathcal{P}=\\{P_{1},\dots,P_{q}\\}$ of $J$,
that is, each $P_{i}$ is measurable, then $\varphi/\mathcal{P}\colon
2^{[k]}\to\mathbb{R}$ denotes the map defined by
$(\varphi/\mathcal{P})(X)=\varphi(\cup_{i\in X}P_{i})$ for $X\subseteq[k]$.

###  2.5 Cost

We give a very brief introduction to the theory of cost, and refer the reader
to [8] and [12] for more details. For two graphings $\mathcal{G}$ and
$\mathcal{H}$ on the same vertex set $(X,\mu)$ we write
$\mathcal{G}\sim\mathcal{H}$ if they have the same connected components. The
_cost_ of $\mathcal{G}$ is defined to be

$\textrm{cost}(\mathcal{G})=\frac{1}{2}\inf\big{\\{}\tilde{\mu}_{\mathcal{H}}\big{(}E(\mathcal{H})\big{)}\
\big{|}\ \mathcal{H}\sim\mathcal{G}\big{\\}}.$

Gaboriau proved that one cannot “cut costs” on treeings, that is, their edge
measure is the same as their cost.

######  Theorem 2.1 (Gaboriau [9]).

For a treeing $\mathcal{T}=(X,E,\mu)$, we have
$\textrm{cost}(\mathcal{T})=\mu_{\mathcal{T}}(E)$.

For a graphing with all components of size $n$, its cost is $1-\frac{1}{n}$,
and for hyperfinite graphings with infinite components the cost is 1. These
facts were observed by Levitt, and we combine them to fit our setup in the
following theorem.

######  Proposition 2.2 (Levitt [15]).

Let $\mathcal{T}=(X,E,\mu)$ be a treeing. Then, the following are equivalent:

  1. (i)

$\mathcal{T}$ is hyperfinite,

  2. (ii)

$\textrm{cost}(\mathcal{T})=\rho_{\mathcal{T}}(E)$.

##  3 Connection to sparse graph limits

In this section we prove Theorems 1.1 and 1.2.

###  3.1 Continuity for local-global convergence

It was proved already in [18, Theorem 4.7] that the rank of the whole edge set
of a graph is locally estimable, i.e. continuous with respect to local
convergence [17, Theorem 22.3].

######  Theorem 3.1.

Let $(G_{1},G_{2},\dots)$ be a sequence of finite graphs with all degrees
bounded by $D$ that converges to a graphing $\mathcal{G}$ in the local sense.
Then, $r_{n}(E(G_{n}))\to\rho_{\mathcal{G}}(E(\mathcal{G}))$.

We can strengthen this result to imply Theorem 1.1 by the following
observation. Given any graphing parameter $f$, we can turn it into a
setfunction $\varphi_{f}$ on subsets of edges of $\mathcal{G}=(X,E,\mu)$ by

$\varphi_{\mathcal{G},f}(F)=f\big{(}(X,F,\mu)\big{)}.$

######  Theorem 3.2.

If $f$ is continuous with respect to local convergence and
$\mathcal{G}_{n}\to\mathcal{G}$ in the local-global sense, then
$\varphi_{\mathcal{G}_{n},f}\rightarrowtail\varphi_{\mathcal{G},f}$.

###### Proof.

For sake of brevity, let $\varphi_{n}=\varphi_{\mathcal{G}_{n},f}$,
$\varphi=\varphi_{\mathcal{G},f}$, $Q^{n}_{k}=Q_{k}(\varphi_{n})$ and
$Q_{k}=Q_{k}(\varphi)$. We need to prove that for all $k$, $Q^{n}_{k}\to
Q_{k}$ in the Hausdorff distance. In other words, we need to show the
following:

  1. (i)

if $a\in Q_{k}$, then there exists $a_{n}\in Q^{n}_{k}$ such that $a_{n}\to
a$,

  2. (ii)

if $a_{n}\in Q^{n}_{k}$ and $a_{n}\to a$, then $a\in\overline{Q}_{k}$.

We prove these using the following technical claim.

######  Claim 3.3.

Let
$(\mathcal{G}_{1},\mathcal{P}_{1}),(\mathcal{G}_{2},\mathcal{P}_{2}),\ldots$
be a sequence of edge-coloured graphings with at most $k$ colours that
converges as coloured graphings to the coloured graphing
$(\mathcal{G},\mathcal{P})$ in the local sense. Then,
$\varphi_{n}/\mathcal{P}_{n}$ converges to $\varphi/\mathcal{P}$ in
$\mathbb{R}^{2^{k}}$.

###### Proof of claim..

For $A\subseteq[k]$, let $\tilde{A}_{n}$ (respectively $\tilde{A}$) denote the
set of edges of $\mathcal{G}_{n}$ (respectively $\mathcal{G}$) with colour in
$A$. Clearly, $\varphi_{n}(\tilde{A}_{n})=(\varphi_{n}/\mathcal{P}_{n})(A)$,
and similarly for $\varphi$, $\mathcal{P}$, and $\tilde{A}$. We denote by
$\mathcal{H}_{A,n}$ the subgraphing of $\mathcal{G}_{n}$ with edge set
$\tilde{A}_{n}$, and define $\mathcal{H}_{A}$ similarly. The coloured local
convergence of the sequence $(\mathcal{G}_{n},\mathcal{P}_{n})$ implies that
$\mathcal{H}_{A,n}$ locally converges to $\mathcal{H}_{A}$ for all $A$. As $f$
is continuous with respect to local convergence, we have

$(\varphi_{n}/\mathcal{P}_{n})(A)=\varphi_{n}(\tilde{A}_{n})=f(\mathcal{H}_{A,n})\to
f(\mathcal{H}_{A})=\varphi(\tilde{A})=(\varphi/\mathcal{P})(A),$

concluding the proof of the claim. ∎

Proof of (i). As $a\in Q_{k}$, there is a Borel partition $\mathcal{P}$ of the
edges of $\mathcal{G}$ such that $\varphi/\mathcal{P}=a$. By $\mathcal{P}$
being a Borel partition and by local-global convergence, we can find some
Borel partition $\mathcal{P}_{n}$ of the edges of $\mathcal{G}_{n}$ such that
the sequence $(\mathcal{G}_{n},\mathcal{P}_{n})$ locally converges to
$(\mathcal{G},\mathcal{P})$ as coloured graphings111Usually one defines local-
global convergence using vertex colorings, but edge colorings can also be
approximated, see [17, Proposition 19.15].. By Claim 3.3, the corresponding
$a_{n}=\varphi_{n}/\mathcal{P}_{n}$ converge to $a$.

Proof of (ii). Assume $a_{n}\to a$. For all $a_{n}$, there exists a partition
$\mathcal{P}_{n}$ such that $a_{n}=\varphi_{n}/\mathcal{P}_{n}$. By possibly
taking a subsequence, we may assume that the sequence
$(\mathcal{G}_{n},\mathcal{P}_{n})$ converges locally as coloured graphings.
Let $(\mathcal{G}^{*},\mathcal{P}^{*})$ represent the limit. The graphing
$\mathcal{G}^{*}$ a priori has nothing to do with $\mathcal{G}$ or the
sequence $\mathcal{G}_{n}$ because local-global convergence of the sequence
$\mathcal{G}_{n}$ does not imply a partition $\mathcal{P}$ of the edges of
$\mathcal{G}$ such that $(\mathcal{G},\mathcal{P})$ represents the limit of
$(\mathcal{G}_{n},\mathcal{P}_{n})$. Nevertheless, by completeness, such a
coloured graphing $(\mathcal{G}^{*},\mathcal{P}^{*})$ exists. However, local-
global convergence provides arbitrarily good approximations of
$(\mathcal{G}^{*},\mathcal{P}^{*})$ on $\mathcal{G}$. That is, there exist
Borel-partitions $\mathcal{R}_{n}$ of $\mathcal{G}$ such that the
$(\mathcal{G},\mathcal{R}_{n})$ locally converge to
$(\mathcal{G}^{*},\mathcal{P}^{*})$. By Claim 3.3 applied to the sequence
$(\mathcal{G}_{n},\mathcal{P}_{n})$, we get that
$a=\varphi_{\mathcal{G}^{*}}/\mathcal{P}^{*}$. Let
$b_{n}=\varphi/\mathcal{R}_{n}$. Then, $b_{n}\in Q_{k}$ and applying the claim
to $(\mathcal{G},\mathcal{R}_{n})$ gives $b_{n}\to a$ as well. Thus we get
$a\in\overline{Q}_{k}$ as stated, finishing the proof of the theorem. ∎

With the help of Theorem 3.2, we are ready to prove Theorem 1.1.

###### Proof of Theorem 1.1..

Let $f(\mathcal{G})=\rho_{\mathcal{G}}(E(\mathcal{G}))$ be the graphing
parameter that assigns to every graphing the total rank of its edge set. Then
$\varphi_{\mathcal{G},f}=\rho_{\mathcal{G}}$, and Theorems 3.1 and 3.2
together complete the proof. ∎

###  3.2 Non-continuity for local convergence

Finally, we prove Theorem 1.2, showing that local convergence does not
guarantee quotient-convergence of the matroids.

###### Proof of Theorem 1.2..

Let $(G_{1},G_{2},\dots)$ be a sequence of $3$-regular, $c$-expander graphs
with $|V(G_{n})|=2n$, such that their girth $g_{n}$ tends to infinity. Let
$\mathcal{G}$ be a subsequential local-global limit of $G_{n}$. Note that
$\mathcal{G}$ is a 3-regular treeing. Let $H_{n}=G_{n}\cup G_{n}$, that is,
$H_{n}$ is the disjoint union of two copies of $G_{n}$. Clearly, the sequence
$H_{n}$ locally converges to $\mathcal{G}$ as well. Write $\rho_{G_{n}}$ for
$r_{G_{n}}/|V(G_{n})|$, and similarly for $H_{n}$.

The partition of $H_{n}$ into two copies of $G_{n}$ defines a factor of the
cycle matroid:

$a_{n}\in Q_{2}(H_{n})\subseteq\mathbb{R}^{2^{2}},\ a_{n}(\emptyset)=0,\
a_{n}(\\{1\\})=a_{n}(\\{2\\})=\frac{|V(G_{n})|-1}{2|V(G_{n})|},\
a_{n}(\\{1,2\\})=\frac{2|V(G_{n})|-2}{2|V(G_{n})|}.$

The limit of $a_{n}$ is

$a\in\mathbb{R}^{2^{2}},\ a(\emptyset)=0,\ a(\\{1\\})=a(\\{2\\})=\frac{1}{2},\
a(\\{1,2\\})=1.$

We claim that $a\notin\overline{Q}_{2}(\rho_{\mathcal{G}})$, showing that
$\rho_{H_{n}}\centernot\rightarrowtail\rho_{\mathcal{G}}$. In fact, we will
show that $G_{n}$ cannot have partitions that are $\varepsilon$-approximations
of $a$, which implies $a\notin\overline{Q}_{2}(\rho_{\mathcal{G}})$ by Theorem
1.1.

By the definition of expander sequences, for every $S\subseteq V(G_{n})$ with
$|S|\leq n$, the number of edges connecting $S$ to $V(G_{n})\setminus S$ is at
least $c\cdot|S|$. Let $E(G_{n})=E_{1}\cup E_{2}$ be any 2-partition of the
edges. For $i\in\\{0,1,2,3\\}$, we denote by $V_{i}$ the set of vertices of
$G_{n}$ with degree $i$ in $E_{1}$ and let $m_{i}=|V_{i}|$. Suppose that this
partition results in a quotient closer to $a$ than $\varepsilon$. Then,
$|\rho_{G_{n}}(E_{i})-\frac{1}{2}|<\varepsilon$ for $i=1,2$. Let us note that
$r_{G_{n}}(E_{1})\leq 2n-m_{0}$, and the previous two inequalities imply
$m_{0}/(2n)\leq(1/2+\varepsilon)$. The same bound holds for $m_{3}$.

We get a contradiction by showing that this is not possible if $g_{n}\geq
32/c$ and $\varepsilon<c/32$. We bound the number of $E_{1}$-components as
follows. The number of singletons is clearly $m_{0}$. If an $E_{1}$-component
is not a tree, then it has at least $g_{n}$ vertices, and hence the number of
such components is at most $2n/g_{n}$. Finally, if a component is a non-
singleton tree, then it has at least $2$ vertices off degree $1$, so the
number of such components is bounded by $m_{1}/2$. We get that

$\rho_{G_{n}}(E_{1})\geq
1-\frac{1}{2n}\left(m_{0}+\frac{m_{1}}{2}+\frac{2n}{g_{n}}\right).$

Writing up the analogous inequality for $E_{2}$ and adding up the two
inequalities, we get

$\rho_{G_{n}}(E_{1})+\rho_{G_{n}}(E_{2})\geq
2-\frac{1}{2n}\left(m_{0}+m_{3}+\frac{m_{1}+m_{2}}{2}\right)-\frac{2}{g_{n}}=1+\frac{m_{1}+m_{2}}{4n}-\frac{2}{g_{n}}.$
(3)

Without loss of generality, we may assume that $m_{0}\leq m_{3}$, implying
$m_{0}\leq n$. The neighbours of $V_{0}$ in $G$ are contained in $V_{1}\cup
V_{2}$, and hence

$m_{1}+m_{2}\geq cm_{0}.$

We also have

$m_{1}+m_{2}=2n-m_{0}-m_{3}\geq
2n-m_{0}-\left(\frac{1}{2}+\varepsilon\right)2n=\left(\frac{1}{2}-\varepsilon\right)2n-m_{0}.$

These two inequalities imply

$m_{1}+m_{2}\geq\frac{c}{c+1}\left(\frac{1}{2}-\varepsilon\right)2n.$

Thus, by (3) and the assumptions $g_{n}\geq 32/c$ and $\varepsilon<c/32$, we
get

$\rho_{G_{n}}(E_{1})+\rho_{G_{n}}(E_{2})\geq
1+\frac{c}{2c+2}\left(\frac{1}{2}-\varepsilon\right)-\frac{2}{g_{n}}>1+2\varepsilon,$

contradicting $|\rho_{G_{n}}(E_{i})-\frac{1}{2}|<\varepsilon$ for $i=1,2$. ∎

##  4 Exposed minorizing measures and hyperfinite spanning forests

In this section, we focus on characterizing the exposed points of the base-
polytope of the cycle matroid of a graphing. Recall that for a finite matroid
$M=(E,r)$, the convex hull of its bases is described as

$C_{M}=\left\\{x\in\mathbb{R}^{E}~{}\Big{|}~{}x\geq 0,\ \sum_{e\in A}x(a)\leq
r(A)\text{ for }A\subseteq E,\ \sum_{e\in E}x(e)=r(E)\right\\}.$

Let $\mathcal{G}=(X,E,\mu)$ be a graphing, let $\tilde{\mu}$ denote its edge
measure, and $\rho$ the corresponding rank function. The analytic counterpart
of $C_{M}$ is the convex set of basic minorizing finitely additive measures

$C_{\mathcal{G}}=bmm^{+}(\rho)=\big{\\{}\alpha\textrm{ finitely additive
measure on $E$}~{}\big{|}~{}\alpha\leq\rho,\ \alpha(E)=\rho(E)\big{\\}}.$

In this section we write $C=C_{\mathcal{G}}$ for brevity. If $\mathcal{G}$ has
no infinite components, then $\rho(E)=1$. Furthermore, as
$\alpha\leq\rho\leq\tilde{\mu}$, in fact all $\alpha\in C$ are
$\sigma$-additive measures and they admit Radon-Nikodym derivatives with
respect to $\tilde{\mu}$, denoted by

$f_{\alpha}(x)=\frac{\partial\alpha}{\partial\tilde{\mu}}(x).$

Note that $f_{\alpha}$ takes values in $[0,1]$. If $f_{\alpha}$ is $0$-$1$
valued $\tilde{\mu}$-almost everywhere, then $\alpha$ is clearly extreme in
$C$. In this case there is a corresponding measurable set of edges
$E_{\alpha}=\\{e\in E\mid f_{\alpha}(e)=1\\}\subseteq E$. The first
observation we make is that such $\mathcal{T}=(X,E_{\alpha},\mu)$ is an
essential hyperfinite spanning forest.

######  Lemma 4.1.

If $f_{\alpha}$ is 0-1 valued, then $\mathcal{T}=(X,E_{\alpha},\mu)$ is an
essential hyperfinite spanning forest.

###### Proof.

By $\alpha\leq\rho$, $E_{\alpha}$ contains no cycles, so $\mathcal{T}$ is a
forest. As $\alpha\in\text{bmm}^{+}(\rho_{\mathcal{G}})$, we have
$\rho_{\mathcal{G}}(E_{\alpha})=\rho_{\mathcal{G}}(E)$, and therefore
$\mathcal{T}$ is essential. Also, we have
$\textrm{cost}(\mathcal{T})=\tilde{\mu}(E_{\alpha})=\alpha(E)=\rho_{\mathcal{T}}(E_{\alpha})$,
so $\mathcal{T}$ is hyperfinite by Proposition 2.2. ∎

For an essential hyperfinite spanning forest $\mathcal{T}=(X,F,\mu)$, let
$\alpha_{F}$ denote the measure defined by $\alpha_{F}(A)=\tilde{\mu}(A\cap
F)$. We have the following.

######  Lemma 4.2.

For any essential hyperfinite spanning forest $\mathcal{T}=(X,F,\mu)$ of a
graphing $\mathcal{G}$, $\alpha_{F}$ is in $C$.

###### Proof.

Let $A\subseteq E$ be a Borel subset of the edges of $\mathcal{G}$. Then
$\mathcal{T}_{A}=(X,A\cap F,\mu)$ is a hyperfinite forest and
$\tilde{\mu}(A\cap F)=\textrm{cost}(\mathcal{T}_{A})$. By Proposition 2.2, we
get $\textrm{cost}(\mathcal{T}_{A})=\rho(A\cap F)$. By monotonicity of $\rho$,
this implies $\alpha_{F}(A)\leq\rho(A)$. ∎

######  Remark 4.3.

Observe that in the above argument, the equality $\alpha_{F}(A)=\rho(A)$ holds
if and only if $\rho(A\cap F)=\rho(A)$. This happens exactly when for
$\mu$-almost all $x\in X$ the $A$\- and $(A\cap F)$-components of $x$ have the
same size. In case this size is infinity, the $(A\cap F)$-component does not
need to be the whole $A$-component. In other words, there is equality exactly
when $\mathcal{T}_{A}=(X,A\cap F,\mu)$ is essential in
$\mathcal{G}_{A}=(X,A,\mu)$.

###  4.1 Exposed points

We say that $f_{\alpha}$ is _exposed_ by $g\in L^{1}(E,\tilde{\mu})$ if the
corresponding continuous linear functional $\varphi_{g}$ of
$L^{\infty}(E,\tilde{\mu})$ attains its strict maximum on $C$ at $f_{\alpha}$.
More formally, if for any $\beta\in C$, $\beta\neq\alpha$ we have
$\varphi_{g}(f_{\alpha})>\varphi_{g}(f_{\beta})$. Clearly, exposed points are
extreme. We prove that all exposed points of $C$ are of the form $\alpha_{F}$,
or in other words, all the exposed $f_{\alpha}$ are $0$-$1$ valued.

######  Theorem 4.4.

Let $f_{\alpha}\in C$ be exposed by a function $g\in L^{1}(E,\tilde{\mu})$.
Then, $f_{\alpha}$ is $0$-$1$ valued $\tilde{\mu}$-almost everywhere.

######  Remark 4.5.

Usually, for a convex set $C$ in a topological vector space, a point $x\in C$
is called exposed if there exists a continuous linear functional that attains
its strict maximum at $x$. In our case, $C\subseteq L^{p}(E,\tilde{\mu})$ for
all $p\in[1,\infty]$. For $f_{\alpha}$ to be exposed in $L^{p}(E,\tilde{\mu})$
where $p\neq\infty$, the witness $g$ has to be in $L^{q}(E,\tilde{\mu})$,
where $q$ is the dual pair of $p$, that is, $1/p+1/q=1$. This means that it is
easier to be exposed for higher values of $p$ since there are more functions
in $L^{q}$ for lower values of $q$. It is even easier to be exposed in
$L^{\infty}(E,\tilde{\mu})$, even with the restriction that the linear
functional corresponds to an $L^{1}$ function, and this is enough for our
argument. What is not enough is to be exposed in $L^{\infty}(E,\tilde{\mu})$
in general, because the linear functional might correspond to a finitely
additive measure, and not to a measure whose Radon-Nikodym derivative would be
the witness $g\in L^{1}(E,\tilde{\mu})$.

###### Proof of Theorem 4.4..

We treat $g$ as a weight function on the edges, and our goal is to find a
maximal essential hyperfinite spanning forest $F$ with respect to this weight
function. We write $\alpha_{F}$ for the corresponding measure in $C$, i.e.
$\alpha_{F}(A)=\tilde{\mu}(A\cap F)$ for all measurable $A\subseteq E$. The
algorithm will result in an $F$ satisfying $\alpha_{F}(\\{g\geq
t\\})=\rho(\\{g\geq t\\})$. In a layer-cake integration this implies, for all
$\beta\in C$,

$\int_{E}\vmathbb{1}_{F}\cdot g\ d\tilde{\mu}=\int_{E}g\
d\alpha_{F}=\hat{\rho}(g)\geq\int_{E}g\ d\beta=\int_{E}f_{\beta}\cdot g\
d\tilde{\mu}.$

Then, by the assumption that $f_{\alpha}$ is the unique maximizer, we have
$\vmathbb{1}_{F}=f_{\alpha}$ in $L^{1}(E,\tilde{\mu})$.

We run a version of Kruskal’s greedy algorithm [14] on $\mathcal{G}$. To
handle ties, we fix an arbitrary Borel ordering of $E$ in advance, and
whenever there is a tie in the $g$ values among finitely many edges
considered, we choose the maximal one according to the Borel ordering. The
algorithm constructs Borel edge sets $F_{1}\subseteq F_{2}\subseteq\ldots$,
with $F=\bigcup F_{n}$ being the final output. In the first step, every vertex
simultaneously chooses the incident edge with the highest $g$-value to be
included in $F_{1}$. During the $n^{\mathrm{th}}$ step, every finite component
of $F_{n-1}$ adds the edge with the highest $g$-value from the set of edges
leaving it, and thus we obtain $F_{n}$. In case there is no edge leaving a
finite $F_{n-1}$ component we do not add anything, but observe that in this
component $F$ is already a spanning tree. Also note that infinite components
do not add any edges, but it may happen that a finite component adds an edge
that connects it to an infinite one.

It is not difficult to see that the sets $F_{n}$ are Borel, cycles cannot be
created, and $F$ is essential. We claim that
$\tilde{\mu}(F)=\rho_{\mathcal{G}}(E)$, so $F$ is hyperfinite by Proposition
2.2. Indeed, set up a payment function as follows. In the beginning, every
vertex receives $1$ token. In a general step, every finite connected component
gives $1$ token to the edge it chooses. After the addition of the edges, for
every finite connected component there is exactly one edge who received $2$
tokens. This edge gives $1$ token back to the component, thus ensuring that
every finite component has a token before the next step. Should a finite
$F$-component become spanning in a finite $\mathcal{G}$-component, and
therefore has no use for its token, this token is redistributed equally among
the vertices of this component. In the end, vertices in finite
$\mathcal{G}$-components paid $1-\frac{1}{|\mathcal{G}_{x}|}$ token, and
vertices in infinite $\mathcal{G}$-components paid 1 token. On the other hand
every chosen edge received 1 token, hence
$\rho_{\mathcal{G}}(E)=\tilde{\mu}(F)$ by the Mass Transport Principle. As $F$
is hyperfinite, by Lemma 4.2, we have $\alpha_{F}\in C$.

Let $A_{t}=\\{g\geq t\\}$ and $F_{\geq t}=F\cap A_{t}$. We further observe
that $F_{t}$ is an essential spanning forest of $A_{t}$. That is, for
$\mu$-almost every $x\in X$,

  1. (1)

if the $A_{t}$-component of $x$ is finite, then $F_{\geq t}$ is a spanning
tree inside this component, and

  2. (2)

if the $A_{t}$-component of $x$ is infinite, then its $F_{\geq t}$-component
is also infinite – though it might be smaller.

For (1), note that the edges leaving the $A_{t}$-component all have $g$-values
strictly less than $t$, while being an $A_{t}$-component means that it can be
connected by edges with $g$-value at least $t$. So the algorithm will connect
these points before growing the component any further. For (2), the reasoning
is analogous. The conclusion, however, is different, This is due to the fact
that we cannot guarantee the connectedness of $F_{\geq t}$ inside the
$A_{t}$-component, because the $F_{\geq t}$-components stop growing once they
are all infinite.

By Remark 4.3, (1) and (2) imply $\alpha_{F}(A_{t})=\rho(A_{t})$, completing
the proof of the theorem. ∎

Let us make a couple of remarks.

######  Remark 4.6.

If $f_{\alpha}$ is $0$-$1$ valued, then it is exposed – the witness for this
is simply choosing $g=f_{\alpha}$. In fact, in this case $f_{\alpha}$ is
_strongly exposed_ , i.e. for any sequence $\beta_{n}\in C$ we have
$\varphi_{g}(f_{\beta_{n}})\to\varphi_{g}(f_{\alpha})\Rightarrow||f_{\beta_{n}}-f_{\alpha}||_{p}\to
0$ for all $p\in[1,\infty)$. So Theorem 4.4 characterizes exposed points of
$C$.

######  Remark 4.7.

By the Klee–Straszewicz theorem [13, Theorem 2.1], exposed points are dense
among extreme points of $C$ in the weak∗ topology of
$L^{\infty}(E,\tilde{\mu})$. Moreover, the exposed points determine $C$ as
$C=\overline{\textrm{conv}(\exp(C))}^{w^{*}}$.

###  4.2 Weakly exposed points

Even in finite dimension, extreme points are not necessarily exposed. To see
this, consider the following set in $\mathbb{R}^{2}$:

$S=\big{\\{}(x,y)\mid-1\leq x\leq 1,\ -1\leq y\leq
1\big{\\}}\cup\big{\\{}(x,y)\mid x^{2}+y^{2}\leq 1\big{\\}}.$

Then $(-1,0)$ and $(1,0)$ are clearly extreme points. However, there is a
unique supporting hyperplane through any of them: $x=-1$ through $(-1,0)$ and
$x=1$ through $(1,0)$, hence these points are not exposed. Nevertheless, these
extreme points can be exposed in finitely many steps by iteratively
restricting the problem to the intersection of the convex set and a supporting
hyperplane. In this subsection, we use this idea to generalize Theorem 4.4 to
extreme points that we call _weakly exposed_.

We say that an extreme point $x\in C$ is _exposed in two steps_ by $L^{1}$
functions, if one can find $g_{1},g_{2}\in L^{1}(E,\tilde{\mu})$ such that
$\varphi_{g_{1}}(x)$ is maximal in $C$, and $x$ to strictly maximizes
$\varphi_{g_{2}}$ in $C^{\prime}=\\{y\in
C\mid\varphi_{g_{1}}(y)=\varphi_{g_{1}}(x)\\}$. Note that the proof of Theorem
4.4 yields the same conclusion for points that are exposed in two steps. The
only difference is that during the algorithm, we always choose an edge that is
maximal with respect to $g_{1}$, and in case of ties, we choose the one
maximal with respect to $g_{2}$. Finally, if there is still a tie, we decide
according to the Borel ordering we fixed at the beginning.

More generally, let $\alpha\in\omega_{1}$ be a countable ordinal and let
$\mathbf{g}\colon\alpha\to L^{1}(E,\tilde{\mu})$ be a list of functions. Let
us define $\mathbf{g}(x)\in\mathbb{R}^{\alpha}$ by
$f(x)_{\beta}=\mathbf{g}(\beta)(x)$. Then, $\mathbf{g}$ defines a Borel
partial ordering on $C$ based on the lexicographical ordering of the images of
points of $C$ in $\mathbb{R}^{\alpha}$. We denote this ordering by
$<_{\mathbf{g}}$ and call a point $x\in C$ _exposed in $\alpha$ steps_ by the
list $\mathbf{g}$ if $x$ is the unique maxima of $<_{\mathbf{g}}$ in $C$. In
other words, for all $y\in C$ there exists an ordinal $\beta_{y}\leq\alpha$
such that for all $\gamma\leq\beta_{y}$, we have
$\mathbf{g}(\gamma)(x)=\mathbf{g}(\gamma)(y)$ and
$\mathbf{g}(\beta_{y})(x)>\mathbf{g}(\beta_{y})(y)$. We say $x\in C$ is
_weakly exposed_ , if it is exposed in $\alpha$ steps for some countable
ordinal $\alpha$.

######  Theorem 4.8.

Let $f_{\alpha}\in C$ be weakly exposed by a list of functions in
$L^{1}(E,\tilde{\mu})$. Then, $f_{\alpha}$ is $0$-$1$ valued
$\tilde{\mu}$-almost everywhere.

###### Proof.

The proof of Theorem 4.4 holds for weakly exposed points as well by always
choosing the $<_{\mathbf{g}}$-maximal edge. ∎

######  Corollary 4.9.

Weakly exposed points of $C$ are strongly exposed.

In finite dimension, all extreme points of a compact convex set are weakly
exposed. In infinite dimension, however, this is not necessarily true. The
closed unit ball of $\ell^{p}(\mathbb{N})$ for $1<p<2$ in
$\ell^{2}(\mathbb{N})$ has extreme points that are not even support points,
see [23, Example 7.5].

######  Remark 4.10.

The algorithm in the proof of Theorem 4.4 uses an arbitrary Borel ordering $<$
on the edge set. The resulting forest is called the _Wired maximal spanning
forest_ , see [20, Chapter 11]. Usually, such forests are studied with the
ordering coming from iid $[0,1]$ labels on the edges of a countable graph.

##  5 Duality

In this section, we present various observations based on the idea that in an
infinite planar graph, the complement of an essential spanning forest is an
essential spanning forest of the dual.

Roughly speaking, a _planar graphing_ is a graphing $\mathcal{G}=(X,E,\mu)$
whose connected components are planar and are also endowed with a concrete
embedding in a measurable way. The embedding is encoded by specifying the
finite facial cycles of the components, and we assume this collection of edge
sets to be Borel inside the standard Borel space of finite subsets of $E$. For
the precise definition, see [7, Section 3.2]. The component of a $\mu$-random
vertex, together with the embedding is a _unimodular random map_ in the sense
of [1].

We will, in fact, restrict our attention to the case when all facial cycles of
$\mathcal{G}$ are finite, and refer to them as _faces_. The assumption of
$2$-vertex-connectivity and bounded size of faces mentioned in the
Introduction also applies. The fact that the encoding is Borel ensures that we
can talk about the dual graphing $\mathcal{G}^{*}=(X^{*},E^{*},\mu^{*})$,
where $X^{*}$ is the set of faces of $\mathcal{G}$. There is a measure
preserving Borel bijection
$\sigma\colon(E,\tilde{\mu})\to(E^{*},\tilde{mu}^{*})$ that denotes the usual
correspondence: $\sigma(e)$ connects two distinct faces $x_{1}^{*}$ and
$x_{2}^{*}$ if and only if $e$ is a common boundary edge of $x_{1}^{*}$ and
$x_{2}^{*}$. For sake of simplicity, we write $e^{*}=\sigma(e)$ and
$F^{*}=\sigma(F)$ for $F\subseteq E(\mathcal{G})$. For an edge set $F\subseteq
E$, we use the notation $F^{*}=\\{e^{*}\mid e\in F\\}$.

Examples of planar graphings include Schreier graphings of p.m.p. actions of
finitely generated groups with planar Cayley graphs (in particular surface
groups), as well as Palm graphings of planar factor graphs of free invariant
point processes on $\mathbb{R}^{2}$ or $\mathbb{H}^{2}$ [21, Remark 17].

######  Remark 5.1.

For graphings, we usually assume $\mu(X)=1$ for convenience. For finite graphs
this corresponds to normalization by the number of vertices. However, when
duals are considered, this normalization is less natural, since the dual graph
typically does not have the same number of vertices. It would probably be more
natural to normalize by the number of edges which is the same for the two
graphs. Nevertheless, to be consistent with the rest of the paper, we do not
change the normalization, and simply accept that the vertex measure of the
dual graphing is not necessarily 1.

######  Remark 5.2.

Limits of sequences of finite planar graphs are hyperfinite by the Lipton-
Tarjan Planar Separation Theorem [16]. Nevertheless, planar graphings need not
be hyperfinite. In fact, there is a sharp dichotomy between hyperfinite and
non-hyperfinite planar graphings, see [1] and [26].

We define the _cocyclic_ matroid of $\mathcal{G}$ by the infinite analogue of
the usual rank function formula:

$\rho^{D}_{\mathcal{G}}(A)=\rho_{\mathcal{G}}(E\setminus
A)+\tilde{\mu}(A)-\rho_{\mathcal{G}}(E).$

Note that $\rho_{\mathcal{G}}(E)=1$, and $\rho^{D}_{\mathcal{G}}$ is
submodular as it is the sum of a submodular and a modular function. Moreover,
the rank of the full edge set in the cocycle matroid is
$\rho^{D}_{\mathcal{G}}(E)=\tilde{\mu}(E)-\mu(X)$. There is a nice
correspondence between the elements of the associated base-polytopes:

$\alpha\in\text{bmm}^{+}(\rho_{\mathcal{G}})\iff\tilde{\mu}-\alpha\in\text{bmm}^{+}(\rho^{D}_{\mathcal{G}}).$

###  5.1 Duality for hyperfinite planar graphings

For finite planar graphs, the cocycle matroid is the cycle matroid of the
dual. In the Borel setting this holds only for hyperfinite planar graphings.
In fact, we will exploit exactly the discrepancy between $\rho_{\mathcal{G}}$
and $\rho^{D}_{\mathcal{G}^{*}}$ in Subsection 5.2 to prove Theorem 1.9.

######  Remark 5.3.

Theorem 1.8 is actually a reformulation of Euler’s formula, stating that for
any embedding of a finite planar graph, the equality $n-m+f=2$ holds, where
$n$, $m$ and $f$ denote the number of vertices, edges and faces, respectively.
For an planar graphing $\mathcal{G}$ with infinite components, the special
case $\rho^{D}_{\mathcal{G}*}(E)=\rho_{\mathcal{G}}(E)$ translates into
$\tilde{\mu}(E)-\mu^{*}(X^{*})=\mu(X)$, that is, the $2$ in the formula
disappears in the limit.

We present two proofs for Theorem 1.8, one relying on Theorem 4.4, the other
using the Mass Transport Principle.

###### Proof of Theorem 1.8 using Theorem 4.4.

We noted earlier that
$\text{bmm}^{+}(\rho^{D}_{\mathcal{G}^{*}})=\tilde{\mu}-\text{bmm}^{+}(\rho_{\mathcal{G}^{*}})$.
By Theorem 4.4, we know that exposed points of
$\text{bmm}^{+}(\rho_{\mathcal{G}})$ and
$\text{bmm}^{+}(\rho_{\mathcal{G}^{*}})$ are essential hyperfinite spanning
forests of $\mathcal{G}$ and $\mathcal{G}^{*}$, respectively. Note also that
they are in a one-to-one correspondence by complementation. Here we use that
$\mathcal{G}$ and $\mathcal{G}^{*}$ are hyperfinite, to ensure that the
complement is again hyperfinite.

These observations together show that $\text{bmm}^{+}(\rho_{\mathcal{G}})$ and
$\text{bmm}^{+}(\rho^{D}_{\mathcal{G}^{*}})$ have the same set of exposed
points. This implies
$\text{bmm}^{+}(\rho_{\mathcal{G}})=\text{bmm}^{+}(\rho^{D}_{\mathcal{G}^{*}})$,
as they are the weak* closure of the convex hull of the same set, see Remark
4.7. Finally, this implies $\rho_{\mathcal{G}}=\rho^{D}_{\mathcal{G}^{*}}$ by
the fact that a submodular function $\varphi$ is determined by
$\text{bmm}^{+}(\varphi)$ in the sense that
$\varphi(A)=\sup_{\alpha\in\text{bmm}^{+}(\varphi)}\alpha(A)$, see [19,
Corollary 6.10]. The proof of $\rho^{D}_{\mathcal{G}}=\rho_{\mathcal{G}^{*}}$
is analogous. ∎

###### Proof of Theorem 1.8 using the Mass Transport Principle.

By using the definitions of $\rho_{\mathcal{G}}$ and
$\rho^{D}_{\mathcal{G}^{*}}$, and the equalities $\tilde{\mu}^{*}=\tilde{\mu}$
and $\rho_{\mathcal{G}^{*}}(E^{*})=\mu^{*}(X^{*})$, we obtain that
$\rho_{\mathcal{G}}(A)=\rho_{\mathcal{G}^{*}}(A)$ is equivalent to

$\tilde{\mu}(A)=\int_{x\in X}1-\frac{1}{|V(\mathcal{G}^{A}_{x})|}\
d\mu(x)+\int_{x^{*}\in X^{*}}\frac{1}{|V(\mathcal{G}^{*,E^{*}\setminus
A^{*}}_{x^{*}})|}\ d\mu^{*}(x^{*}).$ (4)

To verify the equality, we set up a payment between vertices, faces, and
edges. Motivated by the second integral, every face $x^{*}$ that is in a
finite $(E^{*}\setminus A^{*})$-component pays
$1/|V(\mathcal{G}^{*,E^{*}\setminus A^{*}}_{x^{*}})|$ token to the component.
This way every finite $(E^{*}\setminus A^{*})$-component collects 1 token in
total, and this token is passed on to an edge (chosen in a Borel way) in the
$A$-cycle surrounding the component. We can also make sure that the edges that
get payed, oriented from the component that pays to them, form an acyclic
oriented graph on the components of $E^{*}\setminus A^{*}$. This way the edges
of $A$ that do not receive a payment form a subforest $A^{\prime}\subseteq A$
that has the same connected components in $\mathcal{G}$ as $A$.

Next, every $x\in X$ in a finite $A$-component pays
$1/|V(\mathcal{G}^{A}_{x})|$ token to every $A^{\prime}$-edge in its
component. This way all such vertices pay $1-1/|V(\mathcal{G}^{A}_{x})|$, and
such $A$-edges receive $1$ token in total.

What remains are infinite $A^{\prime}$ components and their vertices. Write
$A^{\prime\prime}$ for this edge set, and $X^{\prime\prime}$ for the vertices.
Then $\tilde{\mu}(A^{\prime\prime})=\mu(X^{\prime\prime})$ by Proposition 2.2,
as $A^{\prime\prime}$ is a hyperfinite treeing on $X^{\prime\prime}$ with
infinite components. In a mass transport formulation, this means that we can
arrange that every vertex in $X^{\prime\prime}$ pays 1 token, and every edge
in $A^{\prime\prime}$ gets 1 token.

Concluding the above, vertices and faces payed in total the right hand side of
(4), while every edge in $A$ received 1, so (4) holds by the Mass Transport
Principle. ∎

###  5.2 A matroid attaining the cost

###### Proof of Theorem 1.9.

As we are in the non-hyperfinite case, the dual $\mathcal{G}^{*}$ has no
$2$-ended components $\mu^{*}$-almost surely. By [7], one can pick a 1-ended
hyperfinite spanning forest $F^{*}\subseteq\mathcal{G}^{*}$. The corresponding
measure $\alpha_{F^{*}}$ is in $\text{bmm}^{+}(\rho_{\mathcal{G}^{*}})$,
implying
$\tilde{\mu}-\alpha_{F^{*}}\in\text{bmm}^{+}(\rho^{D}_{\mathcal{G}^{*}})$.
This measure, considered on $E(\mathcal{G})$, corresponds to $E\setminus F$.
The key idea, also exploited in [7], is that $F^{*}$ being $1$-ended almost
everywhere means that $E\setminus F$ is connected on almost every component of
$\mathcal{G}$. That is, $E\setminus F$ is a treeing of $\mathcal{G}$.
Therefore, $\rho^{D}_{\mathcal{G}^{*}}(E)=\alpha_{E\setminus
F}(E)=\tilde{\mu}(E\setminus F)=\textrm{cost}(\mathcal{G})$, where the last
inequality holds by Theorem 2.1. ∎

###  5.3 Free versus wired spanning forests

Let $\mathcal{G}$ be a graphing with a Borel order $<$ on the edges. We have
already seen in Remark 4.10 that the algorithm for finding bases with respect
to $\rho_{\mathcal{G}}$ produces the wired maximal spanning forest, denoted by
$\mathcal{T}_{w}$. There is a natural counterpart, the _free maximal spanning
forest_. We again refer to [20, Chapter 11] for a thorough overview, with the
caveat that here we treat arbitrary Borel orders on the edge set.

We define the free maximal spanning forest $\mathcal{T}_{f}$ by simultaneously
deleting all edges $e$ of $\mathcal{G}$ for which there exists a cycle $C$
containing $e$ in which $e$ is $<$-minimal. It is straightforward to check
that $\mathcal{T}_{f}$ is acyclic, and all of its components are infinite.
Moreover, $\mathcal{T}_{w}\subseteq\mathcal{T}_{f}$.

###### Proof of Theorem 1.10.

When $\mathcal{G}$ and $\mathcal{G}^{*}$ are dual planar graphings and the
Borel total ordering is the same on $E$ and $E^{*}$, the free maximal spanning
forest of $\mathcal{G}$ is exactly the complement of the wired minimal
spanning forest of $\mathcal{G}^{*}$. ∎

######  Remark 5.4.

Based on Theorem 1.10, one could hope to use the free maximal spanning forest
for arbitrary, not necessarily planar graphings to define an interesting
matroid that goes beyond hyperfinite spanning forests. The problem is that the
free maximal spanning forest built on two different Borel orders might have
different edge measure, and so they cannot form bases of the same matroid. For
example, let $\mathcal{G}$ be the Schreier graphing of a free action of
$F_{2}\times\mathbb{Z}$. Let $<_{1}$ be such that all $F_{2}$-edges are larger
than all $\mathbb{Z}$-edges, and the ordering is reversed for $<_{2}$. Then,
$\mathcal{T}^{<_{1}}_{f}$ contains exactly the $F_{2}$-edges while
$\mathcal{T}^{<_{2}}_{f}$ contains exactly the $\mathbb{Z}$-edges, so their
edge measures are $2$ and $1$, respectively.

#### Acknowledgement.

The authors are grateful to Miklós Abért, Boglárka Gehér, András Imolay, Gábor
Kun, Balázs Maga, Nicolas Monod, Gábor Pete, Carsten Thomassen, Tamás Titkos
and Dániel Virosztek for helpful discussions.

Márton Borbényi was supported by the ÚNKP-23-3 New National Excellence Program
of the Ministry for Culture and Innovation from the source of the National
Research, Development and Innovation Fund (NKFIH). László Márton Tóth was
supported by the NKFIH grant KKP-139502, ”Groups and graph limits”. The
research was supported by the Lendület Programme of the Hungarian Academy of
Sciences – grant number LP2021-1/2021, and by Dynasnet European Research
Council Synergy project – grant number ERC-2018-SYG 810115.

## References

  * [1] O. Angel, T. Hutchcroft, A. Nachmias, and G. Ray.  Hyperbolic and parabolic unimodular random maps.  Geometric and Functional Analysis, 28:879–942, 2018.
  * [2] K. Bérczi, M. Borbényi, L. Lovász, and L. M. Tóth.  Cycle matroids that determine their graphing.  Manuscript, 2024+.
  * [3] K. Bérczi, M. Borbényi, L. Lovász, and L. M. Tóth.  Quotient-convergence of submodular setfunctions.  arXiv preprint arXiv:2406.08942, 2024.
  * [4] N. Bowler, J. Carmesin, and R. Christian.  Infinite graphic matroids.  Combinatorica, 38:305–339, 2018.
  * [5] H. Bruhn and R. Diestel.  Infinite matroids in graphs.  Discrete mathematics, 311(15):1461–1471, 2011.
  * [6] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh, and P. Wollan.  Axioms for infinite matroids.  Advances in Mathematics, 239:18–46, 2013.
  * [7] C. T. Conley, D. Gaboriau, A. S. Marks, and R. D. Tucker-Drob.  One-ended spanning subforests and treeability of groups.  arXiv preprint arXiv:2104.07431, 2021.
  * [8] D. Gaboriau.  Around the orbit equivalence theory of the free groups, cost and $\ell^{2}$ Betti numbers.  Lecture notes.
  * [9] D. Gaboriau.  Coût des relations d’équivalence et des groupes.  Inventiones mathematicae, 139(1):41–98, 2000.
  * [10] H. Hatami, P. Hatami, and J. Hirst.  Limits of boolean functions on f_p^ n.  arXiv preprint arXiv:1308.4108, 2013.
  * [11] D. A. Higgs.  Matroids and duality.  Colloquium Mathematicum, 2(20):215–220, 1969.
  * [12] A. Kechris and B. D. Miller.  Topics in orbit equivalence.  Springer, 2004.
  * [13] V. L. Klee Jr.  Extremal structure of convex sets. ii.  Mathematische Zeitschrift, 69(1):90–104, 1958.
  * [14] J. B. Kruskal.  On the shortest spanning subtree of a graph and the traveling salesman problem.  Proceedings of the American Mathematical society, 7(1):48–50, 1956\.
  * [15] G. Levitt.  On the cost of generating an equivalence relation.  Ergodic theory and dynamical systems, 15(6):1173–1181, 1995.
  * [16] R. J. Lipton and R. E. Tarjan.  A separator theorem for planar graphs.  SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  * [17] L. Lovász.  Large networks and graph limits, volume 60.  American Mathematical Soc., 2012.
  * [18] L. Lovász.  The matroid of a graphing.  arXiv preprint arXiv:2311.03868, 2023.
  * [19] L. Lovász.  Submodular setfunctions on sigma-algebras.  arXiv preprint arXiv:2302.04704, 2023.
  * [20] R. Lyons and Y. Peres.  Probability on trees and networks, volume 42.  Cambridge University Press, 2017.
  * [21] S. Mellick.  The Palm groupoid of a point process and factor graphs on amenable and Property (T) groups.  arXiv preprint arXiv:2101.07238, 2021.
  * [22] J. Oxley.  Matroid Theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [23] S. Simons.  The Hahn–Banach–Lagrange theorem.  Optimization, 56(1-2):149–169, 2007.
  * [24] C. Thomassen.  Planarity and duality of finite and infinite graphs.  Journal of Combinatorial Theory, Series B, 29(2):244–271, 1980\.
  * [25] C. Thomassen.  Duality of infinite graphs.  Journal of Combinatorial Theory, Series B, 33(2):137–160, 1982\.
  * [26] Á. Timár and L. M. Tóth.  A full characterization of invariant embeddability of unimodular planar graphs.  Random Structures & Algorithms, 64(2):320–353, 2024.


# Do we have the time for IRM?:
Service denial attacks and SDN-based defences

Ryan Shah and Shishir Nagaraja
University of Strathclyde
<EMAIL_ADDRESS>
###### Abstract

Distributed sensor networks such as IoT deployments generate large quantities
of measurement data. Often, the analytics that runs on this data is available
as a web service which can be purchased for a fee. A major concern in the
analytics ecosystem is ensuring the security of the data. Often, companies
offer Information Rights Management (IRM) as a solution to the problem of
managing usage and access rights of the data that transits administrative
boundaries. IRM enables individuals and corporations to create restricted IoT
data, which can have its flow from organisation to individual control –
disabling copying, forwarding, and allowing timed expiry. We describe our
investigations into this functionality and uncover a weak-spot in the
architecture – its dependence upon the accurate global availability of _time_.
We present an amplified denial-of-service attack which attacks time
synchronisation and could prevent all the users in an organisation from
reading any sort of restricted data until their software has been re-installed
and re-configured. We argue that IRM systems built on current technology will
be too fragile for businesses to risk widespread use. We also present defences
that leverage the capabilities of Software-Defined Networks to apply a simple
filter-based approach to detect and isolate attack traffic.

##  1 Introduction

Led by the intense desire to sense ubiquitously, measure universally, and
apply data analytics to sensed information in the hope of adding value,
governments, industry, society, and the individual are hastily adopting the
vision of the Internet-of-everything. In the majority of cases the primary aim
is to collect data, apply analytics and sell the intelligence gathered further
on within the ecosystem. In the case of industrial IoT systems, organisations
hope to adopt a data-driven approach towards managing, assessing and verifying
their business workflows. Manufacturing industries are keen to understand how
coarse to very-fine grained measurements about their processes can add value
to their bottom line; service industries are similarly interested in obtaining
fine-grained measurements with the view of moving from a periodic maintenance
cycle to a predictive maintenance cycle – i.e by using automated and sensed
data-driven approaches, firms believe they can predict when components within
a system are showing signs of failure. For instance, a conventional lift
requires periodic inspection and replacement of parts which are most worthy of
operation but that must be replaced in order to achieve a working lift with
high probability until the next maintenance cycle (i.e. high availability).
However, such conventional models of periodic maintenance schedules, tend to
overestimate component failures resulting in excess maintenance expenditure
and missing failures between maintenance cycles. On the other hand, a data-
driven approach where the lift is equipped with speed, weight, cable tension,
and shaft sensors, engenders predictive failure models that promise better
results — machine learning techniques applied to the data streams promise to
detect problems as they unfold and prior to catastrophic component failure.
Thus maintenance cycles can be sparser thus saving money for the maintenance
company.

Nice as these ideas are in theory there are some fundamental challenges with
data management that arise in IoT environments. To generate usable
intelligence from hyperconnected networks of sensors, the defender (network
operator) must collect the information at a centralised location in order to
run machine learning algorithms over their data. A cloud storage option is a
natural choice for such a storage location. However, it isn’t always possible
to run all analytics in a single datacentre. In order to take advantage of
specialist analytics services, typical workflows require IoT data to be sent
across administrative boundaries. So how does an organisation secure data that
is stored beyond the customer’s datacentre.

Microsoft provides a solution to the problem of managing information rights
over data that transfers across administrative boundaries such as data
centres, cloud providers, and managed analytics services. Microsoft proposes
to accomplish this using Azure Rights Management (RMS) technology [7]. RMS can
be used to manage IoT data from any network or IoT hub as long as the data is
stored on an Azure cloud.

RMS hopes to make data behave like physical objects. RMS ensures that the
access control metadata placed on IoT data is enforced on remote files, i.e.
even if the data is moved from its location on the cloud on to a specialist
workstation, a different cloud or data centre, or copied to a data storage
that’s not under the control of an IT organisation. RMS also promises audit
and monitoring support to stored data, for instance, the IoT network operator
is notified when a remotely located datafile is accessed, processed, or moved
to another location where this information can be accessed by someone else.

While much attention within IoT security has been devoted to the analysis of
security and privacy protocols for inter-device and device-hub communication
[9], much less attention has been paid to Rights Management services used by
organisations to manage the huge amounts of data that IoT deployments are
expected to generate. Naturally, the security of these rights management
services is of crucial importance. If the rights management can be
compromised, then at best the IoT network operator will lose control of their
data. Worse still, an attacker might deny access to the IoT network operator
itself, resulting in service-denial attacks on the IoT infrastructure. This
can have serious consequences beyond the mere loss of data.

IoT based telemetry and monitoring drive modern safety regimes where
predictive analytics drives (reduced) maintenance frequency and replace
traditional maintenance cycles. Without measurement data, the safety of the
appliance or system is at risk. Therefore, a denial of service attack on IoT
data can directly lead to a safety compromise. In other words, a security
attack translates into a safety problem. In safety-critical applications, such
as elevators, medical device operation, or drug manufacturing, the absence of
maintenance information might require the appliance to be shut down for safety
reasons, with the possibility of cascading failures further down the
dependency chain.

With RMS, an attacker won’t need to find individual device vulnerabilities to
exploit. Instead, if the network operators rights to their data can somehow be
revoked or suspended, then service denial attacks again RMS can be generalised
across IoT networks without attackers being required to know, understand or
exploit the devices and their vulnerabilities within a target network. In this
paper, we propose service denial attacks on an IoT deployment using the Azure
Rights Management Service.

##  2 Information Rights Management

We introduce Digital Rights Management (DRM) as a precursor to Information
Rights Management, which is derived from DRM, and discuss the successes and
limitations of both types of rights management.

DRM is a collection of technologies developed for restricting the use of
hardware and copyrighted work. This includes the control of access,
modification and distribution of content, and the systems that enforce these
policies [15]. It has allowed for the prevention of unauthorised distribution
of copyrighted digital media, and DRM technologies have been used in a variety
of technologies including, but not limited to: documents, film and music. DRM
has also been used in conjunction with other technologies, such as using
steganography to provide DRM control information over insecure communication
channels [16]. DRM can be generalised into four components - digital rights to
manage, encryption, license management and a DRM-enabled client [12]. A
packaging server is used to distribute license data, domain certificates and
packaged content to other servers which manage the different aspects of a DRM
system. License data is sent to a license server which is used to request and
issue licenses to DRM-enabled clients. Domain certificates are registered with
and issued by a domain controller to the clients, and finally a distribution
server (or multiple) request and deliver the protected content to the clients.

Typically, DRM uses encryption which is applied to the content to be
protected, such that it can only be “unlocked” with the correct key. Key
exchange is a critical part of DRM and requires a root of trust [13]. This
involves the distributor only providing the keys to software, services or
devices it trusts. The distribution of the keys can vary on many factors
including the device, the content and security levels required. It can range
from merely providing keys to devices which share a correct token, to secret
keys embedded in the device used for pairing with advanced levels of
encryption. The primary advantage of DRM is that its existence provides a
level of assurance to the owner when allowing the electronic distribution of
their content.

IRM is derived from DRM and involves technologies that protect sensitive
information from unauthorised access. It started as a feature that allowed
users to control the flow of email and office documents such as word-processed
files or spreadsheets and was expanded to include many other types of data
after 2010. While DRM is primarily used to protect intellectual property from
patent infringement and piracy, IRM focuses on protecting sensitive data —
especially data that is exchanged with external entities outside of its
originating organisation. The main difference between IRM and DRM is that a
true IRM system separates the information from its control such that either
can be accessed, manipulated and distributed separately [3].

IRM encrypts data and applies IRM rules which enforce access policies to allow
or deny specific activities, such as the data being read-only or blocking any
data from being copied from a document. A client who is entitled to access the
sensitive data must first be registered with the IRM server. After the user is
authenticated, the server will download some code to the client device. Every
time the user requests a new document from the server or accesses the existing
document(s) on their device, the code on the device must reauthenticate on the
IRM server. This allows for a key to be downloaded which in turn, decrypts the
document and determines the access policies the client is entitled to. Some
IRM services allow for time-limited offline access privileges, for example to
those who want to peruse documents in places with limited access to the
Internet. The benefit to IRM is that these enforced policies persist even when
data is sent externally, such that IRM sealed documents can remain secure no
matter where they are accessed. With this said, IRM solutions require a client
user to have specialised IRM software installed on their device in order to
access data with IRM protection. For this reason, many organisations limit the
use of IRM protection to data that requires it.

#### Rights management and IoT:

Bauer et al. stress the importance of data provenance throughout the life-
cycles of IoT devices to create a trusted and secure IoT environment [4]. They
suggest the use of DRM technologies to control and validate sensitive meta
information such as provenance data. Matthieu and Ramleth propose an alternate
the use of IRM for managing security and access rights within an IoT context
[14]. They propose a cross-domain messaging architecture for IoT devices,
where a remote analytics service performs computations over data supplied by
IoT deployments spanning administrative and organisation boundaries, whilst
restricting the use of the supplied data for the stated purpose. Huckle et al.
[10] identify how IoT and blockchain technologies can use digital rights
management to enable applications that enforce usage rights in the physical
world, such as managing access rights to resources among tenants in a shared
home or within a holiday home.

###  2.1 Limitations

A disadvantage of DRM is that it does not guarantee enforcement in any
fundamental way – once an approve device has access to the data, a large
number of side-channel attacks can be mounted. Further, the restrictions can
result in a significant insult rate as the rights management system tries to
distinguish between legitimate and illegitimate users [13]. While consumers
may feel insulted at treated as a potential pirate user, in a majority of
cases, DRM does not prevent data exfiltration and in turn, demonstrates a lot
of inconvenience to the consumers while attempting to provide a theoretical
level of protection to content distributors. As well as this, the extra costs
of the development and maintenance of DRM systems has sometimes meant that
paying customers had to spend more money to ultimately receive a worse
functioning product than a copy of the same product that doesn’t use DRM.
Although DRM covers the protection of proprietary data; it does not
effectively protect the needs of an industrial (or enterprise) IoT deployment.
Therefore, an IoT deployment would need more appropriate technology when it
comes to protecting and sharing its sensitive data. IRM concentrates on these
needs and uses end-to-end encryption to manage individual permissions and
usage rights. To this end, Furlong and Cookson proposed methods for managing
rights access in a transparent manner [6], with a balance between the fraud
rate and the insult rate.

Like its predecessor, IRM also has limitations. It was designed to not only
manage access rights to data but also control the interactions of the
consumers of the data to enforce some of these rights. However, IRM cannot
prevent side-channel attacks. For instance, anyone capturing a photograph of
the data once it has been accessed and displayed on a device. IRM also
disallows the use of built-in snapshot features to prevent digital capture
from the same device, but with the constant advance in technology, however, it
is practically impossible for IRM systems to prevent third-party software from
capturing snapshots. Further, IRM does not prevent data-exfiltration attacks
by malware. If an attacker has stolen the credentials of someone who has
legitimate access to IRM-protected data, an IRM system has no ability to
prevent the data being accessed by the attacker. Aside from attackers, IRM
cannot prevent domain administrators from accessing the data - which suggests
that on an internal level within an organisation using IRM protection for its
data, there must be a higher level of assurance with technical staff.

###  2.2 Availability Attacks on DRM Systems

Previous work has noted the need for scalability and resilience of online DRM
service components. Federrath [5] and Arnab et al. [2] note that DRM systems
require authentication with an online rights management server and highlight
the need for scalable server-side DRM components [11, 8]. If this server
suffers from an outage then legitimate consumers of the DRM system will be
unable to access the data protected by the DRM system. Much more recently,
Zhang conducted a survey[17] report that the use of DRM in particular Ubisoft
applications resulted in legitimate users being denied access due to a severe
outage to the Ubisoft DRM. All these works point to the need for a scalable or
global-scale architectures for DRM deployment that can withstand the
challenges of servicing DRM clients. With the advent of IoT, the challenge
becomes even more start — Can digital rights management technology offer the
super-scaled architectures required by upcoming IoT deployments?

##  3 Architecture

Azure Rights Management (RMS) is a cloud-based service which can be used to
control the flow of data from devices to the cloud, such that authorised IoT
devices and related services can send, receive and manipulate the data, while
others are denied access. Before data is sent to the cloud, it is encrypted on
the device at the application level, with a policy which defines authorised
use of the data. Some IoT devices may already have several policies pre-
packaged with the device, dependant on the nature of its use. The policy is
typically used to restrict the readability of the data, and restrict copying
and editing only to other devices, organisations and services stated in the
policy. When the protected data is accessed by a legitimate user, organisation
or an authorised service, the data is decrypted, and the policy attached to
the data enforce the rights for that authorised entity.

###  3.1 Protecting Data on an IoT Device

An RMS client on the IoT device will initially connect to the Azure RMS
service which authenticates the device using an Azure Active Directory
account. When connected, the authentication is automatic, and the device is
not prompted for credentials. After authentication, the connection is then
redirected to the organisation’s Azure Information Protection tenant. This
issues certificates to let the device authenticate to the RMS service,
allowing it to protect content offline. The certificates are valid for 31 days
provided that the device account is still enabled in the Azure Active
Directory.

When protecting data, the RMS client on the device creates a random content
key and encrypts the data using the key with AES encryption. The encryption is
used for generic protection and native protection when the file is a protected
pdf, text or image file (.ppdf, .ptxt and .pjpg respectively). The client then
creates a certificate which includes a policy which defines the rights and
restrictions of the data, such as an expiration date. The RMS client on the
device uses the organisation’s key, which was obtained during the
initialisation period for the device, to encrypt the policy and the content
key. During this time, the RMS client also signs the policy with the
certificate already on the device from initialisation. Finally, the client
embeds the policy within the encrypted data, allowing the data to be stored
and shared anywhere through any means of storage and transmission.

Figure 1: Azure RMS IoT Architecture Diagram [1]

###  3.2 Accessing RMS-Protected Data

When an authorised entity, such as those performing predictive analysis, wants
to access the time-expiring data, the RMS client attached to the service sends
the encrypted policy and certificates to the Azure Rights Management Service.
The service decrypts and evaluates the policy such that a list of rights is
obtained specific to the service. The content key is extracted from the
decrypted policy and is then encrypted with the RMS client’s public RSA key
obtained with the request. The content key is then embedded into a use license
with the user rights and is returned to the RMS client. Finally, the RMS
client attached to the predictive analysis service receives the encrypted use
license and decrypts it using its private key, which also, in turn, decrypts
the rights list which is enforced when the data is accessed. The predictive
analysis service can use the data in many ways, such as running machine and
deep learning on the data to learn and make relevant intelligent decisions.

##  4 Denial-of-Service Attacks

During initial experiments with Azure’s IRM system (i.e. RMS) it was
discovered that changing the clock on the RMS client resulted in it
experiencing stability problems. In particular, when the time on the client
was moved forward by 2 hours the RMS client system crashed and no applications
could view or create IRM protected documents. The only workable way to recover
was to re-install the RMS system on the client and reboot. We hypothesise that
the reason the RMS crashed was related to the behaviour of such protection
measures, and some form of time-shifting protection would continue to be
necessary in future versions of the Azure RMS client software. To confirm the
hypothesis, we repeated the exercise 25 times. The client crashed on all 25
repetitions giving us confidence that the RMS client crash has a causal link
to the time shift. To confirm with 100% confidence we would ideally require
access to the client source code, however it is closed source at the time of
writing this paper.

This observation caused us to investigate the reliance of the RMS client
system on synchronized, stable and secure time. It is reasonable to expect
that future versions of client could stop changes in system time resulting in
client becoming unusable. However, since RMS permits time-limited data, it was
clear that there may be more fundamental dependencies on system time.

The (Azure) RMS client does not need to be connected to the RMS server in
order to read RMS protected data, since the client caches keys locally and
uses these when the server cannot be contacted. If, once granted, the right to
read a document cannot be revoked then this local caching would not be a
problem, however in the case of time-limited documents the client must be
responsible for correctly expiring keys and re-requesting them from the
server. An obvious way of bypassing the RMS time-limitation restrictions is
for a client to initially open a document within the time period that they are
permitted to have access, so as to obtain a key. Then by manipulating the
local clock, we prevented this key from expiring and so continuing to have
access of the document, even after the time their access should have been
revoked.

In general, these kind of abuses are well known in relation to time-limited
demos of software, and there are a number of ways of making attacks more
difficult. Since a computing device has no inherent way of maintaining secure
time outside of periodic insecure updates from an external NTP service, these
techniques primarily rely on software watching for unexpected behaviour of the
system clock. If this is detected then access to the protected content is
prevented, although it may be regained if the correct time can then be
confirmed remotely.

Software to detect time-shifting within the OS is typically protected by code
obfuscation and related techniques that apply a graceful return to a correct
clock. While these may be theoretically bypassed, good techniques exist which
would make this task difficult. Our focus was not so much the myriad ways of
continuing to read content after the associated RMS policy denies this access.
Instead we considered denial-of-service attacks which use the RMS protection
which would prevent users from getting access to protected content, even if
the RMS system should allow them.

These attacks centered on the fact that the computing devices on which Azure
runs uses SNTP (Simple Network Time Protocol) to synchronise clients to the
master clock. Windows used this to synchronize systems to their domain
controller, since secure synchronised time over a network was required for the
use of Kerberos within Active Directory as an authentication protocol. Windows
8 and Windows 10 extended this to all machines, by setting systems to
synchronize with time.windows.com if no domain controller is set.

We observed network traffic between a RMS client and the time synchronisation
server. We found that the optional digital signature of time update packets
from the server was not used. This decision is understandable since the
current standard for authenticated NTP uses symmetric cryptography and so
would allow any machine able to authenticate time updates to also spoof them.
This situation would be acceptable where all clients trust every other client
and the server, but not the network, however this is not the case with all
Windows devices.

As expected, by spoofing DNS and directing requests for time.windows.com to a
machine with a SNTP server under our control allowed us to change the clock on
the client machine. However since the RMS client checks time on a weekly basis
it would be necessary to take control of the DNS server for a long period of
time to change the clock on a significant number of machines. This would be a
difficult task to do on a large scale since eventually any attempt to
manipulate clocks would be noticed, particularly if it resulting in IRM
stopping working.

In order to amplify this attack we investigated ways for this attack to be
performed either on a shorter scale by forcing clients to update, or without
requiring DNS to be taken over. Our initial attempt was to flood the network
with broadcast NTP packets.

Figure 2: NTP Broadcast Flooding

This did not succeed in changing the time on the clients, we believe for two
reasons. Firstly it seems that a RMS machine only listens for time updates for
a short period after it sends out an update request. This only occurs every 7
days by default, so machines are only accepting updates for a tiny proportion
of the time. Secondly while there is no nonce in NTP packets, the request and
reply both include the current time of the client to millisecond precision.
The Windows implementation of the NTP client only seems to accept NTP replies
with the same client time as it included in the request and since the lower
order bits of this are sufficiently unpredictable, a flood approach unlikely
to succeed.

The case of where a RMS machine is part of a domain is slightly different.
According to the Windows Time Service documentation a MAC key will be
negotiated between the domain controller and the client, and this will be used
to sign NTP update packets. In our tests, we saw NTP packets sent without MACs
however it is not clear whether this is due to a peculiarity of our domain
controller. Additionally we noted that when the RMS client could not contact
the domain controller for NTP updates, it contacted the DNS server. Both these
observations point to the fact that the RMS client implementation is not based
on the design principle of secure-by-default.

Since in the domain case, time requests are sent to a machine which then gets
updates from time.windows.com, one opportunity for amplification is to put all
resources into causing the domain controller to have the incorrect time.

Figure 3: Inducing Incorrect Time on Controller

We found that this propagates to clients, and so causes the problems with IRM
already mentioned. Furthermore, the Windows Time service documentation states
that if a client detects it is out of sync with the domain controller then it
will update automatically. We found that by changing the domain controller
time, the time on all clients will be changed in a short time period by the
next update cycle. To automate this part of the attack, we generated spoofed
packets in response to NTP packets sent out by the domain controller
purporting to come from the Windows Time Service (the destination IP being
copied from the UDP request packet). Each spoofed packet carried an offset of
four minutes which was accepted by controller. The default pollrate set on the
domain controller is 4096 seconds, thus requiring just over a day to induce
significant drift.

#### Defences

The above DoS attacks depend on the attacker being able to send spoofed SNTP
packets to the RMS client. Software-Defined Networks (SDN) can help mitigate
the attack by implementing a simple threshold-based approach – reject any NTP
response packets reporting a time offset approaching the Kerberos ticket
expiration time. Unlike conventional switches, an SDN switches can be
programmed using an SDN controller that manages the control plane while the
switch focuses on fast packet-forwarding. The controller runs on a server or a
desktop computing device. SDN developers can write programs that secure and
automate routing logic at the core of the network instead of pushing this work
to firewalls installed at the edge of the network. We experimented with a
programmable PICA8 3290 hardware switch that acted as the gateway to an RMS
client (version 2.1) installed on a desktop device running Windows 10. We
programmed the switch using a Ryu controller to buffer all NTP packets and
redirect them to a switch NTP proxy-server process listening on port 2100.
PICA 3290 is a Linux-based switch hence it is capable of running Linux
binaries, hence exhibiting intelligence as opposed to a conventional SDN model
where all the intelligence resides on the controller. We wrote socket code on
the switch to drop any NTP packets where the combined values of NTP offset and
NTP delay is more than four minutes. Five minutes is the threshold beyond
which Kerberos rejects client authentication requests as the tickets expire.

To test the proposed defense, we generated spoofed NTP packets using the SCAPY
tool, purporting to come from the Windows Time Service. We tested with a range
of server offsets between 30 and 600 seconds. The defense-enabled SDN switch
was able to blackhole NTP packets whose combined offset and delay values were
over four minutes with zero false-positives. Our experiments demonstrate that
it is possible to mitigate attacks using SDN approaches. However, an attacker
can successfully counter our defense by lowering the threshold of change — by
slowly increasing the NTP offset say at the rate of 30 seconds at each polling
interval. Better statistical approaches might address this weakness. This will
be the subject of future work.

##  5 Conclusions

In this work, we have highlighted the importance of maintaining secure control
of IoT data as it transcends administrative boundaries. We have examined a
popular approach for achieving this, namely via a cloud-based rights
management service from a prominent software company. We detail several
successful service denial attacks via tampering the time service on which the
digital rights management depends. We report that the attacks are successful
on every attempt without exception. It is particularly noteworthy that even if
IRM system deployed by RMS is made fully scalable, Denial-of-Service attacks
can be mounted by local adversaries with very little resources. This is a
result that has important implications — when system safety is a function of
availability, then a DoS attack on data availability, can escalate into a
safety failure, forcing the operator to engage in an emergency shutdown
procedure.

##  6 Acknowledgements

The authors gratefully acknowledge funding from EPSRC, UK.

## References

  * [1] Microsoft Azure RMS documentation.  https://docs.microsoft.com/en-us/azure/information-protection/what-is-azure-rms.  Accessed: 24/11/2018.
  * [2] A. Arnab and A. Hutchison.  Security considerations for an idealised drm framework.  In Proceedings of the South African Telecomunication Networks and Applications (SATNAC) Conference, volume 2004, 2004.
  * [3] W. S. Bartlett, N. Z. Stahl, and R. S. Brooks.  Information rights management, Dec. 24 2009.  US Patent App. 12/487,353.
  * [4] S. Bauer and D. Schreckling.  Data provenance in the internet of things.  In EU Project COMPOSE, Conference Seminar, 2013.
  * [5] H. Federrath.  Scientific evaluation of drm systems.  2002\.
  * [6] J. Furlong and R. Cookson.  Digital rights management for media streaming systems, Oct. 19 2006.  US Patent App. 11/107,957.
  * [7] M. Grothe, C. Mainka, P. Rösler, and J. Schwenk.  How to break microsoft rights management services.  In WOOT, 2016.
  * [8] T. Hauser and C. Wenz.  Drm under attack: weaknesses in existing systems.  In Digital Rights Management, pages 206–223. Springer, 2003.
  * [9] M. M. Hossain, M. Fotouhi, and R. Hasan.  Towards an analysis of security issues, challenges, and open problems in the internet of things.  In Services (SERVICES), 2015 IEEE World Congress on, pages 21–28. IEEE, 2015.
  * [10] S. Huckle, R. Bhattacharya, M. White, and N. Beloff.  Internet of things, blockchain and shared economy applications.  Procedia computer science, 98:461–466, 2016.
  * [11] P. Koster, F. Kamperman, P. Lenoir, and K. Vrielink.  Identity-based drm: personal entertainment domain.  In Transactions on Data Hiding and Multimedia Security I, pages 104–122. Springer, 2006.
  * [12] W. Ku and C.-H. Chi.  Survey on the technological aspects of digital rights management.  In International Conference on Information Security, pages 391–403. Springer, 2004.
  * [13] D. T. Ltd.  Secure implementation of content protection schemes on consumer electronic devices.
  * [14] C. Matthieu and G. Ramleth.  Security and rights management in a machine-to-machine messaging system, July 28 2015.  US Patent 9,094,407.
  * [15] W. Rosenblatt, S. Mooney, and W. Trippe.  Digital rights management: business and technology.  John Wiley & Sons, Inc., 2001.
  * [16] D. M. Van Wie and R. P. Weber.  Steganographic techniques for securely delivering electronic digital rights management control information over insecure communication channels, Sept. 10 2002.  US Patent 6,449,367.
  * [17] X. Zhang.  A survey of digital rights management technologies.  last modified: Nov, 28:1–10, 2011.