The matroid of a graphing L szl Lov sz††Alfréd Rényi Institute of Mathematics.
Research supported by ERC Synergy Grant No. 810115.

###### Abstract

Graphings serve as limit objects for bounded-degree graphs. We define the
“cycle matroid” of a graphing as a submodular setfunction, with values in
$[0,1]$, which generalizes (up to normalization) the cycle matroid of finite
graphs. We prove that for a Benjamini–Schramm convergent sequence of graphs,
the total rank, normalized by the number of nodes, converges to the total rank
of the limit graphing.

###### Contents

  1. 1 Introduction
  2. 2 $\mathcal{B}$-partitions
    1. 2.1 The semilattice of $\mathcal{B}$-partitions
    2. 2.2 Re-randomization
  3. 3 A supermodular function on partitions
  4. 4 Cycle matroids of graphings
    1. 4.1 Graphing basics
    2. 4.2 The rank function
    3. 4.3 Bases and minorizing measures
    4. 4.4 Beginnings of a limit theory
  5. References

##  1 Introduction

Graphings serve as limit objects for bounded-degree graphs [3, 14]. They can
be defined as Borel graphs on a Borel probability space with a certain
measure-preservation property. Our goal is to extend the definition of the
cycle matroid of a graph to graphings.

In the cycle matroid of a finite graph $G=(V,E)$, the rank of a set
$X\subseteq E$ is determined by the partition $\mathcal{P}$ of the subgraph
$(V,X)$ into connected components: we have $r(X)=|V|-|\mathcal{P}|$. This rank
function is submodular:

$r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)\qquad(X,Y\subseteq E).$ (1)

Let us also remark that a set $X$ is independent in this matroid if and only
if the rank function $r$, restricted to $X$, is just the cardinality function.

One could introduce the rank function on the edge-set of a graphing by
defining it for finite subsets $X$ of the edge set as in the cycle matroid of
the graph formed by $X$ (ignoring isolated nodes). One could extend the rank
function to infinite sets of edges by giving it the value $\infty$. We choose
a perhaps more interesting approach, generalizing the normalized rank
function, defined for a finite graph $G=(V,E)$ as $\rho(X)=r(X)/|V|$. Clearly
this function is submodular, with values in $[0,1]$.

The idea of the generalization is the following observation: Let $\mathcal{P}$
be the partition of the node set $V$ into the connected components of subgraph
$(V,X)$. For $v\in V$, we denote by $\mathcal{P}_{v}$ the partition class
containing $v$. Let $\mathbf{u}$ be a uniform random node of $V$, then

${\sf
E}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{u}}|}\Big{)}=\frac{|\mathcal{P}|}{|V|}=1-\rho(X).$
(2)

This definition can be extended almost verbatim to partitions of graphings
into connected component; however, measurability issues and infinite classes
make it technically involved to prove submodularity and other properties. To
define our generalization to the infinite case, we consider a standard Borel
sigma-algebra $(J,\mathcal{B})$, and “measurable” partitions of $J$ into sets
in $\mathcal{B}$, leading to a setfunction defined on these partitions, which
is “submodular” in some sense.

We will be interested in partitions with many finite classes: If all, or
almost all, partition classes are infinite, then the expectation above will be
$0$ and $\rho(X)=1$.

We define the “cycle matroid” of a graphing as a submodular setfunction
defined on Borel subsets of the edge set $E$, with values in $[0,1]$. This
generalizes the (normalized) cycle matroid of finite graphs. The proof of
submodularity is obtained through a more general result about a function
defined on measurable partitions of a Borel space.

What are the “bases” of this generalized matroid? The results of [15] suggest
that these bases could be defined as finitely additive measures (charges)
$\alpha$ on Borel subsets of edges, upper bounded by $\rho$, with
$\alpha(E)=\rho(E)$. We show that certain spanning forests of the graphing do
give rise to such charges, but we don’t have a full characterization.

A next step should be to develop the limit theory for $\rho$. There have been
attempts to define convergence of matroids, at least for special families [5,
11, 6, 13], but these don’t seem to apply to our case.

A sequence of finite graphs with all degrees bounded by $D$ is said to locally
converge to a graphing $\mathbf{G}$, if for every $r\geq 1$, the distribution
of the $r$-ball centered at a random node of $G_{n}$ converges to the
distribution of the $r$-ball centered at a random point of $\mathbf{G}$. (The
notion of convergence of a bounded-degree graph sequence is due to Benjamini
and Schramm [3], with a different construction for the limit object; see [14]
for convergence to graphings.) To develop a limit theory for cycle matroids,
we want to show that if a sequence of bounded-degree graphs $G_{n}$ converges
to a graphing $\mathbf{G}$, then the setfunctions $\rho_{G_{n}}$ converge to
the setfunction $\rho_{\mathbf{G}}$ in some sense. This is not resolved in
this paper; but we do prove that for a Benjamini–Schramm convergent sequence
of graphs, the rank of the edge set, normalized by the number of nodes,
converges to the rank of the limit graphing.

##  2 $\mathcal{B}$-partitions

###  2.1 The semilattice of $\mathcal{B}$-partitions

Let $(J,\mathcal{B})$ be a standard Borel space, let $\mathcal{P}$ be a
partition of $J$, and for $X\subseteq J$, define

$\mathcal{P}(X)=\cup\\{P\in\mathcal{P}:~{}P\cap X\not=\emptyset\\}.$

We say that $\mathcal{P}$ is a $\mathcal{B}$-partition, if
$\mathcal{P}(A)\in\mathcal{B}$ whenever $A\in\mathcal{B}$. For a partition
$\mathcal{P}$ we denote the class containing $x\in J$ by $\mathcal{P}_{x}$.
Clearly $\mathcal{P}_{x}\in\mathcal{B}$ if $\mathcal{P}$ is a
$\mathcal{B}$-partition. We denote by $\mathcal{P}_{\text{\sf fin}}$ the
family of finite subsets of $\mathcal{P}$.

If $\mathcal{P}$ and $\mathcal{Q}$ are partitions of $J$, we denote by
$\mathcal{P}\land\mathcal{Q}$ and $\mathcal{P}\lor\mathcal{Q}$ their meet and
join in the partition lattice.

######  Lemma 2.1.

(a) If $\mathcal{P}$ and $\mathcal{Q}$ are $\mathcal{B}$-partitions, then so
is $\mathcal{P}\lor\mathcal{Q}$. (b) If, in addition, $\mathcal{Q}$ has a
countable number of classes, then $\mathcal{P}\land\mathcal{Q}$ is a
$\mathcal{B}$-partition.

###### Proof.

(a) Let $A\in\mathcal{B}$, and define $U_{0}=A$, and recursively

$U_{k+1}=\begin{cases}\mathcal{P}(U_{k}),&\text{if $k$ is even},\\\
\mathcal{Q}(U_{k}),&\text{if $k$ is odd}.\end{cases}$

Then $U_{k}\in\mathcal{B}$ for all $k$, and so
$(\mathcal{P}\lor\mathcal{Q})(A)=\cup_{k}U_{k}\in\mathcal{B}$.

(b) Let $U=\bigcup_{Q\in\mathcal{Q}}Q\cap\mathcal{P}(Q\cap A)$. We claim that

$(\mathcal{P}\land\mathcal{Q})(A)=\\{x\in
J:~{}\mathcal{P}_{x}\cap\mathcal{Q}_{x}\cap A\not=\emptyset\\}=U.$ (3)

The first equation is trivial. To verify the second, assume that $x\in J$ has
the property that $\mathcal{P}_{x}\cap\mathcal{Q}_{x}\cap A\not=\emptyset$.
Then there is a $y\in\mathcal{P}_{x}\cap\mathcal{Q}_{x}\cap A$. Hence
$y\in\mathcal{P}_{x}$, which implies that $\mathcal{P}_{x}=\mathcal{P}_{y}$.
Furthermore, $y\in\mathcal{Q}_{x}\cap A$ implies that
$\mathcal{P}_{y}\subseteq\mathcal{P}(\mathcal{Q}_{x}\cap A)$, and hence
$x\in\mathcal{P}(\mathcal{Q}_{x}\cap A)$. Since trivially
$x\in\mathcal{Q}_{x}$, we have
$x\in\mathcal{Q}_{x}\cap\mathcal{P}(\mathcal{Q}_{x}\cap A)$, so $x\in U$.
Conversely, if $x\in Q\cap\mathcal{P}(Q\cap A)$ for some $Q$, then clearly
$Q=Q_{x}$, and $x\in\mathcal{P}(\mathcal{Q}_{x}\cap A)$ means that
$\mathcal{P}_{x}$ intersects $\mathcal{Q}_{x}\cap A$, so
$\mathcal{P}_{x}\cap\mathcal{Q}_{x}\cap A\not=\emptyset$.

Now $Q\cap\mathcal{P}(Q\cap A)$ is clearly a Borel set, and since
$\mathcal{Q}$ has a countable number of classes, (3) implies that
$U=(\mathcal{P}\land\mathcal{Q})(A)$ is Borel.

######  Lemma 2.2.

Let $\mathcal{P}$ be a $\mathcal{B}$-partition, $A\in\mathcal{B}$, and let
$A_{k}=\cup\\{P\in\mathcal{P}:~{}|P\cap A|=k\\}$. Then $A_{k}\in\mathcal{B}$
for $k=0,1,\ldots,\infty$.

This lemma implies that $|\mathcal{P}_{x}|$ is a measurable function of $x$
(which may have infinite values). In particular, the union of $k$-element
partition classes is in $\mathcal{B}$, and hence the union
$\mathcal{P}_{\text{fin}}$ of finite classes of $\mathcal{P}$ is in
$\mathcal{B}$.

###### Proof.

We may assume that $(J,\mathcal{B})$ is the sigma-algebra of Borel sets in
$(0,1)$. Let

$C_{k}=\bigcup_{0=r_{0}<r_{1}<\ldots<r_{k}=1\atop
r_{i}\in\mathbb{Q}}\bigcap_{i=0}^{k-1}\mathcal{P}\big{(}A\cap(r_{i},r_{i+1})\big{)}.$

Then $C_{k}$ is a Borel set, which is the union of partition classes with at
least $k$ elements in $A$. So $A_{k}=C_{k}\setminus C_{k+1}$ is also Borel.

Given a partition $\mathcal{P}$, let us call a set $S\in\mathcal{B}$ a finite-
class representative, if $|S\cap P|=1$ for every finite $P\in\mathcal{P}$ and
$|S\cap P|=0$ for every infinite $P\in\mathcal{P}$.

######  Lemma 2.3.

Every $\mathcal{B}$-partition has a finite-class representative.

###### Proof.

Again, assume that $(J,\mathcal{B})=(0,1)$, and for every finite class
$P\in\mathcal{P}$, let $s_{P}$ be its minimal element. It suffices to show
that

$S=\\{s_{P}:~{}P\in\mathcal{P},P\text{ finite}\\}$

is a Borel set. Indeed, the set
$U_{r}=\cup\\{P\in\mathcal{P}:~{}|P\cap(0,r)|=1\\}$ is Borel by Lemma 2.2, and
then so is $U_{r}\cap(\cup\mathcal{P}_{\text{\sf fin}})$. Thus the set

$V_{r}=U_{r}\cap(\cup\mathcal{P}_{\text{\sf
fin}})\cap(0,r)=\big{\\{}s_{P}:~{}P\text{
finite},P\cap(0,r)=\\{s_{P}\\}\big{\\}}.$

is Borel, and hence $S=\cup_{r\in\mathbb{Q}\cap(0,1)}V_{r}$ is a Borel set.

###  2.2 Re-randomization

Now let $\pi$ be a probability measure on $(J,\mathcal{B})$, and let
$\mathbf{u}$ be a random point from $\pi$. If $\mathcal{P}_{\mathbf{u}}$ is
finite, then let $\mathbf{v}$ be a uniform random point of $P$; else, let
$\mathbf{v}=\mathbf{u}$. We say that $\mathbf{v}$ is obtained by re-
randomizing $\mathbf{u}$ along $\mathcal{P}$. We say that $\mathcal{P}$ has
the re-randomizing property, if re-randomizing results in a point distributed
according to $\pi$.

Another way to express this property is that if $\mu_{x}$ is the uniform
distribution on $\mathcal{P}_{x}$ if $\mathcal{P}_{x}$ is finite, and
$\mu_{x}=\delta_{x}$ otherwise, then the mixture of the measurable family
$M=(\mu_{x}:~{}x\in J)$ of measures by $\pi$ is $\pi$ again. It is easy to
check that every partition of a finite set endowed with the uniform
distribution has the re-randomizing property.

The significance of the re-randomizing property for us is expressed by the
following easy fact:

######  Lemma 2.4.

Let $\mathcal{P}$ be a $\mathcal{B}$-partition of $J$ with the re-randomizing
property. Let $f:~{}J\to\mathbb{R}$ be an integrable function such that
$f(x)=0$ if $\mathcal{P}_{x}$ is infinite, and $\sum_{x\in P}f(x)=0$ for every
finite class $P\in\mathcal{P}$. Let $\mathbf{x}$ be a random point from $\pi$.
Then ${\sf E}f(\mathbf{x})=0$.

###### Proof.

Let $\mathbf{y}$ be obtained from $\mathbf{x}$ by re-randomizing along
$\mathcal{P}$. Then ${\sf E}f(\mathbf{y})=0$, since this holds for every
$\mathbf{x}$. Since $\mathbf{y}$ has the same distribution as $\mathbf{x}$,
the lemma follows.

Not every $\mathcal{B}$-partition has the re-randomizing property.

######  Example 2.5.

Let $(J,\mathcal{B},\pi)$ be the $[0,1]$ interval with the Borel sets and the
Lebesgue measure. Partition the interval $[0,1)$ into pairs $\\{x,2x+1/3\\}$,
where $0\leq x<1/3$. Then for a random point $\mathbf{u}$ from $\pi$, we have
${\sf P}(\mathbf{u}\in[0,1/3))=1/3$, but if we re-randomize to get
$\mathbf{v}$, then ${\sf P}(\mathbf{v}\in[0,1/3))=1/2$.

There are two trivial operations on partitions that preserve the re-
randomizing property: we can merge all infinite classes into one, or resolve
all infinite classes into singletons. Let us state two less trivial
constructions.

######  Lemma 2.6.

Let $\mathcal{P}$ and $\mathcal{Q}$ be $\mathcal{B}$-partitions of $J$ such
that $\mathcal{Q}$ is obtained from $\mathcal{P}$ by splitting some of its
finite classes. If $\mathcal{P}$ has the re-randomizing property, then so does
$\mathcal{Q}$.

###### Proof.

Let us do the following experiment: let $\mathbf{u}$ be a random point from
$\pi$; let $\mathbf{v}$ be obtained from $\mathbf{u}$ by re-randomizing along
$\mathcal{P}$; then let $\mathbf{w}$ be obtained by re-randomizing along
$\mathcal{Q}$. Then (by the re-randomizing property of finite partitions)
$\mathbf{w}$ can be obtained by re-randomizing $\mathbf{u}$ along
$\mathcal{P}$, so it has distribution $\pi$. But it can be obtained by re-
randomizing $\mathbf{v}$ along $\mathcal{Q}$. Since $\mathbf{v}$ has
distribution $\pi$, this proves the lemma.

######  Lemma 2.7.

Let $\mathcal{P}$ and $\mathcal{Q}$ be $\mathcal{B}$-partitions with the re-
randomizing property. Then so is $\mathcal{P}\lor\mathcal{Q}$.

###### Proof.

Let us construct a bipartite multigraph $H_{Z}$ for every finite class $Z$ of
$\mathcal{P}\lor\mathcal{Q}$ as follows. Let $V(H_{Z})=U\cup W$, where
$U=\\{P\in\mathcal{P}:~{}P\subseteq Z\\}$ and
$W=\\{Q\in\mathcal{Q}:~{}Q\subseteq Z\\}$. Let $X\in\mathcal{P}$ be connected
to $Y\in\mathcal{Q}$ by $|X\cap Y|$ edges. The edges of $H_{Z}$ can be
identified with the elements of $Z$, and the degree of $X\in V(H_{Z})$ is
$|X|$. It is also clear that $H_{Z}$ is connected by the definition of
$\mathcal{P}\lor\mathcal{Q}$.

Let $\mathbf{u}$ be a random point of $J$ from the distribution $\pi$, and let
$Z$ be the partition class of $\mathcal{P}\lor\mathcal{Q}$ containing
$\mathbf{u}$. Assume that $Z$ is finite. Let us do a random walk on $H_{Z}$
starting at $v^{0}=\mathcal{P}_{\mathbf{u}}$. The distribution $\eta_{Z,k}$ of
the edge used in step $k$ tends to the uniform distribution on all edges of
$H_{Z}$, by standard results on random walks on graphs.

Let $(v^{0},v^{1},\ldots)$ be the sequence of edges of $H_{Z}$ in this random
walk; equivalently, $(v^{0},v^{1},\ldots)$ is a sequence of points in $Z$. It
follows by the re-randomizing property of $\mathcal{P}$ and $\mathcal{Q}$ that
for every $k$, the distribution of $v^{k}$ is just $\pi$. It follows that if
we choose a random point $\mathbf{u}$ from $\pi$ and re-randomize it along
$\mathcal{P}\lor\mathcal{Q}$ to get $\mathbf{v}$, then $\mathbf{v}$ has
distribution $\pi$, so $\mathcal{P}\lor\mathcal{Q}$ has the re-randomizing
property.

##  3 A supermodular function on partitions

Let $\mathcal{P}$ be a $\mathcal{B}$-partition of $J$. Define

$\psi(\mathcal{P})={\sf E}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{u}}|}\Big{)},$
(4)

where $\mathbf{u}$ is chosen from the distribution $\pi$. Here
$1/|\mathcal{P}_{u}|=0$ if $\mathcal{P}_{u}$ is an infinite set. Clearly
$0\leq\psi(\mathcal{P})\leq 1$. Let us note that if $J$ is finite and $\pi$ is
the uniform distribution on $J$, then

$\psi(\mathcal{P})={\sf
E}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{u}}|}\Big{)}=\sum_{A\in\mathcal{P}}\frac{|A|}{|J|}\,\frac{1}{|A|}=\frac{|\mathcal{P}|}{|J|}.$
(5)

It is also clear that $\psi$ is a decreasing function on partitions (it is
smaller on coarser partitions).

Our main lemma is the following.

######  Lemma 3.1.

Let $(J,\mathcal{B},\pi)$ be a standard Borel probability space and let $\psi$
be defined by (4). Let $\mathcal{P}$, $\mathcal{Q}$ and $\mathcal{R}$ be
$\mathcal{B}$-partitions with the re-randomizing property such that
$\mathcal{R}\leq\mathcal{P}$ and $\mathcal{R}\leq\mathcal{Q}$. Then

$\psi(\mathcal{R})+\psi(\mathcal{P}\lor\mathcal{Q})\geq\psi(\mathcal{P})+\psi(\mathcal{Q}).$
(6)

We see that $\mathcal{R}$ is a “proxy” for $\mathcal{P}\land\mathcal{Q}$,
which may not be a $\mathcal{B}$-partition. In the next section, when applying
the lemma to graphons, we can choose $\mathcal{R}$ to be a natural meet of the
partitions $\mathcal{P}$ and $\mathcal{Q}$ (which will not be
$\mathcal{P}\land\mathcal{Q}$).

###### Proof.

$0^{\circ}$ Let us prove the finite case first, when $\mathcal{B}=2^{J}$. We
don’t have to worry about $\mathcal{P}\land\mathcal{Q}$ being a
$\mathcal{B}$-partition, so we can replace $\mathcal{R}$ by
$\mathcal{P}\land\mathcal{Q}$. Let $K_{n}$ be the complete graph on $J$. We
consider a partition $\mathcal{P}$ as a subgraph $G_{\mathcal{P}}$ of $K_{n}$
that is the disjoint union of complete graphs, corresponding to the partition
classes. Then $G_{\mathcal{P}\land\mathcal{Q}}=G_{\mathcal{P}}\cap
G_{\mathcal{Q}}$ and $G_{\mathcal{P}\lor\mathcal{Q}}$ is the transitive
closure of $G_{\mathcal{P}}\cup G_{\mathcal{Q}}$. Furthermore,
$n(1-\psi(\mathcal{P}))$ is the rank of $G_{\mathcal{P}}$ in the cycle matroid
of $K_{n}$. The inequality follows by the submodularity of the rank function
of the cycle matroid.

$1^{\circ}$ As a first step in the proof of the general case, we want to split
the classes of $\mathcal{Q}_{\text{\sf fin}}$ into some subsets, and those
classes in $\mathcal{R}$ contained in a class in $\mathcal{Q}_{\text{\sf
fin}}$ to singletons, so that the inequality to be proved remains equivalent.

Let $S$ be a finite-class representative for $\mathcal{R}$ (which exists by
Lemma 2.3). We split each $Y\in\mathcal{Q}_{\text{\sf fin}}$ into $Y\cap S$
and singleton sets, and let $\mathcal{Q}^{\prime}$ be the partition of $J$
obtained. Let $\mathcal{R}^{\prime}$ be obtained by splitting every class of
$\mathcal{R}$ contained in $\cup\mathcal{Q}_{\text{\sf fin}}$ to singletons.
It is easy to see that
$\mathcal{P}\lor\mathcal{Q}^{\prime}=\mathcal{P}\lor\mathcal{Q}$.

Let $\mathbf{u}$ be a random point from $\pi$, and let $\mathbf{v}$ be
obtained by re-randomizing $\mathbf{u}$ along $\mathcal{Q}$. If
$\mathcal{Q}_{\mathbf{u}}$ is infinite, then no partition class containing
$\mathbf{v}$ changes when replacing $\mathcal{Q}$ by $\mathcal{Q}^{\prime}$.
If $Y=\mathcal{Q}_{\mathbf{u}}$ is finite, then

$\frac{1}{|(\mathcal{P}\lor\mathcal{Q}^{\prime})_{\mathbf{v}}|}=\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{\mathbf{v}}|},\qquad\text{and}\qquad\frac{1}{|\mathcal{R}^{\prime}_{\mathbf{v}}|}=1.$

Using (5), we have

${\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}^{\prime}_{\mathbf{v}}|}\Big{)}=\frac{|Y\setminus
S|+1}{|Y|},\qquad\text{and}\qquad{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}_{\mathbf{v}}|}\Big{)}=\frac{1}{|Y|}.$

Furthermore,

${\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{R}_{\mathbf{v}}|}\Big{)}=\frac{\big{|}\mathcal{R}|_{Y}\big{|}}{|Y|}=\frac{|Y\cap
S|}{|Y|}.$

Combining these equations, we see that

$\displaystyle{\sf E}_{\mathbf{v}}\Big{(}$
$\displaystyle\frac{1}{|(\mathcal{P}\lor\mathcal{Q}^{\prime})_{\mathbf{v}}|}\Big{)}+{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{R}^{\prime}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}^{\prime}_{\mathbf{v}}|}\Big{)}$
$\displaystyle={\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{\mathbf{v}}|}\Big{)}+1-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-\frac{|Y\setminus
S|+1}{|Y|}$ $\displaystyle={\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{\mathbf{v}}|}\Big{)}+\frac{|Y\cap
S|}{|Y|}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-\frac{1}{|Y|}$
$\displaystyle={\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{\mathbf{v}}|}\Big{)}+{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{R}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}_{\mathbf{v}}|}\Big{)}.$

By Lemma 2.4, this implies that this equation holds when $\mathbf{v}$ is
replaced by $\mathbf{u}$, and so

$\displaystyle\psi(\mathcal{R}^{\prime})$
$\displaystyle+\psi(\mathcal{P}\lor\mathcal{Q}^{\prime})-\psi(\mathcal{P})-\psi(\mathcal{Q}^{\prime})=\psi(\mathcal{R})+\psi(\mathcal{P}\lor\mathcal{Q})-\psi(\mathcal{P})-\psi(\mathcal{Q}),$

so considering the pair $(\mathcal{P},\mathcal{Q}^{\prime})$ instead of
$(\mathcal{P},\mathcal{Q})$, we may assume that every class of $\mathcal{R}$
is a singleton.

$2^{\circ}$ Our next goal is to get rid of the non-singleton finite classes of
$\mathcal{P}\lor\mathcal{Q}$. Let $Z$ be the union of all finite classes of
$\mathcal{P}\lor\mathcal{Q}$, and let $\mathcal{P}^{\prime}$ and
$\mathcal{Q}^{\prime}$ be obtained by splitting each class of $\mathcal{P}$
and $\mathcal{Q}$ contained in $Z$ to singletons. It is easy to see that
$Z\in\mathcal{B}$, and that both $\mathcal{P}^{\prime}$ and
$\mathcal{Q}^{\prime}$ are $\mathcal{B}$-partitions. By Lemma 2.6, both
$\mathcal{P}^{\prime}$ and $\mathcal{Q}^{\prime}$ have the re-randomizing
property.

We can write the inequality to be proved as

$\int\limits_{J}f_{\mathcal{P},\mathcal{Q}}(x)\,d\pi(x)\geq 0,$ (7)

where

$f(x)=f_{\mathcal{P},\mathcal{Q}}(x)=\frac{1}{|\mathcal{R}_{x}|}+\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{x}|}-\frac{1}{|\mathcal{P}_{x}|}-\frac{1}{|\mathcal{Q}_{x}|}.$

Let $f^{\prime}=f_{\mathcal{P}^{\prime},\mathcal{Q}^{\prime}}$. Then
$f^{\prime}(x)=f(x)$ if $x\in J\setminus Z$, and $f^{\prime}(x)=0$ if $x\in
Z$. By the finite case treated above, $\int\limits_{Z}f(x)\,d\pi(x)\geq 0$,
and hence

$\int\limits_{J}f(x)\,d\pi(x)\geq\int\limits_{J}f(x)\,d\pi(x).$

So we may replace $(\mathcal{P},\mathcal{Q})$ by
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$; in other words, we may assume
that every class of $\mathcal{P}\lor\mathcal{Q}$ is either infinite or a
singleton set.

$3^{\circ}$ Our next goal is to get rid of non-singleton finite classes
containing a singleton class from the other partition. Let $S$ and $T$ be the
unions of singleton classes of $\mathcal{P}$ and $\mathcal{Q}$, respectively.
For $Y\in\mathcal{Q}$, define

$Y^{\prime}=\begin{cases}Y\setminus S,&\text{if $Y$ is finite},\\\
Y,&\text{otherwise}.\end{cases}$

If $|Y|>1$, then the class of $\mathcal{P}\lor\mathcal{Q}$ is infinite, so
$Y^{\prime}\not=\emptyset$. Let the partition $\mathcal{Q}^{\prime}$ consist
of the nonempty sets $Y^{\prime}$ ($Y\in\mathcal{Q}$), along with those
singleton subsets of $S$ that are contained in finite classes of
$\mathcal{Q}$. We leave $\mathcal{R}$ unchanged.

We argue similarly as in $1^{\circ}$. Let $\mathbf{u}$ be a random point from
$\pi$, and let $\mathbf{v}$ be obtained by re-randomizing $\mathbf{u}$ along
$\mathcal{Q}$. Fix $\mathbf{u}$, and let $Y=\mathcal{Q}_{\mathbf{u}}$. Then If
$Y$ is infinite, then no partition class containing $\mathbf{v}$ changes when
replacing $\mathcal{Q}$ by $\mathcal{Q}^{\prime}$. If $Y$ is finite, then by
$1^{\circ}$, for any point $\mathbf{v}\in Y$,

$\frac{1}{|\mathcal{R}_{\mathbf{v}}|}=1,\qquad\text{and}\qquad\frac{1}{|\mathcal{Q}_{\mathbf{v}}|}=\frac{1}{|Y|},$

and by $2^{\circ}$,

${\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{\mathbf{v}}|}\Big{)}=0.$

Furthermore, by (5),

${\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}^{\prime}_{\mathbf{v}}|}\Big{)}=\frac{|Y\setminus
Y^{\prime}|+1}{|Y|},$

and

${\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|(\mathcal{P}\lor\mathcal{Q}^{\prime})_{\mathbf{v}}|}\Big{)}=\frac{|Y\setminus
Y^{\prime}|}{|Y|}.$

Combining these equations,

$\displaystyle{\sf E}_{\mathbf{v}}\Big{(}$
$\displaystyle\frac{1}{|(\mathcal{P}\lor\mathcal{Q}^{\prime})_{\mathbf{v}}|}\Big{)}+{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{R}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}^{\prime}_{\mathbf{v}}|}\Big{)}$
$\displaystyle=\frac{|Y\setminus Y^{\prime}|}{|Y|}+1-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-\frac{|Y\setminus
Y^{\prime}|+1}{|Y|}=0+1-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-\frac{1}{|Y|}$
$\displaystyle={\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|(\mathcal{P}\lor\mathcal{Q})_{\mathbf{v}}|}\Big{)}+{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{R}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{P}_{\mathbf{v}}|}\Big{)}-{\sf
E}_{\mathbf{v}}\Big{(}\frac{1}{|\mathcal{Q}_{\mathbf{v}}|}\Big{)}.$

As before, this shows that

$\displaystyle\psi(\mathcal{P}\land\mathcal{Q}^{\prime})$
$\displaystyle+\psi(\mathcal{P}\lor\mathcal{Q}^{\prime})-\psi(\mathcal{P})-\psi(\mathcal{Q}^{\prime})$
$\displaystyle=\psi(\mathcal{P}\land\mathcal{Q})+\psi(\mathcal{P}\lor\mathcal{Q})-\psi(\mathcal{P})-\psi(\mathcal{Q}).$

Carrying out the same process with $\mathcal{P}$ and $\mathcal{Q}$
interchanged, we may assume that for every point, three possibilities remain:
it is contained (i) in singleton classes of both partitions $\mathcal{P}$ and
$\mathcal{Q}$, or (ii) in a singleton class and an infinite class, or (iii) in
two non-singleton classes.

In these three cases we have, respectively,

(i): $\displaystyle f_{\mathcal{P},\mathcal{Q}}(x)$ $\displaystyle=1+1-1-1=0,$
(ii): $\displaystyle f_{\mathcal{P},\mathcal{Q}}(x)$
$\displaystyle=1+0-1-0=0,$ (iii): $\displaystyle
f_{\mathcal{P},\mathcal{Q}}(x)$ $\displaystyle\geq
1+0-\frac{1}{2}-\frac{1}{2}=0.$

This proves the Lemma.

##  4 Cycle matroids of graphings

###  4.1 Graphing basics

A graphing is a quadruple $\mathbf{G}=(J,\mathcal{B},E,\lambda)$, where
$(J,E)$ is a graph on the standard Borel sigma-algebra $(J,\mathcal{B})$, $E$
is a symmetric Borel subset of $\binom{J}{2}$, and $\lambda$ is a probability
measure on $\mathcal{B}$. Let $\deg(u)=\deg_{\mathbf{G}}(u)$ denote the degree
of $u\in J$ in the graph $\mathbf{G}$; for $B\subseteq J$, let $\deg_{B}(u)$
denote the number of edges from the point $u\in J$ to $B$; for $X\subseteq E$,
let $\deg_{X}(u)$ denote the number of edges in $X$ incident with $u$. For
$x\in J$, we denote by $\mathbf{G}_{x}$ the connected component of
$\mathbf{G}$ containing $x$.

It is assumed that all degrees of the graph $(J,E)$ are finite and bounded by
an integer $D\geq 0$, and the “measure-preservation” equation

$\int\limits_{A}\deg_{B}(x)\,d\lambda(x)=\int\limits_{B}\deg_{A}(x)\,d\lambda(x)$
(8)

is satisfied for all $A,B\in\mathcal{B}$. This condition is equivalent to
saying that for a random point $\mathbf{x}$ from distribution $\lambda$, the
(connected rooted) graph $(G_{\mathbf{x}},\mathbf{x})$ is an involution-
invariant random rooted graph as defined by Benjamini and Schramm [3].

The quantity

$\overline{d}=\overline{d}_{\mathbf{G}}=\int\limits_{J}\deg(u)\,d\lambda(u)$

is the average degree of the graphing. The setfunction

$\eta(A\times
B)=\frac{1}{\overline{d}}\int\limits_{A}\deg_{B}(x)\,d\lambda(x)$

extends to a probability measure on $\mathcal{B}\times\mathcal{B}$, which we
call the edge measure of $\mathbf{G}$. Clearly $\eta=\eta_{\mathbf{G}}$ is
symmetric (invariant under interchanging the coordinates) and supported on
$E$. We can express $\eta(X)$ for every Borel set $X\subseteq E$ as

$\eta(X)=\frac{1}{\overline{d}}\int\limits_{J}\deg_{X}(u)\,d\lambda(u).$ (9)

In this paper, a subgraphing of a graphing
$\mathbf{G}=(J,\mathcal{B},E,\lambda)$ is a $4$-tuple
$\mathbf{H}=(J,\mathcal{B},F,\lambda)$, where $F\subseteq E$ is a Borel set.
It is not entirely obvious that $\mathbf{H}$ satisfies the graphing axioms;
see Lemma 18.19 in [14]. Equation (9) implies the following expression for the
edge measure of a subgraphing:

$\eta_{\mathbf{H}}(X)=\frac{\overline{d}}{\overline{d}_{\mathbf{H}}}\eta(X)\qquad(X\in\mathcal{B}\times\mathcal{B}).$
(10)

###  4.2 The rank function

An obvious way to define a matroid rank function of a graphing would be to
consider finite subsets of edges, and consider the rank function $r(X)$ of the
cycle matroid of the graph they form. Every infinite set will have infinite
rank. We explore a more interesting possibility, generalizing the normalized
rank of the cycle matroid of a graph $G=(V,E)$ on $n$ nodes.

Let $c(G)$ denote the number of connected components of a graph $G$. Recalling
that $r(X)=n-c(V,X)$, we define

$\rho(X)=\frac{r(X)}{n}=1-\frac{c(V,X)}{|V|}.$

This number is in $[0,1]$. By (5), we can express it as

$\rho(X)=1-{\sf E}_{\mathbf{u}}\Big{(}\frac{1}{|X_{\mathbf{u}}|}\Big{)},$ (11)

where $X_{\mathbf{u}}$ is the set of nodes of the connected component of
$(V,X)$ containing $\mathbf{u}$.

Now this setfunction makes sense in the graphing case as well. Let
$\mathbf{G}=(J,\mathcal{B},E,\lambda)$ be a graphing. For every Borel set
$X\subseteq E$, the quadruple $\mathbf{G}^{X}=(J,\mathcal{B},X,\lambda)$ is a
graphing. We denote by $\mathcal{P}^{X}$ the partition of $J$ into the
connected components of $\mathbf{G}^{X}$. Then we can define

$\rho(X)=\rho_{\mathbf{G}}(X)=1-{\sf
E}_{\mathbf{u}}\Big{(}\frac{1}{|V(\mathbf{G}^{X}_{\mathbf{u}}|}\Big{)}=1-\psi(\mathcal{P}^{X}),$
(12)

where $\mathbf{u}$ is a random point from $\lambda$. We can see from this
definition right away a nice property of $\rho(X)$, namely that it is an
intrinsic parameter of the edge set $X$: if $\mathbf{H}$ is a subgraphing of
$\mathbf{G}$, and $X$ is a Borel subset of $E(\mathbf{H})$, then
$\rho_{\mathbf{H}}(X)=\rho_{\mathbf{G}}(X)$.

Our goal is to apply the results of Section 3 to the partitions of $J$ into
the connected components of sub-graphings, showing that $1-\rho$ is
supermodular, and so $\rho$ is submodular. For this, we need a simple (but not
quite trivial) lemma.

######  Lemma 4.1.

Let $\mathbf{G}=(J,\mathcal{B},E,\lambda)$ be a graphing, and let
$\mathcal{P}$ be the partition of $J$ into the connected components of
$\mathbf{G}$. Then $\mathcal{P}$ is a $\mathcal{B}$-partition with the re-
randomizing property.

###### Proof.

The fact that $\mathcal{P}$ is a $\mathcal{B}$-partition, follows e.g. by
Lemma 18.2 in [14], which asserts that if $A\in\mathcal{B}$, then the
neighbors of $A$ form a Borel set. Repeating this argument, the set $A_{k}$ of
nodes that are at a distance at most $k$ form $A$ is a Borel set, and hence
$\mathcal{P}(A)=\cup_{k}A_{k}$ is Borel.

To prove that $\mathcal{P}$ has the re-randomizing property, let $\mathbf{u}$
be a random point from $\lambda$, let $\mathbf{v}$ be obtained from
$\mathbf{u}$ by re-randomizing along $\mathcal{P}$, and let $\lambda^{\prime}$
be the distribution of $\mathbf{v}$. Let $B=\cup\mathcal{P}_{\text{\sf fin}}$.
Since $\lambda^{\prime}|_{J\setminus B}=\lambda|_{J\setminus B}$ by
definition, it suffices to show that $\lambda^{\prime}(A)=\lambda(A)$ for all
$A\in\mathcal{B}$, $A\subseteq B$. For $x,y\in J$, define

$f(x,y)=\begin{cases}1/|V(\mathbf{G}_{x})|,&\text{if $x\in B$ and $y\in A\cap
V(G_{x})$,}\\\ 0,&\text{otherwise}.\end{cases}$

Then

$\sum_{y}f(x,y)=\begin{cases}\displaystyle\frac{|V(\mathbf{G}_{x})\cap
A|}{|V(\mathbf{G}_{x})|},&\text{if $x\in B$},\\\
0,&\text{otherwise},\end{cases}$

and

$\sum_{x}f(x,y)=\begin{cases}1,&\text{if $y\in A$},\\\
0,&\text{otherwise}.\end{cases}$

By the Mass Transport Principle (in the form of [14], Proposition 18.49),

$\displaystyle\lambda(A)$
$\displaystyle=\int\limits_{J}\sum_{x}f(x,y)\,d\lambda(y)=\int\limits_{J}\sum_{y}f(x,y)\,d\lambda(x)$
$\displaystyle=\int\limits_{B}\frac{|V(\mathbf{G}_{x})\cap
A|}{|V(\mathbf{G}_{x})|}\,d\lambda(x)={\sf P}(u\in B,u^{\prime}\in
A)=\lambda^{\prime}(A).$

This proves the re-randomizing property of $\mathcal{P}$.

Another simple fact we need is the following.

######  Lemma 4.2.

The setfunction $\rho=\rho_{\mathbf{G}}$ defined by (12) satisfies

$\frac{\overline{d}}{1+D}\eta(X)\leq\rho(X)\leq\overline{d}\eta(X).$

for all $X\in\mathcal{B}\times\mathcal{B}$.

###### Proof.

Clearly $|V(\mathbf{G}^{X}_{u})|\geq 1+\deg_{X}(u)$, and hence

$1-\frac{1}{|V(\mathbf{G}^{X}_{u})|}\geq
1-\frac{1}{1+\deg(u,X)}=\frac{\deg(u,X)}{1+\deg(u,X)}\geq\frac{\deg(u,X)}{1+D}.$

On the other hand,

$1-\frac{1}{|V(\mathbf{G}^{X}_{u})|}\leq\deg(u,X),$

since both sides are zero if $\deg(u,X)=0$, and the left hand side is at most
$1$ and the right hand side is at least $1$ otherwise. Taking expectation, and
using (9), we get the inequalities in the lemma.

Let us state some nice properties of the setfunction $\rho$ (see [15] for more
on these properties and their relevance). We say that a setfunction
$\varphi:~{}\mathcal{B}\to\mathbb{R}_{+}$ is strongly bounded, if there is a
(finite) measure $\alpha$ such that $\varphi\leq\alpha$. It is continuous from
above, if for every sequence $A_{1}\supseteq A_{2}\supseteq\ldots$ of sets
$A_{i}\in\mathcal{B}$ and $A=\cap_{i}A_{i}$, we have
$\varphi(A_{n})\to\varphi(A)$ $(n\to\infty)$. It is absolutely continuous with
respect to a measure $\pi$, if for every $\varepsilon>0$ there is a $\delta>0$
such that $\pi(S)<\delta$ implies that $|\varphi(S)|<\varepsilon$ for every
$S\in\mathcal{B}$.

######  Theorem 4.3.

The setfunction $\rho$ defined on the Borel subsets of $E$ by (12) is
increasing and submodular. In addition, it is strongly bounded, continuous
from above and absolutely continuous with respect to a measure $\eta$.

###### Proof.

To prove submodularity, we use Lemma 3.1. Equivalently, we want to prove that
$\psi(\mathcal{P}^{X})$ is a supermodular setfunction of $X$:

$\psi(\mathcal{P}^{X\cup Y})+\psi(\mathcal{P}^{X\cap
Y})\geq\psi(\mathcal{P}^{X})+\psi(\mathcal{P}^{Y}).$ (13)

Here $\mathcal{P}^{X\cup Y}$ etc. are $\mathcal{B}$-partitions with the re-
randomizing property by Lemma 4.1. Furthermore, $\mathcal{P}^{X\cup
Y}=\mathcal{P}^{X}\lor\mathcal{P}^{Y}$. In general, we will not have
$\mathcal{P}^{X\cap Y}=\mathcal{P}^{X}\land\mathcal{P}^{Y}$, but
$\mathcal{R}=\mathcal{P}^{X\cap Y}$ satisfies $\mathcal{R}\leq\mathcal{P}^{X}$
and $\mathcal{R}\leq\mathcal{P}^{Y}$, so Lemma 3.1 proves (13).

The smoothness properties are trivial by Lemma 4.2.

###  4.3 Bases and minorizing measures

Bases of the cycle matroid of a graph are spanning forests, so we expect that
bases of the matroid of a graphing (if meaningful at all) will be connected to
spanning trees. It is suggested in [15], that the “bases” for a general
increasing submodular setfunction $\varphi$ with $\varphi(\emptyset)=0$ should
be minorizing charges, i.e., nonnegative finitely additive measures $\alpha$
on $\mathcal{B}$ such that $\alpha\leq\varphi$.

It was proved (under somewhat different conditions) by Choquet [8] and Šipoš
[21] (see also [10], Chapter 10), that for every increasing submodular
setfunction $\varphi$ defined on Borel sets with $\varphi(\emptyset)=0$ and
every family $\SS$ of Borel sets that is totally ordered by inclusion, there
is always a minorizing charge $\alpha$ with $\alpha(J)=\varphi(J)$. In our
case, Theorem 4.3 implies that every minorizing charge for $\rho$ is in fact
countably additive. See [15] for other matroid-like properties of minorizing
measures, like Steinitz exchange, greedy algorithm, intersection, etc.

So we expect that spanning forests give rise to minorizing measures. In the
finite case, if $X\subseteq E$ is a spanning forest, then $\rho(Y)=|Y|/|V|$
for every $Y\subseteq X$, and so $\rho$ is additive on $X$. This does not hold
for graphings in general (see Example 4.6), but we can prove this at least in
a special case. We say that a graphing $\mathbf{G}=(J,\mathcal{B},E,\lambda)$
is hyperfinite, if for every $\varepsilon>0$ there is a Borel set $X\subseteq
E$ with $\eta(X)<\varepsilon$ such that all connected components of
$\mathbf{G}\setminus X$ are finite.

######  Lemma 4.4.

Let $\mathbf{G}=(J,\mathcal{B},E,\lambda)$ be a hyperfinite graphing such that
every connected component is a tree. Then for all Borel sets $U\subseteq E$,
we have $\rho(U)=(\overline{d}/2)\eta(U)$.

In particular, $\rho$ is a measure. Applying this lemma with $U=E$, we obtain
that $\rho(E)=\overline{d}/2$, so the lemma could be phrased as
$\rho(U)=\rho(E)\eta(U)$.

###### Proof.

First, assume that every connected component $Q$ of $\mathbf{G}$ is a finite
tree. Then $U\cap E(Q)$ is independent in the cycle matroid of $Q$, and hence

$\rho_{Q}(U\cap E(Q))=\frac{|U\cap E(Q)|}{|V(Q)|}.$

The quantities on both side can be expressed using a random point $\mathbf{q}$
of $V(Q)$.

$\rho_{Q}(U\cap E(Q))={\sf
E}_{\mathbf{q}}\Big{(}1-\frac{1}{|U_{\mathbf{q}}|}\Big{)},$

and

$|U\cap E(Q)|=\frac{1}{2}\sum_{q\in V(Q)}\deg_{U}(q)=\frac{|V(Q)|}{2}{\sf
E}_{\mathbf{q}}\deg_{U}(\mathbf{q}).$

Thus

${\sf
E}_{\mathbf{q}}\Big{(}1-\frac{1}{|U_{\mathbf{q}}|}-\frac{1}{2}\deg_{U}(\mathbf{q})\Big{)}=0.$

Since this holds for every connected component $Q$ of $\mathbf{G}$, Lemma 2.4
implies that the same relation holds for a random point $\mathbf{x}$ from
$\lambda$:

${\sf
E}_{\mathbf{x}}\Big{(}1-\frac{1}{|U_{\mathbf{x}}|}-\frac{1}{2}\deg_{U}(\mathbf{x})\Big{)}=0.$

But here

${\sf
E}_{\mathbf{x}}\Big{(}1-\frac{1}{|U_{\mathbf{x}}|}\Big{)}=\rho(U)\qquad\text{and}\qquad\frac{1}{2}{\sf
E}_{\mathbf{x}}\big{(}\deg_{U}(\mathbf{x})\big{)}=\frac{\overline{d}}{2}\eta(U)$

This settles the case when all components of $\mathbf{G}$ are finite.

Now let $\mathbf{G}$ be any hyperfinite forest. Fix an $\varepsilon>0$. By
hyperfiniteness, there is a Borel set $X\subseteq E$ such that
$\eta(X)<\varepsilon$ and every connected component of
$\mathbf{H}=\mathbf{G}\setminus X$ is finite. By Lemma 4.2 we have $\rho(U\cap
X)\leq D\eta(U\cap X)\leq D\varepsilon$, and so

$\rho(U\setminus X)\leq\rho(U)\leq\rho(U\setminus X)+\rho(U\cap
X)\leq\rho(U\setminus X)+D\varepsilon.$

As noted before, we have $\rho(U\setminus X)=\rho_{\mathbf{H}}(U\setminus X)$.
Hence by the special case proved above and by (10),

$\rho(U\setminus
X)=\frac{\overline{d}_{\mathbf{H}}}{2}\eta_{\mathbf{H}}(U\setminus
X)=\frac{\overline{d}}{2}\eta(U\setminus X),$

and so

$\rho(U)\leq\rho(U\setminus
X)+D\varepsilon=\frac{\overline{d}}{2}\eta(U\setminus
X)+D\varepsilon\leq\frac{\overline{d}}{2}\eta(U)+D\varepsilon.$

while

$\rho(U)\geq\rho(U\setminus X)=\frac{\overline{d}}{2}\eta(U\setminus
X)\geq\frac{\overline{d}}{2}\eta(U)-\varepsilon.$

Letting $\varepsilon\to 0$, the lemma follows.

We can describe a class of minorizing measures for $\rho$. In the finite case,
these are all the extremal minorizing measures. In the infinite case there
must be others, but constructing all of them will probably be very difficult.

######  Corollary 4.5.

Let $\mathbf{G}$ be a graphing and $\mathbf{H}=(J,F)$, a hyperfinite spanning
subforest of $\mathbf{G}$. Then

$\alpha(X)=\frac{\overline{d}}{2}\eta(X\cap F)$

defines a measure on the Borel subsets of $E$ such that $\alpha\leq\rho$ and
$\alpha(E)=\rho(E)$.

###### Proof.

It is clear that $\alpha$ defines a measure. Using (10) and Lemma 4.4, we get

$\alpha(X)=\frac{\overline{d}}{2}\eta(X\cap
F)=\frac{\overline{d}}{2}\,\frac{\overline{d}_{\mathbf{H}}}{\overline{d}}\,\eta_{\mathbf{H}}(X\cap
F)=\frac{\overline{d}_{\mathbf{H}}}{2}\frac{2}{\overline{d}_{\mathbf{H}}}\rho(X\cap
F),$

and hence $\alpha(X)\leq\rho(X)$, and $\alpha(E)=\alpha(F)=\rho(F)=\rho(E)$.

######  Example 4.6.

We cannot drop the hyperfiniteness assumption in Lemma 4.4. Indeed, let
$D=2r-1$ be an odd integer $(r\geq 3)$, and let $\mathbf{G}$ be a graphing
such that every connected component is a $D$-regular tree (such graphings
exist, for example the Bernoulli graphing of a $D$-regular rooted tree, see
e.g. [14]). By a theorem of Csóka, Lippner and Pilhurko [9], the edge set of
$\mathbf{G}$ has a partition $E_{0}\cup E_{1}\cup\dots\cup E_{D+1}$ such that
$E_{i}\in\mathcal{B}\times\mathcal{B}$, $E_{1},\dots,E_{D+1}$ are matchings,
and $E_{0}$ covers a set $S_{0}$ of measure $0$. Let $U=E_{1}\cup\dots\cup
E_{r}$ and $W=E\setminus U$. Then every $u\in J\setminus S_{0}$ misses at most
one of $E_{1},\dots,E_{D+1}$. Hence the connected component of $(J,U)$
containing $u$ has at least $r$ nodes, and the same holds for $(J,W)$. This
implies that

$\rho(U)+\rho(W)\geq 2\big{(}1-\frac{1}{r}\big{)}=2-\frac{2}{r}>1=\rho(U\cup
W).$

So $\rho$ is not even additive.

###  4.4 Beginnings of a limit theory

A next step should be to develop the limit theory for $\rho$; in other words,
to show that if a graph sequence $(G_{n}:~{}n=1,2,\dots)$ with uniformly
bounded degrees locally converges to a graphing $\mathbf{G}$, then the
setfunctions $\rho_{G_{n}}$ converge to the setfunction $\rho_{\mathbf{G}}$ in
some sense. This is not resolved in this paper; but we do prove that the total
rank converges. Given a graphing $\mathbf{G}=(J,\mathcal{B},E,\lambda)$, we
define its total rank as

$\overline{\rho}(\mathbf{G})=\rho_{\mathbf{G}}(E(\mathbf{G}))=1-{\sf
E}\Big{(}\frac{1}{|V(\mathbf{G}_{\mathbf{u}})|}\Big{)},$ (14)

where $\mathbf{u}$ is a random point from $\lambda$. The total rank of a
finite graph is defined analogously.

A graphing parameter $f$ is called locally estimable, if given an error bound
$\varepsilon>0$ and degree bound $D\geq 0$, there are integers $k,r\geq 1$
depending only on $\varepsilon$ and $D$, such that for any graphing
$\mathbf{G}=(J,\mathcal{B},E,\lambda)$ with maximum degree $D$, selecting $k$
independent random nodes $x_{1},\ldots,x_{k}$ from $\lambda$ and considering
their neighborhoods $B_{r}(x_{1}),\ldots,B_{r}(x_{k})$, we can compute an
estimate $R$ of $f(G)$ such that

${\sf P}\big{(}|R-f(G)|\geq\varepsilon\big{)}\leq\varepsilon.$ (15)

This definition applies, in particular, to estimating $f$ on finite graphs.

######  Theorem 4.7.

(a) The graphing parameter $\overline{\rho}$ is locally estimable. (b) If
$G_{1},G_{2},\ldots$ is a sequence of finite graphs with all degrees bounded
by $D\geq 0$ locally converging to a graphing $\mathbf{G}$, then
$\overline{\rho}(G_{n})\to\overline{\rho}(\mathbf{G})$ as ($n\to\infty$).

###### Proof.

Choose $k=\lceil 2/\varepsilon\rceil$. Then for every $x\in J$ we have
$B_{k}(x)\subseteq V(x)$ and

$|B_{k}(x)|\begin{cases}=|V(x)|,&\text{if $B_{k}(x)=V(x)$},\\\ \geq
k,&\text{otherwise}.\end{cases}$

Hence

$\frac{1}{|V(x)|}\leq\frac{1}{|B_{k}(x)|}\leq\frac{1}{|V(x)|}+\frac{1}{k}.$

Taking expectation in $x$, we get

$\overline{\rho}(\mathbf{G})\geq 1-{\sf
E}_{x}\Big{(}\frac{1}{|B_{k}(x)|}\Big{)}\geq\overline{\rho}(\mathbf{G})-\frac{\varepsilon}{2}.$

Repeating this $N=O(\varepsilon^{-2}\log\varepsilon^{-1})$ times
independently, the quantity

$R=1-\frac{1}{N}\sum_{i=1}^{N}\frac{1}{|B_{k}(x_{i})|}$

will be closer to $\overline{\rho}(\mathbf{G})$ than $\varepsilon$ with
probability at least $1-\varepsilon$. The second assertion follows easily.

######  Remark 4.8.

The total rank is even easier to define for the Benjamini–Schramm
representation of the weak limit [3], namely an involution-invariant random
rooted connected graph $(G,o)$. Then

$\overline{\rho}(\mathbf{G})=1-{\sf E}\Big{(}\frac{1}{|V(G,o)|}\Big{)}.$

However, the submodularity over subgraphs would be more difficult to
formulate.

## References

  * [1]
  * [2] F. Bach: Submodular functions: from discrete to continuous domains, Mathematical Programming 175 (2019), 419–459.
  * [3] I. Benjamini and O. Schramm: Recurrence of Distributional Limits of Finite Planar Graphs, Electronic J. Probab. 6 (2001), paper no. 23, 1–13.
  * [4] K.P.S. Bhaskara Rao, M. Bhaskara Rao: Theory of Charges, A Study of Finitely Additive Measures, Academic Press, London–New York–Paris–San Diego–San Francisco (1982).
  * [5] A. Björner: Continuous partition lattice, Proc. Natl. Acad. Sci. 84 (1987) 6327–6329.
  * [6] A. Björner, L. Lovász: Pseudomodular lattices and continuous matroids, Acta Sci. Math. Szeged 51 (1987), 295–308.
  * [7] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh, P. Wollan, Axioms for infinite matroids, Adv. Math. 239 (2013) 18–46.
  * [8] G. Choquet: Theory of capacities, Annales de l’Institut Fourier, 5 (1954), 131–295.
  * [9] E. Csóka, G. Lippner and O. Pikhurko: Kőnig’s line coloring and Vizing’s theorems for graphings, Forum of Math., Sigma 4 (2016), 40pp.
  * [10] D. Denneberg: Non-Additive Measure and Integral, Kluwer Academic Publisher, Dordrecht, 1994.
  * [11] M. Haiman: On Realization of Björner’s ’Continuous Partition Lattice’ by Measurable Partitions, Trans. Amer. MathṠoc. 343 (1994), 695–711.
  * [12] A.S. Kechris: Classical Descriptive Set Theory, Springer Grad. Texts in Math. 156 (1995).
  * [13] F. Kardoš, D. Král’, A. Liebenau, L. Machd: First order convergence of matroids, Europ. J. Combinatorics 59 (2017), 150–168.
  * [14] L. Lovász: Large networks and graph limits, Amer. Math. Soc., Providence, RI (2012).
  * [15] L. Lovász: Submodular setfunctions, matroids and graph limits, preliminary version on https://arxiv.org/abs/2302.0470
  * [16] K. Murota: Discrete Convex Analysis, Soc. Ind. Appl. Math. (1987).
  * [17] K. Murota: Discrete convex analysis, Mathematical Programming 83 (1998), 313–371.
  * [18] J. von Neumann: Continuous Geometries, Proc. Nat. Acad. Sci. USA 22 (1936), 92-100.
  * [19] J.G. Oxley: Matroid Theory, Oxford University Press, Oxford 1992
  * [20] A. Schrijver: Combinatorial Optimization—Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.
  * [21] Ján Šipoš: Nonlinear integrals, Mathematica Slovaca 29 (1979), 257–270.
  * [22] J. Toland: The Dual of $L_{\infty}(X,L,\lambda)$, Finitely Additive Measures and Weak Convergence: A Primer, SpringerBriefs in Mathematics, Springer-Verlag, 2020.
  * [23] D.J.A. Welsh: Matroid Theory, L.M.S. Monographs 8, Academic Press (1976).
  * [24] N. White, ed.: Theory of Matroids, Encyclopedia of Mathematics and its Applications 26, Cambridge University Press (1986).