# Graph Connectivity with Noisy Queries00footnotetext: This work is partially
supported by NTUA Basic Research Grant (PEBE 2020) “Algorithm Design through
Learning Theory: Learning-Augmented and Data-Driven Online Algorithms
(LEADAlgo)”.

Dimitris Fotakis1
<EMAIL_ADDRESS>Evangelia Gergatsouli2
<EMAIL_ADDRESS>
Charilaos Pipis1
<EMAIL_ADDRESS>
Miltiadis Stouras3*** Supported by the Costas M. Lemos Foundation Research
Scholarship
<EMAIL_ADDRESS>
Christos Tzamos2
<EMAIL_ADDRESS>

1National Technical University of Athens
2University of Wisconsin-Madison
3 École Polytechnique Fédérale de Lausanne

###### Abstract

Graph connectivity is a fundamental combinatorial optimization problem that
arises in many practical applications, where usually a spanning subgraph of a
network is used for its operation. However, in the real world, links may fail
unexpectedly deeming the networks non-operational, while checking whether a
link is damaged is costly and possibly erroneous. After an event that has
damaged an arbitrary subset of the edges, the network operator must find a
spanning tree of the network using non-damaged edges by making as few checks
as possible.

Motivated by such questions, we study the problem of finding a spanning tree
in a network, when we only have access to noisy queries of the form “Does edge
e exist?”. We design efficient algorithms, even when edges fail adversarially,
for all possible error regimes; 2-sided error (where any answer might be
erroneous), false positives (where “no” answers are always correct) and false
negatives (where “yes” answers are always correct). In the first two regimes
we provide efficient algorithms and give matching lower bounds for general
graphs. In the False Negative case we design efficient algorithms for large
interesting families of graphs (e.g. bounded treewidth, sparse). Using the
previous results, we provide tight algorithms for the practically useful
family of planar graphs in all error regimes.

##  1 Introduction

From road and railway networks to electric circuits and computer networks,
maintaining an operational spanning subgraph of a network is crucial in many
real-life applications. This problem can be viewed as a traditional
combinatorial optimization problem, graph connectivity. However, in real-life
applications, edges sometimes fail; a natural destruction on the road or a
malfunction in the connector cable can render a link in the network non
operational. Worse still, detecting faulty connections is not always that
simple; our tools may be unreliable, resulting in untrustworthy indications.
Can we efficiently find an operational spanning tree, when we cannot obtain
reliable signals on the operation of edges?

In this work we study the problem of finding a spanning tree using noisy
queries on the existence of edges. Specifically, given a moldgraph $G$, where
some subgraph $H$ of $G$ is realized, we have access to an oracle that answers
questions of the form _“Does edge $e$ exist in $H$?”_. The answers the oracle
gives are _inconsistent_ : for a specific edge $e$, the answer might differ
every time. Queries to the oracle are costly, therefore our goal is to find a
spanning tree asking as few queries as possible. We design efficient
algorithms that achieve this goal, in all 3 different error regimes; 2-sided
(where any answer might be erroneous), 1-sided false positives (where “no”
answers are always correct) and 1-sided false negatives (where “yes” answers
are always correct).

###  1.1 Our Contribution

As a warm-up, we begin by solving the simpler problem of verifying the
connectivity of a tree (Theorem 3.1). In the 2-sided error case, we give an
algorithm performing $O(m\log m)$ queries and show that no algorithm can
perform better, even on special cases like sparse graphs. In the 1-sided False
Negative error regime, we design an algorithm that is optimal on planar graphs
and yields efficient guarantees for other special families like graphs with
treewidth $k$ or degeneracy $k$ ($O(km)$ queries) and graphs with Hadwiger
number $k$ ($O(k\sqrt{\log k}m)$ queries). The same algorithm can be used for
general graphs, and outside the aforementioned families, its performance
gracefully degrades to that of the naive strategy (that is $O(m\log n)$
queries).

In the False-Positive error case, our algorithm obtains tight guarantees for
general graphs (Theorem 6.1), while in the special case where the realized
graph is acyclic, the query complexity becomes linear. Both in the False-
Negatives and the False-Positives case, our algorithms _do not need to know_
whether the graph has any special properties (sparsity, acyclic realized
subgraph etc), they can simply run a unified algorithm that achieves the best
guarantee according to each case.

Our results, imply tight algorithms for planar graphs, which is a family of
graphs that is frequently encountered in road/railway networks, electrical
circuits, image processing/computer vision [YF15, STC09].

###  1.2 Related Work

Variations of this problem have been studied in literature, however they
differ from our setting. A crucial assumption in all of the previous works, is
that each edge has an independent probability of existence, which however,
does not always bear out in practice. For example, a power outage may deem
several local network links non-operational. In our work, we allow the
existence probabilities of different edges to be arbitrarily correlated.

[FRPU94] first studied evaluating boolean decision trees where the nodes are
noisy and the goal is to find the correct leaf within a tolerance parameter
$Q$. In [FWK14, FFX+17] the authors study finding spanning trees in Erdos-
Renyi graphs, a special class of random graphs where each edge exists
independently with some probability. In their setting each edge has a _query
cost_ , and the goal is to find a spanning tree using the least number of
queries. However, contrary to their setting, we handle both adversarially
selected realized graphs and noisy answers to existence queries. More
recently, [LRAZ21] also studied the problem of finding a MST when the edges
can fail with some probability. The work of [HEK+08] and [EH14] considers
verifying spanning trees where each edge has a weight inside an uncertainty
region and the algorithm can ask the edge to reveal it. The goal is to find a
small weight spanning tree without asking all the edges for their weight. None
of these settings account for _inconsistent_ queries, like in our setting.

On a different problem in [MS17], the authors study clustering in a similar
setting to ours where they have access to queries of the form “is $u$ and $v$
in the same cluster?”. However in their model, the oracle gives consistent
answers on each query†††In our case, asking if an edge $e$ exists can change
from “Yes” to “No” or vice versa for distinct queries on the same edge..

##  2 Preliminaries

In graph connectivity with noisy queries we are given a graph $G=(V,E)$, with
edge set $E$ and node set $V$ called the _moldgraph_ , then an adversary
selects a connected subgraph $G^{\prime}$ of $G$ to be realized. The goal of
the algorithm is to find a spanning tree in the subgraph $G^{\prime}$ spending
as little time as possible gathering information. The algorithm does not
directly observe the subgraph that is realized, but only has access to an
oracle that answers questions of the form “ _Is edge $e\in E$ realized?_”.
Each call to this oracle costs $1$, therefore our goal is to find a realized
spanning tree, with constant probability using the minimum number of queries
to the oracle.

This oracle, however, is noisy and inconsistent; it might not give the correct
answer and when asked multiple times on the same edge, it may give different
answers. More formally, the oracle is a function
$\mathcal{O}:E\rightarrow\\{\text{Yes, No}\\}$, that given an edge $e\in E$
answers either _Yes_ or _No_ , indicating whether the edge is realized or not.
We study all the possible error types for the oracle, outlined below.

#### 2-sided error:

the oracle’s answer is wrong (ie. with “No” for realized edges and “Yes” for
non-realized) with constant error probability $p<1/2$.

#### 1-sided error, False Negative (FN):

if the edge is not realized then the response is always “No”. If it is
realized then the response is “No” with constant error probability $p<1/2$,
and “Yes” with probability $(1-p)$. Thus, when the oracle responds “Yes” then
it is certain that this edge is realized, but when it responds “No” then the
edge may or may not be realized, hence the False Negative responses.

#### 1-sided error, False Positive (FP):

if the edge is realized then the response is always “Yes”. If it is not
realized then the response is “Yes” with constant error probability $p<1/2$,
and “No” with probability $(1-p)$. Thus, when the oracle responds “No” then it
is certain that this edge is not realized, but when it responds “Yes” then the
edge may or may not be realized, hence the False Positive responses.

###  2.1 Graphs notation

We present some useful definitions for concepts we use throughout the paper.
We begin by our definition of sparsity. Sometimes the parameter $\rho$ is
referred to as the average degree of the graph.

######  Definition 1 ($\rho$-sparse Graphs).

A graph $G$ with $m$ edges and $n$ vertices is called $\rho$-sparse if
$m\leq\rho n$.

It is noteworthy that our definition of $\rho$-sparsity for graphs is weaker
than the usual definitions of graph sparsity, in the sense that it can be
easily satisfied without requiring local sparsity properties. This means that
constructing efficient algorithms for this property, directly translates to
efficient algorithms for other usual sparsity parameters. For example, using
our definition, $k$-degenerate graphs are $k$-sparse [LW70], $k$-treewidth
graphs are also $k$-sparse [RS84], and graphs with Hadwiger number $k$ are
$O(k\sqrt{\log k})$-sparse [Kos84, BCE80].

######  Definition 2 (Edge Contraction).

The edge contraction operation on an edge $e=\\{u,v\\}$ of a graph $G$ results
in a new graph $G^{\prime}$ wherein $u$ and $v$ are replaced by a new vertex
$uv$ which is connected to all vertices of $G$ that were incident to either
$u$ or $v$.

######  Definition 3 (Graph minor [Lov06]).

A graph $H$ is called a minor of a graph $G$, if $H$ can occur after applying
a series of edge deletions, vertex deletions, and edge contractions.

######  Definition 4 (Minor-closed Graph Family).

A set $\mathcal{F}$ of graphs is called a minor-closed graph family if for any
$G\in\mathcal{F}$ all minors of $G$ also belong to $\mathcal{F}$.

The algorithms that we present for FN and FP queries produce and handle
multigraphs during intermediate steps. Here, we present and define some of the
main concepts we are using from multigraphs.

An edge $e=\\{u,v\\}$ in a multigraph is a link connecting $u$ and $v$. There
might be other parallel edges between $u$ and $v$, and each one is distinct.
Sometimes we will need to work with the set of all parallel edges between $u$
and $v$. We call this set a _super-edge_ between $u$ and $v$. For simplicity,
we consider simple edges to be super-edges with size 1.

######  Definition 5 (Neighborhood).

For a vertex $v\in V$, we denote by $N(v)$ its _neighborhood_ , which is the
set of all super-edges with $v$ as one of the endpoints.

######  Definition 6 (Degree).

For a node $v\in V$, degree $\text{deg}(v)$ of $v$ is the size of $N(v)$.

Finally, we note that whenever an algorithm performs an edge-contraction
operation on edge $e$ of a multigraph, then we delete all the other parallel
edges to $e$ as well, leaving no self-loops in the graph. Moreover, if any
parallel super-edges result after the contraction, they are replaced by a
larger super-edge, their union.

##  3 Verifying Connectivity

As a warm-up, before attempting to find a realized spanning tree of the graph,
we begin by presenting an algorithm for verifying the connectivity of a tree.
Specifically, given a tree, which could be the operating spanning tree of a
network, we want to verify whether it is connected or not, that is whether all
of its edges are realized.

Naively verifying this property (ie. performing a fixed number of queries on
every edge) needs $O(n\log n)$ queries to yield a constant probability
guarantee. However, we show that it is possible to verify the connectivity of
the tree using only $O(n)$ queries, which is asymptotically the same as if our
oracle had no noise.

Algorithm 1 $Verify(T)$: A verification protocol for tree connectivity with
2-sided error

Input: Tree $\mathcal{T}$ of $n$ edges
Parameters: $\varepsilon$, $\delta$, $p$
Output: True iff $T$ is connected

1:$threshold\
\leftarrow\lceil\log_{\frac{1-p}{p}}\left(\frac{1}{\delta}\right)\rceil$

2:$budget\ \leftarrow\lceil\frac{1}{\epsilon}\cdot\frac{1}{1-2p}\rceil\cdot
threshold\cdot n$

3:for $e\in E(T)$ do

4: counter $\leftarrow 0$

5: while (counter $<$ threshold) & (budget $>$ 0) do

6: q $\leftarrow$ Query edge $e$

7: budget $\leftarrow$ budget $-1$

8:

9: if q is “Yes” then

10: counter $\leftarrow$ counter $+1$

11: else

12: counter $\leftarrow$ counter $-1$

13: end if

14: end while

15: if budget = 0 then

16: return False

17: end if

18:

19:end for

20:

21:return True

Our algorithm (Algorithm 1) has a predetermined budget of queries that depends
on the requested guarantees. It fixes an ordering of the edges, and for each
edge it performs queries until it receives $c$ more positive answers than
negative ones (where $c$ is also fixed and depends on the requested
guarantees). For realized edges, since $p<1/2$, the expected number of queries
until they reach $c$ is polynomial in $c$, while the probability to never
yield $c$ more positive answers than negative ones, within the budget, is
exponentially small in $c$. Using a global budget instead of a fixed per-edge
number of queries, allows us to dynamically allocate it based on need. We save
up queries from realized edges that reach the threshold quickly and spend it
on other realized edges that yield multiple false negatives. On the other
hand, the probability that a non-realized edge reaches $c$ is exponentially
small in $c$. As a result, if a non-realized edge exists in the tree, the
algorithm will consume all of its budget on this edge before reaching the
threshold. Using this approach, Algorithm 1 achieves the following guarantees.

######  Theorem 3.1.

Algorithm 1 correctly classifies connected trees with probability
$1-\varepsilon$ and disconnected trees with probability $1-\delta$, while
performing at most $O\left(\frac{1}{\varepsilon}n\log\frac{1}{\delta}\right)$
queries.

The proof of the theorem is deferred to Section A of the appendix. As a
Corollary of Theorem 3.1, we get that, for constant probability guarantees,
Algorithm 1 requires $O(n)$ queries.

######  Corollary 3.1.1.

Algorithm 1 correctly classifies connected trees with probability $.99$ and
disconnected trees with probability $.99$, using $O(n)$ queries.

##  4 Two-sided error oracle

Moving on to our main result, we show how to find a realized spanning tree in
the 2-sided error oracle. Recall that in this case, the oracle may give false
responses either when the edge is realized or when it is non-realized. The
main result for this regime is the following theorem.

######  Theorem 4.1.

In the 2-sided error regime, there exists an algorithm that finds a realized
spanning tree with high probability, using $O(m\log m)$ queries in a moldgraph
of $m$ edges. Moreover, no algorithm can do better than $\Omega(m\log m)$.

To show this theorem, we separately show the upper and lower bounds in Lemmas
4.2 and 4.4. Combining them we immediately get the theorem.

###  4.1 Upper Bound

In order to show the upper bound (Lemma 4.2), we describe an algorithm that
achieves this query bound and prove its correctness in Lemma 4.3

######  Lemma 4.2.

In the 2-sided error regime, there exists an algorithm that finds a realized
spanning tree with high probability, using $O(m\log m)$ queries in a moldgraph
of $m$ edges.

Our algorithm, described below, uses the same idea as the naive algorithm for
the connectivity verification problem.

#### Naive algorithm

The algorithm is as follows. First, query each edge of the moldgraph
$O(\log{m})$ times. Second, by treating all edges with more “Yes” than “No”
responses as realized, compute a spanning tree on the discovered realized
subgraph. If the graph is disconnected, output any spanning tree of the
moldgraph.

The algorithm performs $O(m\log m)$ queries in total. The following lemma
shows the correctness of the algorithm, and its proof is deferred to Section B
of the appendix.

######  Lemma 4.3.

The Naive algorithm finds a realized spanning tree with high probability.

(a) The moldgraph used for the proof of Lemma 4.4

(b) A realized graph from the family mentioned in the proof of Lemma 4.4. The
dotted lines are non-realized edges and by the edges lie the answers of the
2-sided noisy oracle.

Figure 1:

###  4.2 Lower Bound

Switching gears towards the lower bound, we give an instance showing that we
cannot hope for anything better than the $O(m\log m)$ upper bound shown in the
previous section. As we expected, this is a strictly harder problem than
verifying the connectivity of a tree, since in this case we have to identify a
realized edge in each independent cut of the moldgraph.

######  Lemma 4.4.

In the 2-sided error regime, there exists a graph where any algorithm requires
$\Omega(m\log m)$ queries to discover a spanning tree with constant failure
probability.

###### Proof of Lemma 4.4.

We consider the graph in Figure 1 which has $n+1$ vertices and $2n$ edges.
Between any two consecutive vertices there exist 2 parallel edges, one of
which is realized and the other is not. Note that this moldgraph is a
multigraph for simplicity of presentation. But the arguments hold analogously
for a $2$-by-$n$ grid moldgraph, if we additionally give our algorithms the
extra information that all vertical edges are realized. This only makes an
algorithm more powerful as, in the worst-case, it can choose to ignore this
information and execute independently. Then, we show that even with this extra
knowledge, no algorithm can achieve a better query complexity than the desired
bound.

Any algorithm on this graph will have to treat each edge-pair independently of
the others, because uncovering a realized edge in one pair does not give any
information on the solution to other pairs. Moreover, the optimal strategy for
any algorithm is to query both edges in a pair an equal number of times and
then pick the one with the majority of positive responses. Otherwise, picking
the one with the least positive responses gives us smaller probability of
success.

Let us suppose that the algorithm performs $k$ queries on a specific edge-
pair. If more than $k/2$ of them give false responses then the wrong edge will
be picked as realized. Consequently, the algorithm will have to perform more
than $k$ queries on this edge-pair to discover the correct edge. We set
$k=\Theta(\log(n/\log n))=\Theta(\log n)$ and call such a faulty edge-pair a
“bad” pair. Then, by the fact that false queries follow a binomial
distribution, we get

$\textbf{Pr}\left[\text{bad}\right]>p^{k/2}>\log n/n$

Thus the probability that at least one such “bad pair” exists is

$\displaystyle\textbf{Pr}\left[\text{bad exists}\right]$
$\displaystyle=1-\textbf{Pr}\left[\text{all good}\right]$ $\displaystyle\geq
1-\left(1-\frac{\log n}{n}\right)^{n}$ $\displaystyle\geq 1-\frac{1}{n}$

Assuming that there exists such a “bad pair” then the algorithm will have to
perform $\Omega(\log{n})$ queries on it. However, there is no way to know from
the beginning which pair it will be. This means that any algorithm in this
case will have to pick an $\alpha$-fraction of edge-pairs on which to perform
these many queries, for some (not necessarily constant) $\alpha$. Define
$Q_{b}$ to be the event that the algorithm performs $\Omega(\log n)$ queries
on the “bad pair”. Then, $\textbf{Pr}\left[Q_{b}\right]=\alpha$ and the
probability of failure for the algorithm when a bad pair exists is

$\textbf{Pr}\left[\text{fail}|\text{bad
exists}\right]=\alpha\textbf{Pr}\left[\text{fail}|Q_{b}\right]+(1-\alpha)\geq(1-\alpha)$

Thus, the total probability of failure to discover a spanning tree will be

$\displaystyle\textbf{Pr}\left[\text{fail}\right]$
$\displaystyle\geq\textbf{Pr}\left[\text{fail}|\text{bad
exists}\right]\textbf{Pr}\left[\text{bad exists}\right]$
$\displaystyle\geq(1-\alpha)\left(1-\frac{1}{n}\right)$

If we want the failure probability to be constant then it must hold that
$\alpha=1-o(1)$. Consequently, we perform $\Omega(\log n)$ queries on $\alpha
n=\Theta(n)$ edges, giving us an $\Omega(n\log n)$ lower bound for this graph
instance. The desired lower bound comes from the fact that any algorithm
performing better than $\Omega(m\log m)$ queries would perform better than
$\Omega(n\log n)$ in this instance, as it has $m=O(n)$. ∎

##  5 One-sided error oracle: False Negatives

Moving on to the one-sided error regime, we first consider the case of False
Negative errors in the oracle. Our main contribution is an algorithm for the
case of sparse and minor-closed graph families. We also show how we can obtain
an algorithm for general graphs, that still performs well on $\rho$-sparse
graphs, even when this property is unknown to us.

Finally, we show how to combine these results to obtain an algorithm for
planar graphs that uses $O(m)$ queries to find a spanning tree, while no
algorithm can do better (Corollary 5.4.1). This also implies better guarantees
for other special families of graphs, as shown in Corollary 5.4.2.

######  Theorem 5.1.

In the 1-sided False Negative regime, given a moldgraph of $m$ edges and $n$
nodes, there exists an algorithm that finds a realized spanning tree using
$O(m\log n)$ queries in expectation. If the moldgraph is $\rho$-sparse and
minor-closed, the algorithm uses $O(\rho m)$ queries in expectation.

###### Proof of Theorem 5.1.

To create such an algorithm, we can run in parallel both the Naive Algorithm
presented in the next subsection (Lemma 5.2) and Algorithm 3 for sparse minor-
closed graphs. In particular, it suffices to let the two algorithms perform
their queries alternately and independently of each other.

If the moldgraph is $\rho$-sparse and minor-closed, then by Lemma 5.3,
Algorithm 3 will perform $O(\rho m)$ queries in expectation before finding a
spanning tree. For each one of these queries, we have just performed one extra
query for the naive algorithm. Thus, eventually the combined algorithm will
find the spanning tree in the same query complexity.

Otherwise, in general graphs, by using Lemma 5.2 for the Naive Algorithm and a
similar argument as before, we get $O(m\log n)$ queries in expectation. ∎

###  5.1 Warm-up: naive algorithm

We start by describing the naive algorithm used for general graphs, that
obtains the $O(m\log n)$ guarantee. The algorithm proceeds in rounds, where in
each round it performs one query on all $m$ edges of the moldgraph. It repeats
this process until $n-1$ realized edges forming a spanning tree are
discovered. Note that in the case of FN queries we can be completely certain
when a realized edge is discovered.

######  Lemma 5.2.

The Naive Algorithm finds a spanning tree while performing $O(m\log n)$
queries on expectation.

The proof is deferred to section C of the Appendix.

###  5.2 An Algorithm for $\rho$-sparse graphs

We present the algorithm used to obtain better guarantees for the family of
$\rho$-sparse and minor closed graphs. The algorithm is presented in Algorithm
3 and the guarantees in Lemma 5.3.

######  Lemma 5.3.

Given a moldgraph of $m$ edges, belonging to a $\rho$-sparse and minor-closed
family of graphs, Algorithm 3 performs $O(\rho m)$ queries in expectation and
uncovers a realized spanning tree with probability $1$.

The basic primitive that our algorithm uses is a DISCOVER subroutine that
cleverly orders queries in a way that it allows it to explore multiple edge
sets in parallel. The subroutine is presented in more detail in Algorithm 2
and the Lemma that follows.

Algorithm 2 DISCOVER($\mathcal{S}$): Discovers an edge in a collection
$\mathcal{S}$ of edge sets.

Input: Set $\mathcal{S}=\\{E_{1},E_{2},\ldots,E_{k}\\}$
Output: Realized edge $e$

1:while no edge is found do

2: for $i=1$ to $k$ do

3: Let $e$ be the next edge in the cyclic order of $E_{i}$

4: $q\leftarrow$ Query edge $e$

5:

6: if $q$ is “Yes” then

7: return $e$

8: end if

9: end for

10:end while

######  Lemma 5.4.

Let $\mathcal{S}$ be a collection of $k$ sets of edges. Assume as well that
there exists at least one set in $\mathcal{S}$ containing some realized edge,
then Algorithm 2 finds and returns such an edge using at most $2k|E_{f}|$
queries in expectation, where $E_{f}$ is the set containing the found edge.

The proof is deferred to Section C of the Appendix.

Algorithm 3 SolveSparseFN($G$): Solves the problem in sparse moldgraphs using
an 1-sided error oracle with False Negatives.

Input: Graph $G$
Output: A realized spanning tree

1:if $G$ is a single node then

2: return $\emptyset$

3:end if

4:

5:$u=\text{argmin}\\{\text{deg}(v)$}

6:$e=\text{DISCOVER}(N(u))$

7:

8:// Let $G^{\prime}$ be the resulting graph after contracting edge $e$.

9:return $\text{SolveSparseFN}(G^{\prime})\ \cup\ \\{e\\}$

We are now ready to prove the main result of the section, Lemma 5.3.

###### Proof of Lemma 5.3.

We use induction on the number $n$ of vertices of $G$ to prove that Algorithm
3 performs at most $4\rho m$ queries in expectation. Throughout this proof we
denote by $m$ the total number of simple edges of the graph, and by $m_{s}$
the number of super-edges.

The base case of induction for $n=1$ holds trivially, as the algorithm needs
no queries. Now assume that it holds for all graphs of at most $n-1$ vertices.
We will prove that it also holds for graphs of $n$ vertices.

By using the sparsity property that $m_{s}\leq\rho n$, we can see that there
always exists at least one vertex $u$ with degree $\text{deg}(u)\leq 2\rho$.
Otherwise, the number of super-edges would be equal to

$m_{s}=\frac{1}{2}\sum_{v\in V}\text{deg}(v)>\rho n$

which leads to the graph not being $\rho$-sparse, a contradiction.

The algorithm uses Algorithm 2 as a basic subroutine, passing as input the
neighborhood $N(u)$ of the least-degree vertex $u$. This is allowed because
$N(u)$ is a cut of the moldgraph and thus satisfies the assumption of Lemma
5.4 that at least one edge-set contains a realized edge.

The DISCOVER subroutine will find a realized edge inside a super-edge $E_{f}$,
spending in expectation at most $2\cdot\text{deg}(u)|E_{f}|\leq 4\rho|E_{f}|$
queries.

After contracting the super-edge $E_{f}$ that contains the realized edge found
by the subroutine, the algorithm will continue on the contracted graph
$G^{\prime}$ that has $n-1$ vertices. It is important to note here that the
graph $G^{\prime}$ will still be $\rho$-sparse, because of our assumption that
graphs are also minor-closed. By the induction hypothesis, the algorithm will
find a realized spanning tree of $G^{\prime}$, by performing at most

$4\rho\ (m-|E_{f}|)$

queries in expectation. Therefore, the total number of queries performed will
be at most

$4\rho|E_{f}|+4\rho\ (m-|E_{f}|)=4\rho m$

in expectation, and thus gives us the desired $O(\rho m)$ upper bound. ∎

######  Corollary 5.4.1.

If the moldgraph is planar, then Algorithm 3 performs $O(m)$ queries in
expectation and succeeds in finding a realized spanning tree with probability
1. Moreover, this is tight and no better algorithm exists for this case.

###### Proof of Corollary 5.4.1.

The upper bound follows directly by Lemma 5.3 and the fact that planar graphs
are both minor-closed and $3$-sparse, as $m\leq 3n-6$.

To argue that the algorithm is tight, we remind that in all cases the realized
spanning subgraph is chosen arbitrarily, and even in an adversarial way. This
means that any algorithm aiming to find a realized spanning tree has to
perform at least $n-1$ queries, for the $n-1$ realized edges of the spanning
tree that it discovers. As planar graphs have $m=\Theta(n)$ the desired lower
bound follows. ∎

Apart from planar graphs, as we hinted when defining $\rho$-sparsity, an
efficient algorithm for $\rho$-sparse graphs immediately gives us efficient
algorithms for graphs that are sparse with respect to other widely-used
parameters. Based on [LW70, RS84, Kos84], we can see that the parameters of
degeneracy, treewidth and Hadwiger Number all define minor-closed graph
families. Moreover, $k$-degenerate graphs and $k$-treewidth graphs have
sparsity $k$, while graphs with Hadwiger number $k$ are $O(k\sqrt{\log
k})$-sparse. Hence, applying Lemma 5.3 we get the following Corollary.

######  Corollary 5.4.2.

Algorithm 3 performs $O(km)$ queries for graphs with treewidth $k$ or
degeneracy $k$ and $O(k\sqrt{\log k}m)$ queries for graphs with Hadwiger
number $k$.

##  6 One-sided error oracle: False Positives

In the 1-sided, False-Positive error case, we initially present an $O(m\log
m)$ algorithm for general graphs, while dropping the complexity to linear when
the realized graph is a tree. Each of these guarantees are tight for their
respective case. We also show how using one algorithm, we can capture both
cases, without actually knowing the structure of the realized graph, and
obtain the tight guarantees for each case. Our formal guarantees are formally
stated in Theorem 6.1.

######  Theorem 6.1.

In the 1-sided error FP regime, there exists an algorithm that performs
$O(m\log m)$ queries in the general case and finds a realized spanning tree
with high probability. Moreover, if the realized subgraph is a tree, the
algorithm performs $O(m)$ queries in expectation and succeeds to find the
spanning tree with high probability. These complexities are tight for their
respective cases.

###### Proof of Theorem 6.1.

Similarly to the case of False Negative oracle errors (Lemma 5.1) we can
combine the Naive Algortihm with Algorithm 4, letting them perform queries
alternately. When any of the two algorithms halts, the process ends.

Consider the case of general graphs. By Lemma 6.2 the naive algorithm succeeds
in finding a realized spanning tree with high probability by performing
$O(m\log m)$ queries. Thus, the combined algorithm also succeeds with at most
$O(m\log m)$ queries.

Now, we look at the special case where the moldgraph is planar and the
realized subgraph is a tree. By Lemma 6.5, Algorithm 4 performs at most $O(m)$
queries in expectation. Let $X$ be the random variable denoting the number of
queries performed by Algorithm 4, and let $E=\\{X>m\log_{2}(m^{2})\\}$ be the
event that $X$ is more than the queries of the naive algorithm. Using Markov’s
inequality we get

$\textbf{Pr}\left[E\right]\leq\frac{\mathbb{E}\left[X\right]}{m\log_{2}(m^{2})}\leq
O\left(\frac{1}{\log m}\right)$

Thus, the number $Q$ of queries performed before the combined algorithm
terminates for this case is

$\displaystyle\mathbb{E}\left[Q\right]$ $\displaystyle=\mathbb{E}\left[Q|\neg
E\right]\textbf{Pr}\left[\neg
E\right]+\mathbb{E}\left[Q|E\right]\textbf{Pr}\left[E\right]$
$\displaystyle\leq\mathbb{E}\left[X\right]+(m\log_{2}(m^{2}))O\left(\frac{1}{\log
m}\right)$ $\displaystyle\leq O(m)$

When the algorithm has terminated, there still exists some probability of
failure, in the case that both event $E$ happens and the naive algorithm fails
to find a realized spanning tree. By using the failure probability from Lemma
6.2 and the previously calculated probability of event $E$ happening, we get

$\textbf{Pr}\left[E\wedge\text{naive algo fails}\right]=O\left(\frac{1}{m\log
m}\right)$

Thus, the combined algorithm succeeds in this case with high probability as
well, and the proof is concluded. ∎

###  6.1 Upper & Lower Bounds

We start by showing, similar to the previous section, how to obtain the upper
bound in the case of general graphs.

######  Lemma 6.2.

In the 1-sided error FP regime, there exists an algorithm that performs
$O(m\log m)$ queries in the general case and finds a realized spanning tree
with high probability.

The proof is deferred to Section D of the Appendix.

Furthermore, we show the lower bound for the general case graphs, stated
formally below. Observe that from the construction of this lower bound, no
algorithm can do better in planar or sparse graphs.

######  Lemma 6.3.

In the regime of 1-sided FP errors, if the realized graph has cycles, any
algorithm requires $\Omega(m\log m)$ queries to discover a spanning tree with
constant failure probability.

The proof is deferred to Section D of the Appendix.

###  6.2 Special Case: Acyclic Realized Graphs

In this section we focus on the special case where the realized subgraph is a
tree.This property implies that for each cycle in the moldgraph, at least one
edge of the cycle must be non-realized. Since our oracle only commits False
Positive errors, the negative answers are definitive, meaning that we can
completely remove the edges which have yielded such answers. We design an
algorithm (Algorithm 4) that utilizes this fact and progressively removes non-
realized edges until it is left with a tree which will also be the realized
subgraph. This result is stated formally in the theorem below.

######  Theorem 6.4.

In the regime of 1-sided FP errors, if the moldgraph $G$ is a planar graph and
the realized subgraph is a tree, Algorithm 4 recovers the realized spanning
tree with probability $1$ while performing at most $O(m)$ queries in
expectation.

Our main observation is that the FP setting is very similar, and in fact can
be reduced to, the FN setting. In the FN setting, we know that at least one
realized edge lies in every cut of the moldgraph and we repeatedly query the
edges of a cut in order to unveil the realized edge. In a similar manner, in
the FP setting, we can repeatedly query the edges of the cycle in order to
discover the non-realized edge in every cycle. Hence, the question that arises
is: how can one decide a sequence of cycles to query such that the expected
number of queries is minimized? Algorithm 4 does so by utilizing the planarity
of the moldgraph to consistently find small cycles to query.

Algorithm 4 SolvePlanarFP($G$): Discovers a realized spanning tree in planar
moldgraphs using an 1-sided error oracle with False Positives.

Input: Planar Graph $G(V,E)$
Output: A realized spanning tree

1:// Construct the dual graph of $G$

2:$G^{\prime}\leftarrow dual(G)$

3:

4:// Inverse all the oracle answers and use SolveSparseFN

5:return $E(G)\setminus\text{SolveSparseFN}(G^{\prime})$

#### Description of Algorithm 4

Our algorithm reduces the FP setting of this special case to solving an FN
instance on the _dual graph_ of the moldgraph. The dual of a planar graph has
one node for each face of the planar graph, as illustrated in Figure 2. Two
face nodes are connected by an edge in the dual graph if and only if they
share an edge in the planar graph. With this transformation we can now focus
on cuts of the dual graph which directly correspond to cycles of the
moldgraph. Notice that removing an edge in the moldgraph (after identifying it
as non-realized) is the same as contracting it in the dual graph. As a result,
removing all the non-realized edges until we are left with a tree in the
moldgraph is exactly equivalent to contracting the same edges in the dual
until we are left with one node (Lemma 6.5). For this reason, Algorithm 4
constructs the dual graph of the moldgraph and calls Algorithm 3 to retrieve a
non-realized spanning tree of the dual graph. Note that we reverse all the
oracle’s answers before we hand them out to Algorithm 3, since by design it
contracts the edges for which we get positive answers but in the FP setting we
want to contract the edges of the dual graph whose corresponding edges yielded
negative answers.

(a) A cycle of the graph is the neighborhood of the enclosed face’s node in
the dual graph

(b) Breaking the cycle by removing an edge leads to the contraction of the
corresponding edge in the dual graph

Figure 2: One iteration of Algorithm 4

We will now prove the correctness of Algorithm 4 and bound its query
complexity.

######  Lemma 6.5.

Let $G$ be a planar moldgraph, $T$ be the realized tree of $G$ and
$G^{\prime}$ be a dual graph of $G$. The induced subgraph of $G^{\prime}$
containing all the edges corresponding to non-realized edges of $G$, is a
spanning tree of $G^{\prime}$.

The proof of Lemma 6.5 is deferred to Appendix D.

###### Proof of Theorem 6.4.

Algorithm 4 constructs the dual graph of $G$ and uses Algorithm 3 to find a
spanning tree of $G^{\prime}$ consisting of non-realized edges. From Lemma 6.5
we know that by removing these edges, we are left with the realized tree $T$
of $G$. All the queries performed during this process are made through
Algorithm 3. Therefore, from Lemma 5.3, the total number of queries conducted
is $O(m)$. ∎

## References

  * [BCE80] Béla Bollobás, Paul A Catlin, and Paul Erdös.  Hadwiger’s conjecture is true for almost every graph.  Eur. J. Comb., 1(3):195–199, 1980.
  * [EH14] Thomas Erlebach and Michael Hoffmann.  Minimum spanning tree verification under uncertainty.  In Dieter Kratsch and Ioan Todinca, editors, Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, volume 8747 of Lecture Notes in Computer Science, pages 164–175. Springer, 2014\.
  * [FFX+17] Luoyi Fu, Xinzhe Fu, Zhiying Xu, Qianyang Peng, Xinbing Wang, and Songwu Lu.  Determining source-destination connectivity in uncertain networks: Modeling and solutions.  IEEE/ACM Trans. Netw., 25(6):3237–3252, 2017.
  * [FRPU94] Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal.  Computing with noisy information.  SIAM Journal on Computing, 23(5):1001–1018, 1994.
  * [FWK14] Luoyi Fu, Xinbing Wang, and P. R. Kumar.  Optimal determination of source-destination connectivity in random graphs.  In Jie Wu, Xiuzhen Cheng, Xiang-Yang Li, and Saswati Sarkar, editors, The Fifteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc’14, Philadelphia, PA, USA, August 11-14, 2014, pages 205–214. ACM, 2014.
  * [HEK+08] Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihalák, and Rajeev Raman.  Computing minimum spanning trees with uncertainty.  In Susanne Albers and Pascal Weil, editors, STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings, volume 1 of LIPIcs, pages 277–288. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2008\.
  * [Kos84] Alexandr V. Kostochka.  Lower bound of the hadwiger number of graphs by their average degree.  Combinatorica, 4(4):307–316, 1984.
  * [Lov06] László Lovász.  Graph minor theory.  Bulletin of the American Mathematical Society, 43(1):75–86, 2006\.
  * [LRAZ21] Jianhua Lyu, Yiran Ren, Zeeshan Abbas, and Baili Zhang.  Reliable route selection for wireless sensor networks with connection failure uncertainties.  Sensors, 21(21):7254, 2021.
  * [LW70] Don R. Lick and Arthur T. White.  k-degenerate graphs.  Canadian Journal of Mathematics, 22(5):1082–1096, 1970.
  * [MS17] Arya Mazumdar and Barna Saha.  Clustering with noisy queries.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [RS84] Neil Robertson and Paul D Seymour.  Graph minors. iii. planar tree-width.  Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984.
  * [STC09] Frank R. Schmidt, Eno Töppe, and Daniel Cremers.  Efficient planar graph cuts with applications in computer vision.  In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pages 351–356. IEEE Computer Society, 2009.
  * [YF15] Julian Yarkony and Charless C. Fowlkes.  Planar ultrametrics for image segmentation.  In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 64–72, 2015.

##  Appendix A Proofs from Section 3

See 3.1

###### Proof of Theorem 3.1.

Algorithm 1 decides a fixed permutation of the given tree’s edges and proceeds
by doing the following procedure sequentially on each edge: It queries the
given edge until it receives
$c=\lceil\log_{\frac{1-p}{p}}\left(\frac{1}{\delta}\right)\rceil$ more
positive answers than negative ones, or until the global predetermined budget
of queries is consumed. If the algorithm runs out of queries then it reports
the tree as disconnected, otherwise it reports it as connected.

Focus on the queries on a given edge $e$ and let $Y_{i}$ be a random variable
that takes the value $1$ if the $i$-th query is positive and $-1$ otherwise.
Let $X_{i}$ be the sum of $Y_{j}$ for the first $i$ queries on edge $e$. The
random variable $X_{i}$ counts the difference of the amount of positive and
negative answers from queries performed on $e$. The sequence
$\\{X_{t}\\}_{t\geq 0}$ is a Markov process and specifically a biased random
walk. The transition probabilities are the following

$\makebox[100.00015pt][l]{\text{If $e$ is
realized:}}\begin{cases}\textbf{Pr}\left[X_{t+1}=X_{t}+1\right]=1-p\\\
\textbf{Pr}\left[X_{t+1}=X_{t}-1\right]=p\\\ \end{cases}$

$\makebox[100.00015pt][l]{\text{If $e$ is non-
realized:}}\begin{cases}\textbf{Pr}\left[X_{t+1}=X_{t}+1\right]=p\\\
\textbf{Pr}\left[X_{t+1}=X_{t}-1\right]=1-p\\\ \end{cases}$

Since $p<\frac{1}{2}$, if the edge $e$ is realized, the random walk is biased
towards positive values and if $e$ does not exist, the random walk is biased
towards negative values. Therefore, if we had infinite amount of queries, the
random walk of a realized edge would surpass any positive threshold with
probability $1$, whereas the random walk of a non-existing edge would have
exponentially small probability of even reaching the threshold. However, now
that we can perform a finite number of queries, there is a constant
probability that at least one of the positive edges will fail to reach the
threshold. We prove that the selected threshold and total budget yield an
$(\epsilon,\delta)$ probability guarantee.

First, we calculate the probability to miss-classify a disconnected tree. Let
$A\subseteq E(T),\ A\neq\emptyset,$ be the subset of the tree’s edges that do
not exist. In order for Algorithm 1 to miss-classify $T$ as connected, the
random walk of all the edges in $A$ must surpass the threshold. Hence, the
probability of failure is upper bounded by the probability that a single edge
of $A$ surpasses the threshold

$\displaystyle\textbf{Pr}\left[\text{ALG\ fails\ on\ }T\right]$
$\displaystyle=\prod_{e\in A}\textbf{Pr}\left[e\ \text{passes\ the\
threshold}\right]$ $\displaystyle\leq\textbf{Pr}\left[e\in A\ \text{passes\
the\ threshold}\right]$

We will calculate the probability that a non-realized edge $e$ reaches the
threshold. Let $T_{c}$ be the threshold hitting time of the edge’s random
walk, that is

$T_{c}=\inf\left\\{t:X_{t}=\left\lceil\log_{\frac{1-p}{p}}\left(\frac{1}{\delta}\right)\right\rceil\right\\}$

The probability that the edge reaches the threshold within the query budget is
of course bounded by the probability to reach the same threshold in infinite
amount of steps. Therefore the probability of failure is bounded by

$\textbf{Pr}\left[T_{c}<+\infty\right]$

We define the potential function $\Phi:\mathbb{Z}\to\mathbb{N}$, as the
probability to hit the threshold given that we start at a specific location

$\Phi(x)=\textbf{Pr}\left[T_{c}<+\infty|X_{0}=x\right]$

Using a first step analysis and the Markov property we arrive at the following
equations system for $\Phi$

$\begin{cases}\Phi(x)=p\ \Phi(x+1)+(1-p)\ \Phi(x),\ \forall x\in[0,c)\\\
\Phi(c)=1\end{cases}$

where $c=\lceil\log_{\frac{1-p}{p}}\left(\frac{1}{\delta}\right)\rceil$.

From the above system we get that

$\Phi(x)=\left(\frac{1-p}{p}\right)^{x-c},\ x\in[0,c]$

Given the potential function, the probability of failure is bounded as follows

$\textbf{Pr}\left[\text{ALG fails on}\
T\right]\leq\Phi(0)=\left(\frac{1-p}{p}\right)^{-\lceil\log_{\frac{1-p}{p}}\left(\frac{1}{\delta}\right)\rceil}\leq\delta$

Now given a tree $T^{\prime}$ that is connected, we will calculate the
probability that Algorithm 1 miss-classifies it as disconnected. We, again,
focus on the random walk of a single edge $e$ and define $T_{c}$ as
previously. Now that the $e$ is realized, we will calculate the expected
number of queries to reach the threshold, by using the below potential
function.

$g(x)=\mathbb{E}\left[T_{c}|X_{0}=x\right]$

In a similar manner, we construct the following equations system for $g$

$\begin{cases}g(x)=1+(1-p)\ g(x+1)+p\ g(x),\ \forall x\in[0,c)\\\
g(c)=0\end{cases}$

The above system yields the following solution for $g$

$g(x)=\tilde{A}\left[\left(\frac{p}{1-p}\right)^{x}-\left(\frac{p}{1-p}\right)^{c}\
\right]+\frac{x-c}{2p-1}$

for some real constant $\tilde{A}$ and
$c=\lceil\log_{\frac{1-p}{p}}\left(\frac{1}{\delta}\right)\rceil$. This gives
us the following bound on the expected value of $T_{c}$

$\mathbb{E}\left[T_{c}|X_{0}=0\right]=g(0)\leq\frac{c}{1-2p}$

Let $\ T_{c}^{1},\ \dots,\ T_{c}^{n}\ $ be the hitting times of the random
walks of each edge of $T^{\prime}$. The only way in which Algorithm 1 can
miss-classify $T^{\prime}$ as disconnected is if the queries required for all
edges to reach the threshold are more than the available budget. Therefore,
using Markov’s inequality, the probability of failure is bounded as follows

$\displaystyle\textbf{Pr}\left[\text{ALG\ fails\ on\ }T^{\prime}\right]$
$\displaystyle=\textbf{Pr}\left[S_{n}\geq\frac{1}{\epsilon}\cdot\frac{c}{1-2p}\cdot
n\right]$
$\displaystyle\leq\textbf{Pr}\left[S_{n}\geq\frac{1}{\epsilon}\cdot\mathbb{E}\left[S_{n}\right]\right]$
$\displaystyle\leq\epsilon$

where $S_{n}=\sum_{i=1}^{n}T_{c}^{i}$ ∎

##  Appendix B Proofs from Section 4

See 4.3

###### Proof of Lemma 4.3.

Fix an edge $e$, and assume that the algorithm performs $k=\log(m^{2})/(1-2p)$
queries on it. Then the probability of receiving more true than false query
responses for $e$ (ie. of uncovering it correctly in the first step of the
algorithm) equals

$\displaystyle\textbf{Pr}\left[\text{correctly uncover}\ e\right]$
$\displaystyle=1-\textbf{Pr}\left[\text{incorrectly uncover}\ e\right]$
$\displaystyle\geq 1-\textbf{Pr}\left[X_{e}<k/2\right]$

where $X_{e}\sim\text{Binom}(k,(1-p))$ is the random variable counting the
number of true responses for this edge. By using Hoeffding’s inequality to
bound the tail of a binomial distribution we obtain

$\displaystyle\textbf{Pr}\left[\text{correctly uncover}\ e\right]$
$\displaystyle\geq 1-\exp\left(-2k\left(1/2-p\right)\right)$
$\displaystyle=1-\exp\left(-k\left(1-2p\right)\right)$
$\displaystyle=1-\frac{1}{m^{2}}$

Then the probability of correctly uncovering all $m$ edges of the graph is

$\textbf{Pr}\left[\text{correctly uncover
all}\right]\geq\left(1-\frac{1}{m^{2}}\right)^{m}\geq 1-\frac{1}{m}$

where the last step is an application of Bernoulli’s inequality. Thus, with
high probability, our algorithm succeeds in finding a realized spanning tree.
∎

##  Appendix C Proofs from Section 5

See 5.2

###### Proof of Lemma 5.2.

Let $T$ be any realized spanning tree. If an algorithm repeatedly queries all
$m$ edges of the moldgraph in a Round-Robin fashion, then by a Coupon
Collector’s argument on the $n-1$ edges of $T$ it will need $O(\log n)$ rounds
of queries on expectation, until it uncovers all edges of the spanning tree.
Thus giving us $O(m\log n)$ queries in total. ∎

See 5.4

###### Proof of Lemma 5.4.

The algorithm proceeds in rounds. In each round it queries one edge from each
of the sets of $\mathcal{S}$, performing a total of $k$ queries per round. The
probability of getting a False Negative answer for a realized edge of $E_{f}$
is $p<1/2$ and the number of queries performed on this edge follows a
geometric distribution with parameter $1-p$. Thus, the expected number of
queries needed to discover a realized edge of $E_{f}$ is at most $2|E_{f}|$.
As the algorithm queries exactly one edge per round, it will run in $2|E_{f}|$
rounds, giving a total of $2k|E_{f}|$ queries in expectation. ∎

##  Appendix D Proofs from Section 6

See 6.5

###### Proof of Lemma 6.5.

We will prove Lemma 6.5 by induction on the number of non-realized edges of
$G$. We denote the edge set of $G$ by $E(G)$, the faces of $G$ by $F(G)$ and
the set of vertices of $G$ by $V(G)$.

#### Base Case:

Suppose that $G$ only has $1$ non-realized edge, that is
$E(G)=E(T)\cup\\{e\\}$. We know that the realized subgraph $T$ of $G$ is a
tree, therefore $|E(T)|=|V(G)|-1$ and $|E(G)|=|V(G)|$. As a result, the graph
$G$ contains exactly one cycle and two faces; one that is enclosed by the
cycle and the outer face. The dual graph $G^{\prime}$ will have exactly two
vertices, one for each face, which will be connected by all the edges of the
cycle. Therefore, the induced subgraph of $G^{\prime}$ that contains only the
non-realized edge $e$ will be a spanning tree of $G^{\prime}$.

#### Induction step:

Assume that for every graph $G$ with at most $k$ non-realized edges, these
edges form a spanning tree of the dual graph $G^{\prime}$. We will show that
for all graphs $G$ with $k+1$ non-realized edges, these edges also form a
spanning tree of $G^{\prime}$.

Let $G$ be a graph with $n$ vertices, $n-1$ realized edges that form a
realized tree $T$ and $k+1$ non-realized edges. Let also $e$ be a non-realized
edge of $G$. We remove $e$ from $G$ and take the induced subgraph $G_{e}$. The
induction step holds for $G_{e}$, hence its $k$ non-realized edges form a
spanning tree of its dual graph $G_{e}^{\prime}$. By adding the edge $e$ in
$G_{e}$, we form a new face $f_{e}$. We can also see this from Euler’s
formula:

$\displaystyle V(G)+F(G)$ $\displaystyle=E(G)+2$ $\displaystyle=E(G_{e})+1+2$
$\displaystyle=V(G_{e})+F(G_{e})+1$ $\displaystyle\Rightarrow F(G)$
$\displaystyle=F(G_{e})+1$

For the new face $f_{e}$, there are two cases:

  1. 1.

Edge $e$ divides an old face into two new faces, one of them being $f_{e}$. In
this case, the vertex of the old face in the dual graph $G_{e}^{\prime}$ will
be expanded into two vertices that are connected by $e$ and, using the
induction step, the $k+1$ non-realized edges will form a spanning tree of
$G^{\prime}$.

  2. 2.

Edge $e$ closes a new cycle and encloses the new face $f_{e}$. The vertex of
the face $f_{e}$ will be connected by $e$ to the vertex of the outer face. As
a result, the $k+1$ non-realized edges will form a spanning tree of
$G^{\prime}$.

∎

See 6.2

###### Proof of Lemma 6.2.

The algorithm that achieves the guarantees of the theorem is similar to the
one for the 2-sided error oracle, with the difference that instead of
categorizing edges as realized/non-realized based on the majority of query
responses, we consider an edge as non-realized when it receives at least one
“No” response, and as realized otherwise. In this case we perform
$k=\log_{2}(m^{2})$ queries on each edge. Thus, to bound the probability of
failure for a single edge it suffices to bound the probability of a non-
realized edge giving $k$ false “Yes” responses. This equals

$\textbf{Pr}\left[\text{uncorrectly uncover}\ e\right]\leq
p^{k}<\left(\frac{1}{2}\right)^{k}=\frac{1}{m^{2}}$

The rest of the proof is the same as for the 2-sided error oracle, and gives
us that the algorithm succeeds with probability $(1-1/m)$. ∎

(a) The moldgraph used for the proof of Theorem 6.3

(b) A realized graph from the family mentioned in the proof of Theorem 6.3.
The dotted lines are non-realized edges and by the edges lie the answers of
the 1-sided FP noisy oracle.

Figure 3:

See 6.3

###### Proof of Theorem 6.3.

The outline of this proof is very similar to that of Lemma 4.4. Consider the
graph in Figure 3 which has $n+1$ vertices and $2n$ edges. Between any two
consecutive vertices exist 2 parallel edges. Half of the edge-pairs are
arbitrarily picked to have only 1 realized edge, while in the other half both
of their edges are realized.

Every time that we receive a negative query response for an edge, we can be
certain that this edge is not realized and thus discard it. Now, call “bad
pair” an edge-pair having one non-realized edge for which the algorithm
receives $k$ consecutive positive query responses. We set
$k=\Theta(\log(n/\log n))=\Theta(\log n)$, which gives us
$\textbf{Pr}\left[\text{bad}\right]\geq\log n/n$. Thus the probability that at
least one such “bad pair” exists is

$\textbf{Pr}\left[\text{bad exists}\right]\geq 1-\left(1-\frac{\log
n}{n}\right)^{n/2}\geq 1-\frac{1}{n}$

Note that this “bad pair” should have received the exact same responses as
edge-pairs having two realized edges. There are $n/2=\Theta(n)$ such pairs and
the “bad pair” will be indistinguishable from them, as they have been picked
arbitrarily. Thus, by a similar argument as in Theorem 4.4 we conclude that
any algorithm with constant probability of failure requires $\Omega(n\log n)$
queries to discover a spanning tree in this specific graph instance.

The desired $\Omega(m\log m)$ lower bound again results from the fact that if
we had an algorithm performing better than $\Omega(m\log m)$ queries, it would
perform better than $\Omega(n\log n)$ in this instance, as it has $m=O(n)$. ∎


# Lattice operads and operad filtrations

Denis Bashkirov<EMAIL_ADDRESS>Czech Academy of Sciences, Institute of
Mathematics, Žitná 25, 115 67 Prague 1, Czech Republic

(Date: December 30, 2022)

###### Abstract.

The aim of the note is to elaborate on the notion of a filtration of an operad
defined in terms of a lattice-valued operad serving as an indexing object.
That covers ordinary ${\mathbb{Z}}$-indexed filtrations of associative
algebras and operads as a special case, yet the notion appears to be natural
enough to include examples of other kind as well.

##  1\. Introduction

Filtrations and gradings, being a standard tool for studying structural
properties of associative algebras, rings and modules, admit a natural and
straightforward generalization to the realm of operads. While examples and
applications of operad filtrations freely available in the literature concern
primarily the case of filtrations indexed by the integers [LV12], the aim of
the present note is to elaborate on the notion of a filtration of a (linear)
operad defined by means of a more flexible indexing object, that being a
poset-valued or, more specifically, a lattice-valued operad. Such an indexing
object is meant to relate, in a reasonably fine way, the natural partial order
on the set of all linear subspaces of each component ${\mathcal{P}}(n)$ of a
given operad ${\mathcal{P}}$ with the operadic compositions within
${\mathcal{P}}$. The construction encompasses, in particular, both the
standard case of the $\mathbb{Z}$-indexed filtrations and filtrations by the
multiindex operad $M\mathbb{Z}$ that were used in [BM22] for studying algebras
of multilinear differential operators, cf. Example 1(b). It should be pointed
out that the concept of a filtration by an ordered operad, along with some
applications pertaining to distributive laws for Koszul operads, is originally
due to A.Khoroshkin and V.Dotsenko [Kho06, Dot07]; see Example 1(f) for an
account of their operad of inversions.

The note is organized as follows. In section 2 we introduce the notion of a
lattice operad and present some basic results concerning formal properties
thereof, along with a few examples. The corresponding notion of a filtration
indexed by a lattice operad is discussed in section 3. Among some basic
technical results, we establish the functorial properties of this construction
(Theorems 1 and 2) and show (Proposition 1) that the set-valued functor of all
filtrations of a given linear operad is representable. We would note that some
of the results presented in sections 2 and 3 can be generalized to the case of
semilattice-valued and, more generally, poset-valued operads.

As apparent from the case of associative algebras and modules, for practical
reasons it is worth to single out filtrations of a particularly simple
structure, namely, the ones that admit a characterization in terms of a
certain generating set (the standard filtrations), as well as filtrations with
some additional compositional constraints (such as, for instance, the
$D$-filtrations). As the organizing principle here, for a given linear operad
${\mathcal{P}}$ and an indexing lattice operad $L$, filtrations with
properties of interest are introduced via closure operators on the complete
lattice of all subspaces of ${\mathcal{P}}$ (done arity-wise) indexed by $L$.
We present some relevant examples in section 4. In the remaining part we
discuss the notion of the associated graded for a filtered operad.

### Conventions

Throughout the text the term operad stands for a symmetric operad in the
category of sets, lattices or vector spaces (possibly, graded) over a ground
field ${\mathbb{K}}$ with their standard symmetric monoidal structures.

##  2\. Lattice operads

Let ${\mathtt{Lat}}$ be the cartesian symmetric monoidal category of lattices
and lattice homomorphisms. The natural partial order on a lattice $L$ is
defined via $a\leq b\Leftrightarrow a=a\wedge b$ for all $a,b\in L$. In
particular, any homomorphism $f:L\to K$ of lattices is monotonic in the sense
that $a\leq b\Rightarrow f(a)\leq f(b)$ for all $a,b\in L$. By a _lattice
operad_ we mean a symmetric operad in ${\mathtt{Lat}}$.

######  Lemma 1.

Let $L$ be a lattice operad. Then

  1. (a)

the $\circ_{i}$-compositions are monotonic. That is, for any $m,n\geq 1$,
$1\leq i\leq m$, $c\in\mathcal{P}(n)$ and $a,b\in\mathcal{P}(m)$ such that
$a\leq b$,

$a\circ_{i}c\leq b\circ_{i}c,$

Similarly, for any $1\leq j\leq n$,

$c\circ_{j}a\leq c\circ_{j}b.$

  2. (b)

The $\circ_{i}$-compositions are weakly distributive. That is,

(1a) $\displaystyle a\circ_{i}(b\wedge c)$
$\displaystyle\leq(a\circ_{i}b)\wedge(a\circ_{i}c)$ (1b) $\displaystyle
a\circ_{i}(b\vee c)$ $\displaystyle\geq(a\circ_{i}b)\vee(a\circ_{i}c)$

for all $m,n\geq 1$, $1\leq i\leq m$, $a\in\mathcal{P}(m)$,
$b,c\in\mathcal{P}(n)$, and

(2a) $\displaystyle(a\wedge b)\circ_{i}c\leq(a\circ_{i}c)\wedge(b\circ_{i}c)$
(2b) $\displaystyle(a\vee b)\circ_{i}c\geq(a\circ_{i}c)\vee(b\circ_{i}c)$

for all $m,n\geq 1$, $1\leq i\leq m$, $a,b\in\mathcal{P}(m)$,
$c\in\mathcal{P}(n)$.

###### Proof.

  1. (a)

Let $a\leq b$ for some $a,b\in{\mathcal{P}}(m)$ and $c\in{\mathcal{P}}(n)$.
Then by definition of the monoidal structure on ${\mathtt{Lat}}$, we have
$(a,c)\leq(b,c)$ in $L(m)\times L(n)$. Now, since $\circ_{i}:L(m)\times
L(n)\to L(m+n-1)$ is a lattice homomorphism and, hence, is monotonic, the
first comparison follows. The second one can be established in the same way.

  2. (b)

We will derive the first comparison. The remaining three are analogous. To
this end, notice first that for any $x,y,z\in L$, we have

(3) $\displaystyle x\leq y,\,x\leq z\Rightarrow x\leq y\wedge z.$

Indeed,

$x\wedge(y\wedge z)=(x\wedge y)\wedge z=x\wedge z=x.$

Now, let $a,b$ and $c$ be as stated in the hypothesis. Since $b\wedge c\leq b$
and $b\wedge c\leq c$, then by the previous part, we have $a\circ_{i}(b\wedge
c)\leq a\circ_{i}b$ and $a\circ_{i}(b\wedge c)\leq a\circ_{i}c$. The
conclusion now follows upon taking $x=a\circ_{i}(b\wedge c)$, $y=a\circ_{i}b$
and $z=a\circ_{i}c$ in (3).

∎

######  Example 1.

  1. (a)

Let $C{\mathbb{Z}}=\\{C{\mathbb{Z}}(n)\\}_{n\geq 1}$ be defined by
$C{\mathbb{Z}}(n):=\mathbb{Z}$ with the usual order (thus $\wedge$, $\vee$ are
the minimum and the maximum respectively) and the trivial action of the
symmetric group ${\mathbb{S}}_{n}$ for all $n\geq 1$. Define
$a\circ_{i}b:=a+b$ for all $a\in C{\mathbb{Z}}(m)$, $b\in C{\mathbb{Z}}(n)$
and $1\leq i\leq m$. Then $C{\mathbb{Z}}$ is a lattice operad.

  2. (b)

For $n\geq 1$, let $M\mathbb{Z}(n)$ be $\mathbb{Z}^{n}$ with the partial order
inherited from $\mathbb{Z}$. In particular, for each $n\geq 1$,
${M{\mathbb{Z}}}(n)$ is a lattice with the join and the meet operations being

$(p^{\prime}_{1},\ldots,p^{\prime}_{n})\vee(p^{\prime\prime}_{1},\ldots,p^{\prime\prime}_{n}):=(\max(p^{\prime}_{1},p^{\prime\prime}_{1}),\ldots,\max(p^{\prime}_{n},p^{\prime\prime}_{n}))$

and

$(p^{\prime}_{1},\ldots,p^{\prime}_{n})\wedge(p^{\prime\prime}_{1},\ldots,p^{\prime\prime}_{n}):=(\min(p^{\prime}_{1},p^{\prime\prime}_{1}),\ldots,\min(p^{\prime}_{n},p^{\prime\prime}_{n}))$

respectively. With the natural permutation action of ${\mathbb{S}}_{n}$ and
the partial compositions

$\circ_{i}:{M{\mathbb{Z}}}(m)\times{M{\mathbb{Z}}}(n)\to{M{\mathbb{Z}}}(m+n-1),\
n\geq 1,\ 1\leq i\leq m,$

defined for $({a}_{1},\ldots,{a}_{m})\in{M{\mathbb{Z}}}(m)$ and
$({b}_{1},\ldots,{b}_{n})\in{M{\mathbb{Z}}}(n)$ by

$({a}_{1},\ldots,{a}_{m})\circ_{i}({b}_{1},\ldots,{b}_{m}):=({a}_{1},\ldots,{a}_{i-1},b_{1}+a_{i},\ldots,b_{n}+a_{i},{a}_{i+1},\ldots,{a}_{m}),$

the collection ${M{\mathbb{Z}}}=\\{{M{\mathbb{Z}}}(n)\\}_{n\geq 1}$ makes up a
(unital) lattice operad.

An interested reader is referred to the appendix for an explicit description
of small-arity components of some lattice suboperads of ${M{\mathbb{Z}}}$.

  3. (c)

More generally, upon replacing $(\mathbb{Z},+,0)$ by a monoid $A$ in the above
construction, we obtain the word operad $\mathbb{W}A$, or the combinatorial
operad as per S.Giraudo [Gir15, Dot20]. Now, if $A$ is a totally ordered
monoid or, more generally, a monoid ordered with respect to a certain lattice
structure on it, then $\mathbb{W}A$ is a lattice operad.

  4. (d)

Generalizing the first example above, given a non-empty set $I$, we define the
counting operad $C{\mathbb{Z}}^{I}$ with respect to $I$ by setting
$C{\mathbb{Z}}^{I}(n):={\mathbb{Z}}^{I}$ with the natural lattice structure
inherited from ${\mathbb{Z}}$ as before, the trivial ${\mathbb{S}}_{n}$-action
and the partial compositions defined by setting $(a_{p})_{p\in
I}\circ_{i}(b_{p})_{p\in I}:=(a_{p}+b_{p})_{p\in I}$ for all $a=(a_{p})_{p\in
I}\in C{\mathbb{Z}}^{I}(n)$, $b=(b_{p})_{p\in I}\in C{\mathbb{Z}}^{I}(m)$,
$m,n\geq 1$ and $1\leq i\leq m$. The terminology is to be elucidated later,
cf. Example 3(d). The lattice operad $C{\mathbb{Z}}^{I}$ can be identified
with the $I$-fold cartesian product of the lattice operad $C{\mathbb{Z}}$ with
itself.

  5. (e)

Let $\mathcal{P}$ be a ${\mathbb{K}}$-linear operad. For each $n\geq 1$, take
$Sub(\mathcal{P})(n)$ to be the lattice of all ${\mathbb{K}}$-linear subspaces
of $\mathcal{P}(n)$ with the ${\mathbb{S}}_{n}$-action induced from
$\mathcal{P}(n)$. Given $m,n\geq 1$, $1\leq i\leq m$, and two subspaces $V\in
Sub(\mathcal{P})(m)$, $U\in Sub(\mathcal{P})(n)$, we define
$V\circ_{i}U:=\\{a\circ_{i}b|a\in V,b\in U\\}$. Then
$Sub(\mathcal{P}):=\\{Sub(\mathcal{P})(n)\\}_{n\geq 1}$ is a lattice operad.

  6. (f)

(A.Khoroshkin, V.Dotsenko [Kho06, Dot07]) Let ${\mathbb{F}}(a,b)$ be the free
symmetric operad on two generators $a,b$ of arity $2$ and let
$T\in{\mathbb{F}}(a,b)(n)$. One can identify $T$ with a rooted binary tree
with $n$ leaves and $n-1$ internal vertices labeled by $a$ and $b$. Define the
degree $\deg(T)$ to be the number of $a$’s among the labels, and the number of
inversions ${\text{inv}}(T)$ to be the number of pairs $(v_{1},v_{2})$ of
internal vertices of $T$ such that $v_{2}$ is a descendant of $v_{1}$, the
vertex $v_{1}$ is labeled by $b$ and $v_{2}$ is labeled by $a$.

((a)) $\deg(T)=3,{\text{inv}}(T)=2$

((b)) $\deg(T)=2,{\text{inv}}(T)=4$

For each $n\geq 2$, define

${\mathbb{F}}^{inv}(a,b)(n):=\\{(\deg(T),{\text{inv}}(T))|T\in{\mathbb{F}}(a,b)(n)\\}.$

As a set, ${\mathbb{F}}^{inv}(a,b)(n)$ consists of all integer tuples $(d,v)$
such that $0\leq d\leq n-1$ and $0\leq v\leq(n-d-1)\cdot d$. The figures above
depict some tree representatives of the elements $(3,2)$ and $(2,4)$ from
${\mathbb{F}}^{inv}(a,b)(5)$. In particular, figure (B) illustrates how a tree
$T$ with the maximum value of ${\text{inv}}(T)$ for a fixed $\deg(T)$ can be
constructed. For each $n\geq 2$, we equip ${\mathbb{F}}^{inv}(a,b)(n)$ with
the lexicographic order and the trivial ${\mathbb{S}}_{n}$-action.

Now, for $m,n\geq 2$, $(d,v)\in{\mathbb{F}}^{inv}(a,b)(n)$ and
$(e,w)\in{\mathbb{F}}^{inv}(a,b)(m)$, we define the partial compositions in
${\mathbb{F}}^{inv}(a,b)$ by setting

$(d,v)\circ_{i}(e,w):=(d+e,\max\limits_{T^{\prime},T^{\prime\prime}}({\text{inv}}(T^{\prime}\circ_{i}T^{\prime\prime})))$

for each $1\leq i\leq m$. Here, the maximum is taken over all trees
$T^{\prime}\in{\mathbb{F}}(a,b)(n)$, $T^{\prime\prime}\in{\mathbb{F}}(a,b)(m)$
such that $\deg(T^{\prime})=d$, ${\text{inv}}(T^{\prime})=v$ and
$\deg(T^{\prime\prime})=e$, ${\text{inv}}(T^{\prime\prime})=w$. That makes
${\mathbb{F}}^{inv}(a,b)=\\{{\mathbb{F}}^{inv}(a,b)(n)\\}_{n\geq 2}$ a lattice
operad, which is actually a totally ordered set in each arity.

######  Definition 1.

A _lax morphism_ of lattice operads $f:K\to L$ is a family of
${\mathbb{S}}_{n}$-equivariant lattice homomorphisms $f_{n}:K(n)\to L(n)$ for
all $n\geq 1$ such that

(4) $\displaystyle f(a)\circ_{i}f(b)\leq f(a\circ_{i}b)$

for all $m,n\geq 1$, $1\leq i\leq m$, $a\in K(m)$, $b\in K(n)$.

Lattice operads together with lax morphisms form a category that we denote as
${\mathtt{LatOper}}$. Indeed, we have the following simple

######  Lemma 2.

Let $K,L,M$ be lattice operads. The composition of lax morphisms
$K\overset{f}{\to}L\overset{g}{\to}M$ is a lax morphism.

###### Proof.

Let $m,n\geq 1$, $1\leq i\leq m$ and $a\in K(m)$, $b\in K(n)$. Since $g$ is
lax, we have

$\displaystyle(g\circ f)(a)\circ_{i}(g\circ f)(b)=g(f(a))\circ_{i}g(f(b))\leq
g(f(a)\circ_{i}f(b)).$

Since $f(a)\circ_{i}f(b)\leq f(a\circ_{i}b)$ due to $f$ being lax, and $g$ on
the right-hand side is monotonic as a lattice homomorphism $L(m+n-1)\to
M(m+n-1)$, then

$g(f(a)\circ_{i}f(b))\leq g(f(a\circ_{i}b))=(g\circ f)(a\circ_{i}b)$

completing the proof. ∎

Clearly, any morphism of lattice operads in the usual sense is lax. The
converse is not true as shows the following

######  Example 2.

Let $C{\mathbb{Z}}$ and $M\mathbb{Z}$ be as in Example 1. The mapping
$\rho:C{\mathbb{Z}}\to M\mathbb{Z}$ defined by setting

$\rho(k):=\underbrace{(k,\dots,k)}_{n}$

for all $n\geq 1$ and $k\in C{\mathbb{Z}}(n)={\mathbb{Z}}$ is a lax morphism.

To see that it is not, in fact, an operad morphism in the ordinary sense, take
$n=2$, $1\in C{\mathbb{Z}}(2)$ and observe that
$\rho(1)\circ_{1}\rho(1)=(1,1)\circ_{1}(1,1)=(2,2,1)$, while
$\rho(1\circ_{1}1)=\rho(\underbrace{1+1}_{\in C{\mathbb{Z}}(3)})=(2,2,2).$

##  3\. Filtrations by lattice operads

The following is a generalization of the standard notion of a filtration of an
associative algebra indexed by an ordered monoid.

######  Definition 2.

Let $L$ be a lattice operad. An (increasing) _$L$ -filtration_
$F{\mathcal{P}}=\\{F_{p}{\mathcal{P}}(n)\\}_{p\in L(n),n\geq 1}$ of a
${\mathbb{K}}$-linear operad ${\mathcal{P}}$ is a collection of
${\mathbb{K}}$-subspaces of $F_{p}{\mathcal{P}}(n)\subset{\mathcal{P}}(n)$
indexed by the elements $p\in L(n)$ for all $n\geq 1$ subject to the following
conditions:

  * (i)

Monotonicity: $F_{p^{\prime}}{\mathcal{P}}(n)\subset
F_{p^{\prime\prime}}{\mathcal{P}}(n)$ for all $p^{\prime},p^{\prime\prime}\in
L(n)$ such that $p^{\prime}\leq p^{\prime\prime}$.

  * (ii)

Equivariance:
$F_{p}{\mathcal{P}}(n)\cdot\sigma=F_{p\cdot\sigma}{\mathcal{P}}(n)$ for all
$p\in L(n)$ and $\sigma\in{\mathbb{S}}_{n}$.

  * (iii)

Compositional compatibility:
$F_{a}{\mathcal{P}}(m)\circ_{i}F_{b}{\mathcal{P}}(n)\subset
F_{a\circ_{i}b}{\mathcal{P}}(m+n-1)$ for all $a\in L(m)$, $b\in L(n)$ and
$1\leq i\leq m$.

  * (iv)

Unitality: if $L(1)$ has the smallest element $\mathbf{0}$ and
$e\in\mathcal{P}(1)$ is the operadic unit, if it exists, then
${\mathbb{K}}\cdot e\subset F_{\mathbf{0}}\mathcal{P}(1)$.

######  Remark 1.

There is an obvious dualization of the above definition covering the case of
decreasing filtrations. A typical use-case thereof is a filtration of an
operad by the powers of an operadic ideal; a compelling example can be found
in [Dot19].

Some terminology from the realm of associative algebras can be readily
extrapolated to this context. Namely, an $L$-filtration $F{\mathcal{P}}$ is
said to be _exhaustive_ if ${\mathcal{P}}(n)=\bigcup\limits_{p\in
L}F_{p}{\mathcal{P}}(n),$ for all $n\geq 1$ and is said to be _bounded below_
if for any $n\geq 1$, there exists $b_{n}\in L(n)$ such that
$F_{p}{\mathcal{P}}(n)=0$ for all $p\leq b_{n}$. Dually, an $L$-filtration
$F{\mathcal{P}}$ is called _stabilized_ if for any $n\geq 1$, there exists
$c_{n}\in L(n)$ such that $F_{p}{\mathcal{P}}=F_{p\wedge c_{n}}{\mathcal{P}}$
for any $p\geq c_{n}$.

We say that an $L$-filtration $F{\mathcal{P}}$ is _saturated_ if

$F_{p^{\prime}}{\mathcal{P}}(n)\cap
F_{p^{\prime\prime}}{\mathcal{P}}(n)\subset F_{p^{\prime}\wedge
p^{\prime\prime}}{\mathcal{P}}(n)$

for all $n\geq 1$, $p^{\prime},p^{\prime\prime}\in L(n)$. This property is
vacuous for ${\mathbb{Z}}$-indexed filtrations of associative algebras, but it
is non-trivial in the context of filtrations by lattice operads.

######  Example 3.

  1. (a)

The ordinary notion of a ${\mathbb{Z}}$-indexed filtration of an associative
algebra can be recovered from the above definition. Indeed, let
$C{\mathbb{Z}}$ be the lattice operad of Example 1(a). Then an (increasing)
filtration $FA=\\{F_{n}A\\}_{n\in\mathbb{Z}}$ of an associative
${\mathbb{K}}$-algebra $A$ can be identified with the corresponding
$C{\mathbb{Z}}$-filtration of $A$, when the latter is regarded as an
${\mathbb{K}}$-linear operad concentrated in arity $1$.

  2. (b)

For any lattice operad $L$ and any ${\mathbb{K}}$-linear operad
${\mathcal{P}}$, there is a trivial exahaustive $L$-filtration
$\mathbf{1}\mathcal{P}$ of $\mathcal{P}$ defined by
$\mathbf{1}_{p}\mathcal{P}(n)=\mathcal{P}(n)$ for all $n\geq 1$ and $p\in
L(n)$.

  3. (c)

For any ${\mathbb{K}}$-linear operad ${\mathcal{P}}$ there is a _tautological_
filtration $\tau{\mathcal{P}}$ of ${\mathcal{P}}$ by the lattice operad
$Sub({\mathcal{P}})$ as per Example 1(e). Namely, for all $n\geq 1$ and $U\in
Sub({\mathcal{P}})(n)$, we set $F_{U}{\mathcal{P}}(n):=U$.

  4. (d)

Let $E:=\\{\mu_{i}|i\in I\\}$ for some $I\neq\varnothing$ and
${\mathbb{F}}(E)$ be the free ${\mathbb{K}}$-linear operad on the generators
$E$. No conditions are imposed on the arities of $\mu_{i}$’s. Given a tuple
$p=(p_{i})_{i\in I}\in{\mathbb{Z}}^{I}$ and $n\geq 1$, we define
$F_{p}{\mathbb{F}}(E)(n)$ to be the linear span of all partial-composition
monomials $\nu$ in generators $E$, of arity $n$ and such that each $\mu_{i}$
appears as a factor in $\nu$ no more than $p_{i}$ times. In particular,
$F_{p}{\mathbb{F}}(E)(n)=0$ whenever $p_{i}\leq 0$ for all $i\in I$. Since
${\mathbb{F}}(E)$ is free, it follows quite easily that the collection
$\\{F_{p}{\mathbb{F}}(E)(n)\\}_{n\geq 1,p\in{\mathbb{Z}}^{I}}$ is a bounded
$C{\mathbb{Z}}^{I}$-filtration of ${\mathbb{F}}(E)$, where $C{\mathbb{Z}}^{I}$
is the counting operad introduced in Example 1(d). Here, each tuple $p\in
C{\mathbb{Z}}^{I}(n)$ counts, or rather gives an upper bound for, the number
of occurrences of each of the generators $\mu_{i}$ in the monomial expressions
appearing in $F_{p}{\mathbb{F}}(E)(n)$.

A certain modification of the above construction allows one to introduce in a
similar way a $C{\mathbb{Z}}^{I}$-filtration for a general
${\mathbb{K}}$-linear operad ${\mathcal{P}}$ upon choosing a presentation
${\mathcal{P}}={\mathbb{F}}(E)/(\mathcal{R})$. This is to be addressed later
in Corollary 2 below.

  5. (e)

Let $A$ be a commutative associative ${\mathbb{K}}$-algebra $A$. A multilinear
differential operator is a mapping $\delta:A^{\otimes n}\to A$ such that
$\delta=\delta(x_{1},\dots,x_{n})$ is a differential operator of order $\leq
d_{i}$ in each variable $x_{i}$ for the fixed values of all the remaining
arguments. A prototypical example to have in mind is that of a Poisson or,
more generally, a Jacobi algebra $A$, whose bracket $\\{-,-\\}:A\otimes A\to
A$ is a differential operator of order one in each variable. Thus $\delta$ can
be assigned a tuple $(d_{1},\dots,d_{n})\in\mathbb{Z}_{\geq 0}^{n}$.

All multilinear differential operators on $A$ taken together form a suboperad
$\mathcal{D}iff_{A}$ of the endomorphism operad $\mathcal{E}nd(A)$, which
carries a natural ${M{\mathbb{Z}}}$-filtration by the tuple of orders
$(d_{1},\dots,d_{n})$, $n\geq 1$ [BM22]. In particular, the combinatorics of
the lattice suboperad of ${M{\mathbb{Z}}}$ generated by the element
$(1,1)\in{M{\mathbb{Z}}}(2)$ arises in connection with Poisson and Jacobi
algebras.

Given a lattice operad $L$ and a ${\mathbb{K}}$-linear operad $P$, let
$Filt(L,\mathcal{P})$ be the set of all $L$-filtrations of $\mathcal{P}$. This
assignment is functorial contravariantly in $L$ and covariantly in
${\mathcal{P}}$. Indeed, first, we have the following

######  Theorem 1.

Let ${\mathcal{P}}$ be a ${\mathbb{K}}$-linear operad and $f:K\to L$ be a lax
morphism of lattice operads. Define $f^{*}:Filt(L,{\mathcal{P}})\to
Filt(K,{\mathcal{P}})$ by setting

$(f^{*}(F{\mathcal{P}})_{p}{\mathcal{P}})(n):=F_{f(p)}{\mathcal{P}}(n)$

for any $L$-filtration $F{\mathcal{P}}$, all $n\geq 1$ and $p\in K(n)$. Then

  1. (a)

$f^{*}(F{\mathcal{P}}){\mathcal{P}}$ is a well-defined $K$-filtration.

  2. (b)

$(gf)^{*}=f^{*}g^{*}$ for any pair of lax morphisms
$K\overset{f}{\to}L\overset{g}{\to}M$.

###### Proof.

  1. (a)

To simplify the notation, we denote $f^{*}(F{\mathcal{P}}){\mathcal{P}}$ by
$G{\mathcal{P}}$. To check monotonicity of $G{\mathcal{P}}$, let
$p,q~{}\in~{}K(n)$ be such that $p\leq q$. Then $f(p)\leq f(q)$, since
$f:K(n)\to L(n)$, being a lattice homomorphism, is monotonic. Now, by
monotonicity of $F{\mathcal{P}}$,

$G_{p}{\mathcal{P}}(n)=F_{f(p)}{\mathcal{P}}(n)\subset
F_{f(q)}{\mathcal{P}}(n)=G_{q}{\mathcal{P}}(n).$

To check the compositional compatibility, let $n\geq 1$, $1\leq i\leq m$ and
$p\in K(m)$, $q\in K(n)$. Then

$\displaystyle G_{p}{\mathcal{P}}(m)\circ_{i}G_{q}{\mathcal{P}}(n)$
$\displaystyle=F_{f(p)}{\mathcal{P}}(m)\circ_{i}F_{f(q)}{\mathcal{P}}(n)$
$\displaystyle\subset F_{f(p)\circ_{i}f(q)}{\mathcal{P}}(n)$
$\displaystyle\subset
F_{f(p\circ_{i}q)}{\mathcal{P}}(m+n-1)=G_{p\circ_{i}q}{\mathcal{P}}(m+n-1)$

Here, the first inclusion follows from compositional compatibility for
$F{\mathcal{P}}$ and the second one follows by the defining property of a lax
morphism (4) and monotonicity.

Equivariance and unitality of $G{\mathcal{P}}$ are straightforward.

  2. (b)

Let $F{\mathcal{P}}$ be a $M$-filtration of ${\mathcal{P}}$, $n\geq 1$ and
$p\in K(n)$. Denote $g^{*}(F{\mathcal{P}})$ by $G{\mathcal{P}}$. Then
$G_{p}{\mathcal{P}}=F_{g(p)}{\mathcal{P}}$ and, assuming arity $n$ everywhere,
we have

(5)
$\displaystyle((gf)^{*}F{\mathcal{P}})_{p}{\mathcal{P}}=F_{g(f(p))}{\mathcal{P}}=(f^{*}G_{p}{\mathcal{P}}){\mathcal{P}}=(f^{*}(g^{*}F_{p}{\mathcal{P}})){\mathcal{P}}=((f^{*}g^{*})F{\mathcal{P}})_{p}{\mathcal{P}}$

∎

######  Corollary 1.

By virtue of Example 2, any $M\mathbb{Z}$-filtration of a
${\mathbb{K}}$-linear operad ${\mathcal{P}}$ gives rise to a
$C{\mathbb{Z}}$-filtration of ${\mathcal{P}}$.

######  Theorem 2.

Let $L$ be a lattice operad and $\phi:{\mathcal{P}}\to{\mathcal{Q}}$ be a
morphism of ${\mathbb{K}}$-linear operads. Define
$\phi_{*}:Filt(L,{\mathcal{P}})\to Filt(L,{\mathcal{Q}})$ by setting

$(\phi_{*}(F{\mathcal{P}})_{p}{\mathcal{Q}})(n):=\phi(F_{p}{\mathcal{P}}(n))$

for any $L$-filtration $F{\mathcal{P}}$, all $n\geq 1$ and $p\in L(n)$. Then

  1. (1)

$\phi_{*}(F{\mathcal{P}}){\mathcal{Q}}$ is a well-defined $L$-filtration.

  2. (2)

$(\psi\phi)_{*}=\psi_{*}\phi_{*}$ for any pair of ${\mathbb{K}}$-linear operad
morphisms
${\mathcal{P}}\overset{\phi}{\to}{\mathcal{Q}}\overset{\psi}{\to}\mathcal{R}$.

###### Proof.

  1. (1)

To simplify the notation, we denote $\phi_{*}(F{\mathcal{P}}){\mathcal{Q}}$ by
$G{\mathcal{Q}}$. To check monotonicity of $G{\mathcal{Q}}$, let $p,q\in L(n)$
be such that $p\leq q$. Then by monotonicity of $F{\mathcal{P}}$,

$G_{p}{\mathcal{P}}=\phi(F_{p}{\mathcal{P}})\subset\phi(F_{q}{\mathcal{P}})=G_{q}{\mathcal{P}}.$

To check the compositional compatibility, let $n\geq 1$, $1\leq i\leq m$ and
$p\in L(m)$, $q\in L(n)$. Then

$\displaystyle G_{p}{\mathcal{Q}}(m)\circ_{i}G_{q}{\mathcal{Q}}(n)$
$\displaystyle=\phi(F_{p}{\mathcal{P}}(m))\circ_{i}\phi(F_{q}{\mathcal{P}}(n))=\phi(F_{p}{\mathcal{P}}(m)\circ_{i}F_{q}{\mathcal{P}}(n))$
$\displaystyle\subset\phi(F_{p\circ_{i}q}{\mathcal{P}}(m+n-1))=G_{p\circ
q}{\mathcal{Q}}(m+n-1)$

Equivariance follows from the definition of an operad morphism and the
equivariance property of $F{\mathcal{P}}$. Unitality is straightforward.

  2. (2)

Let $p\in L(n)$. Suppressing arity $n$ for the sake of brevity, we have

$((\psi\phi)_{*}(F{\mathcal{P}})_{p}){\mathcal{Q}}=(\psi\circ\phi)(F_{p}{\mathcal{P}})=\psi(\phi(F_{p}{\mathcal{P}}))=\psi(\phi_{*}(F{\mathcal{P}})_{p}{\mathcal{Q}})=\psi_{*}(\phi_{*}(F{\mathcal{P}})_{p}{\mathcal{Q}}).$

∎

######  Corollary 2.

Let ${\mathcal{P}}$ be a ${\mathbb{K}}$-linear operad defined in terms of a
presentation ${\mathcal{P}}={\mathbb{F}}(E)/(\mathcal{R})$ with respect to a
generating set $E=\\{\mu_{i}|i\in I\\}$. Recall (cf.Example 1(d)) that
${\mathbb{F}}(E)$ carries a canonical $C{\mathbb{Z}}^{I}$-filtration. Then it
induces a natural $C{\mathbb{Z}}^{I}$-filtration on ${\mathcal{P}}$ along the
projection ${\mathbb{F}}(E)\twoheadrightarrow{\mathcal{P}}$.

######  Proposition 1.

Let ${\mathcal{P}}$ be a ${\mathbb{K}}$-linear operad. The functor
$Filt(-,{\mathcal{P}}):{\mathtt{LatOper}}^{op}\to{\mathtt{Sets}}$ is
representable. In fact,

$Filt(L,{\mathcal{P}})\simeq{{\rm
Hom}}_{{\mathtt{LatOper}}}(L,Sub({\mathcal{P}}))$

functorially in $L$. Here, ${\mathtt{LatOper}}$ is the category of lattice
operads with lax morphisms and $Sub({\mathcal{P}})$ is the lattice operad of
Example 1(e).

###### Proof.

In one direction, let $F{\mathcal{P}}$ be an $L$-filtration of
${\mathcal{P}}$. Then $p\mapsto F_{p}{\mathcal{P}}$ for all $p\in L$ defines a
lax operad morphism $L\to Sub({\mathcal{P}})$ as follows from the definition
of an $L$-filtration.

Conversely, given a lax operad morphism $f:L\to Sub({\mathcal{P}})$, we get an
$L$-filtration of ${\mathcal{P}}$ by considering the image of the tautological
filtration $\tau{\mathcal{P}}$ under

$f^{*}:Filt(Sub({\mathcal{P}}),{\mathcal{P}})\to Filt(L,{\mathcal{P}}).$

provided by Theorem 1.

One readily verifies that these correspondences are indeed inverse to each
other and natural. ∎

######  Lemma 3.

For any lattice operads $K,L$, the set ${\rm Hom}_{{\mathtt{LatOper}}}(L,K)$
acquires a lattice structure by setting

$(f\wedge g)(p):=f(p)\wedge g(p)$

and

$(f\vee g)(p):=f(p)\vee g(p)$

for all $n\geq 1$, $p\in L(n)$.

###### Proof.

First, we check that $f\wedge g$ is a well-defined lax lattice operad
morphism. To this end, let $m,n\geq 1$, $1\leq i\leq m$, $p\in L(m)$ and $q\in
L(n)$. Then

$\displaystyle(f\wedge g)(p\circ_{i}q)$ $\displaystyle=f(p\circ_{i}q)\wedge
g(p\circ_{i}q)$
$\displaystyle\geq(f(p)\circ_{i}f(q))\wedge(g(p)\circ_{i}g(q))$
$\displaystyle\geq(f(p)\circ_{i}f(q))\wedge(g(p)\circ_{i}g(q))\wedge(f(p)\circ_{i}g(q))\wedge(g(p)\circ_{i}f(q))$
$\displaystyle\geq[(f(p)\wedge g(p))\circ_{i}f(q)]\wedge[(f(p)\wedge
g(p))\circ_{i}g(q)]$ $\displaystyle\geq(f(p)\wedge g(p))\circ_{i}(f(q)\wedge
g(q))=(f\wedge g)(p)\circ_{i}(f\wedge g)(q)$

Here, the first comparison follows from the definition of a lax morphism
applied to $f$ and $g$, the second one is due to the natural order on the
lattice $K(m+n-1)$, the third and the fourth one are an application of the
distributive properties of Lemma 1. Equivariance of $f\wedge g$ is clear.

A similar argument shows that $f\vee g$ is a lax operad morphism as well. The
lattice axioms for $\wedge$ and $\vee$ hold true, since they hold in each
$K(n)$ for $n\geq 1$. ∎

######  Remark 2.

If each component $K(n)$ of a lattice operad $K=\\{K(n)\\}_{n\geq 1}$ is a
complete lattice, then so is ${\rm Hom}_{{\mathtt{LatOper}}}(L,K)$ for any
lattice operad $L$.

######  Corollary 3.

$Filt(L,{\mathcal{P}})$ is a (complete) lattice with the trivial
$L$-filtration $\mathbf{1}{\mathcal{P}}$ as its largest element. Indeed, it
follows from Proposition 1, the above remark and the fact that
$Sub({\mathcal{P}})(n)$ is a complete lattice for each $n\geq 1$.

More explicitly, the lattice structure here corresponds to taking (arity-wise)
intersections and ${\mathbb{K}}$-linear sums of $L$-filtrations of
${\mathcal{P}}$.

##  4\. Filtrations with special properties

Given a lattice operad $L$ and a ${\mathbb{K}}$-linear operad ${\mathcal{P}}$,
we define $PreFilt(L,{\mathcal{P}})$ to be the set of all collections
$F{\mathcal{P}}=\\{F_{p}{\mathcal{P}}\\}_{p\in L}$ of ${\mathbb{K}}$-linear
subspaces $F_{p}{\mathcal{P}}\subset{\mathcal{P}}(n)$ for all $n\geq 1$ and
$p\in L(n)$. For any $F{\mathcal{P}},G{\mathcal{P}}\in
PreFilt(L,{\mathcal{P}})$ we define $(F\cap G){\mathcal{P}}\in
PreFilt(L,{\mathcal{P}})$ by setting

$(F\cap G)_{p}{\mathcal{P}}:=F_{p}{\mathcal{P}}\cap
G_{p}{\mathcal{P}}\subset{\mathcal{P}}(n)$

and define $(F+G){\mathcal{P}}\in PreFilt(L,{\mathcal{P}})$ by setting

$(F+G)_{p}{\mathcal{P}}:=F_{p}{\mathcal{P}}+G_{p}{\mathcal{P}}\subset{\mathcal{P}}(n)$

for all $n\geq 1$ and $p\in L(n)$. One verifies that
$PreFilt(L,{\mathcal{P}})$ is a (complete) lattice with respect to these
operations, and $Filt(L,{\mathcal{P}})$ is its sublattice.

Now, let $\mathcal{C}$ be a subset of $PreFilt(L,{\mathcal{P}})$ such that

$\displaystyle\mathbf{1}{\mathcal{P}}\in\mathcal{C}$ (6) $\displaystyle
F{\mathcal{P}}\in
PreFilt(L,{\mathcal{P}})\Rightarrow\bigcap\limits_{G{\mathcal{P}}\in\mathcal{C}:F{\mathcal{P}}\leq
G{\mathcal{P}}}G{\mathcal{P}}\in\mathcal{C}$

Then, as it is the case for any complete lattice [Eve44], under these
assumptions, $\mathcal{C}$ induces the closure operator
$\gamma_{\mathcal{C}}:PreFilt(L,{\mathcal{P}})\to\mathcal{C}$ on
$PreFilt(L,{\mathcal{P}})$ that satisfies

  1. (1)

$F{\mathcal{P}}\leq\gamma_{\mathcal{C}}(F{\mathcal{P}})$ for any
$F{\mathcal{P}}\in PreFilt(L,{\mathcal{P}})$;

  2. (2)

$\gamma_{\mathcal{C}}(\gamma_{\mathcal{C}}(F{\mathcal{P}}))=\gamma_{\mathcal{C}}(F{\mathcal{P}})$
for any $F{\mathcal{P}}\in PreFilt(L,{\mathcal{P}})$;

  3. (3)

$F{\mathcal{P}}\leq
G{\mathcal{P}}\Rightarrow\gamma_{\mathcal{C}}(F{\mathcal{P}})\leq\gamma_{\mathcal{C}}(G{\mathcal{P}})$
for any $F{\mathcal{P}},G{\mathcal{P}}\in PreFilt(L,{\mathcal{P}})$.

The premise here is that for the given lattice operad $L$ and a
${\mathbb{K}}$-linear operad ${\mathcal{P}}$, the closure operator
$\gamma_{\mathcal{C}}$ produces the smallest $L$-filtration of type
$\mathcal{C}$ out of the inital data provided in the form of a $L$-indexed
collection of subspaces of ${\mathcal{P}}$. This is illustrated below.

######  Example 4.

Throughout the following examples ${\mathcal{P}}$ is a fixed
${\mathbb{K}}$-linear operad.

  1. (a)

Let $L$ be a lattice operad. Then by Corollary 3,
$\mathcal{C}=Filt(L,{\mathcal{P}})$ satisfies the conditions (4) above. The
corresponding closure operator returns for a given collection
$E{\mathcal{P}}\in PreFilt(L,{\mathcal{P}})$ the smallest $L$-filtration
$G_{E}{\mathcal{P}}$ such that $E_{p}{\mathcal{P}}\subset G_{p}{\mathcal{P}}$
for all $n\geq 1$, $p\in L(n)$. In other words, one may think of
$G_{E}{\mathcal{P}}$ as of the $L$-filtration of ${\mathcal{P}}$ generated by
$E$.

As an application, this allows one to introduce a certain analogue of the
standard filtration of an associative algebra with respect to a chosen set of
generators [MRS01]. Namely, let ${\mathcal{P}}$ be an operad with a generating
collection $E=\\{E(n)\\}_{n\geq 1}$. Then, specializing to $L=M\mathbb{Z}$ in
the above construction, we set $E_{p}{\mathcal{P}}(n):=E(n)$ if
$p\geq(1,\dots,1)$ and $E_{p}{\mathcal{P}}(n):=0$ otherwise for all $n\geq 1$.
In the terminology of [BM22], the corresponding closure $E{\mathcal{P}}\mapsto
G_{E}{\mathcal{P}}$ is the _prestandard multifiltration_ of ${\mathcal{P}}$
with respect to $E$.

Similarly, by taking $L=C{\mathbb{Z}}$ and setting
$E_{p}{\mathcal{P}}(n):=E(n)$ if $p\geq 1$ and $E_{p}{\mathcal{P}}(n):=0$
otherwise for all $n\geq 1$, we get a filtration of ${\mathcal{P}}$ by the
total degrees of the partial-composition polynomials in $E$. In fact, the
latter $C{\mathbb{Z}}$-filtration of ${\mathcal{P}}$ is the $\rho^{*}$-image
of the former $M{\mathbb{Z}}$-filtration, cf. Example 2 and Corollary 1.

  2. (b)

Let $L$ be a lattice operad such that each $L(n)$ for $n\geq 1$ is complete.
Then the set

$\mathcal{S}:=\\{G{\mathcal{P}}\in Filt(L,{\mathcal{P}})|G{\mathcal{P}}\hbox{
is saturated}\\}$

satisfies conditions (4) above. We call the corresponding closure operator
$F{\mathcal{P}}\mapsto\overline{F{\mathcal{P}}}$ the _saturation_ of
$F{\mathcal{P}}$.

  3. (c)

Recall that an increasing ${\mathbb{Z}}$-indexed filtration
$\\{F_{i}B\\}_{i\in{\mathbb{Z}}}$ of an associative non-commutative algebra
$B$ is called a $D$-filtration if $F_{i}B=0$ for $i<0$ and
$[F_{i}B,F_{j}B]\subset F_{i+j-1}B$ for all $i,j\geq 0$. Here, the bracket
denotes the ordinary commutator bracket $[a,b]=a\cdot b-b\cdot a$.

An operadic enhancement of the commutator bracket can be introduced as
follows. For ${a\in{\mathcal{P}}(m)}$, $b\in{\mathcal{P}}(n)$, $1\leq i\leq
m$, $1\leq j\leq n$, we set

$\displaystyle[a,b]_{ij}:=(a\circ_{i}b)\cdot(\tau_{i-1,j-1}\times{\mathbbm{1}}_{m+n-i-j+1})-(-1)^{|a||b|}(b\circ_{j}a)\cdot({\mathbbm{1}}_{i+j-1}\times\tau_{m-i,n-j}),$

where $\tau_{i-1,j-1}\times{\mathbbm{1}}_{m+n+i+j+1}\in{\mathbb{S}}_{m+n-1}$
is the permutation that exchanges the first $i-1$ symbols with the subsequent
$j-1$ symbols and leaves the remaining symbols untouched. The action of
${{\mathbbm{1}}_{i+j-1}\times\tau_{m-j,n-i}}$ is defined in a similar way. The
flow diagram shown below illustrates the idea.

Figure 2. The operadic commutator

Next, we define

$\displaystyle[-,-]_{ij}:{M{\mathbb{Z}}}(m)\times{M{\mathbb{Z}}}(n)\to{M{\mathbb{Z}}}(m+n-1),\
1\leq i\leq m,\ 1\leq j\leq n,$

by setting

$[\vec{a},\vec{b}]_{ij}:=(\vec{b}_{L}+a_{i},\vec{a}_{L}+b_{j},a_{i}+b_{j}-1,\vec{b}_{R}+a_{i},\vec{a}_{R}+b_{j}),$

for $\vec{a}=(\vec{a}_{L},a_{i},\vec{a}_{R})\in{M{\mathbb{Z}}}(m)$ and
$\vec{b}=(\vec{b}_{L},b_{j},\vec{b}_{R})\in{M{\mathbb{Z}}}(n)$. Here, an
expression of the form $\vec{p}+q$ for a vector $\vec{p}=(p_{1},\dots,p_{k})$
and a scalar $q$ stands for $(p_{1}+q,\dots,p_{k}+q)$.

Finally, we say that a ${M{\mathbb{Z}}}$-filtration $F{\mathcal{P}}$ of a
${\mathbb{K}}$-linear operad ${\mathcal{P}}$ is a $D$-filtration if

$[F_{\vec{p}}{\mathcal{P}}(m),F_{\vec{q}}{\mathcal{P}}(n)]_{ij}\subseteq
F_{[\vec{p},\vec{q}]_{ij}}{\mathcal{P}}(m+n-1)$

for all $\vec{p}\in{M{\mathbb{Z}}}(m)$, $\vec{q}\in{M{\mathbb{Z}}}(n)$, $1\leq
i\leq m$, $1\leq j\leq n$. This agrees with the associative-algebraic case
above. In the operadic context, the prototypical example of a $D$-filtration
is the ${M{\mathbb{Z}}}$-filtration of the operad of multilinear differential
operators outlined in Example 3(e).

One may verify that for a given operad ${\mathcal{P}}$, the set of all
$D$-filtrations $\mathcal{D}\subset PreFilt({M{\mathbb{Z}}},{\mathcal{P}})$
satisfies the conditions of (4) giving rise to the closure operator
$F{\mathcal{P}}\mapsto(F{\mathcal{P}})^{D}$. In particular, in the terminology
of [BM22], the _standard $D$-filtration_ associated to a generating collection
$E$ of a ${\mathbb{K}}$-linear operad ${\mathcal{P}}$ is obtained as the
composition $\overline{(G_{E}{\mathcal{P}})^{D}}$ of the three closure
operators defined above. The construction can be made explicit in the form of
a certain iterative algorithm as done in op.cit.

  4. (d)

As a non-example, the property of being a stabilized filtration does not arise
from a closure operator. That is, $\mathcal{B}:=\\{G{\mathcal{P}}\in
Filt(L,{\mathcal{P}})|G{\mathcal{P}}\hbox{ is stabilized}\\}$ does not, in
general, satisfy conditions (4).

##  5\. Gradings and associated graded operads

######  Definition 3.

Let $G$ be a set-valued operad and ${\mathcal{P}}$ be a ${\mathbb{K}}$-linear
operad. We say that ${\mathcal{P}}$ is _$G$ -graded_ if

  * (i)

for all $n\geq 1$, we have a decomposition
${\mathcal{P}}(n)=\bigoplus\limits_{p\in G(n)}{\mathcal{P}}(n)_{p}$;

  * (ii)

for any $m,n\geq 1$, $1\leq i\leq m$, $p\in G(m)$ and $q\in G(n)$,

${\mathcal{P}}(m)_{p}\circ_{i}{\mathcal{P}}(n)_{q}\subset{\mathcal{P}}(m+n-1)_{p\circ_{i}q}$

######  Example 5.

  1. (1)

Any $\mathbb{Z}$-graded algebra can be regarded as an operad concentrated in
arity $1$ graded by the operad $C{\mathbb{Z}}$ of Example 1(a), when we forget
about its order structure.

  2. (2)

Let $V=V_{0}\oplus V_{1}$ be a $\mathbb{Z}/2\mathbb{Z}$-graded
${\mathbb{K}}$-vector space. For each $n\geq 1$ and
$(d_{1},\dots,d_{n})\in(\mathbb{Z}/2\mathbb{Z})^{n}$ take
$\mathcal{E}_{V}(n)_{(d_{1},\dots,d_{n})}$ to be the space of all
${\mathbb{K}}$-linear mappings $f:V^{\otimes n}\to V$ such that

$v\mapsto f(u_{1},\dots,u_{i-1},v,u_{i+1},\dots,u_{n})$

is homogeneous of degree $d_{i}$ for all $1\leq i\leq n$ and any choice of
homogeneous elements $u_{j}\in V$. Then
$\mathcal{E}_{V}=\\{\mathcal{E}_{V}(n)\\}_{n\geq 1}$, where
$\mathcal{E}_{V}(n):=\bigoplus\limits_{(d_{1},\dots,d_{n})\in(\mathbb{Z}/2\mathbb{Z})^{n}}\mathcal{E}_{V}(n)_{(d_{1},\dots,d_{n})}$
is a suboperad of the endomorphism operad $\mathcal{E}nd(V)$ graded by the
word operad $\mathbb{W}(\mathbb{Z}/2\mathbb{Z})$.

We say that a lattice operad $L$ is _strictly monotonic_ if $q<q^{\prime}$
implies $p\circ_{i}q<p\circ_{i}q^{\prime}$ and
$q\circ_{j}p<q^{\prime}\circ_{j}p$ for any $m,n\geq 1$, $1\leq i\leq m$,
$1\leq j\leq n$, $p\in L(m)$, $q,q^{\prime}\in L(n)$.

######  Example 6.

Lattice operads $C{\mathbb{Z}}$ and $M\mathbb{Z}$ are strictly monotonic. To
produce an example of a non-strictly monotonic lattice operad, one can modify
$C{\mathbb{Z}}$ by replacing ${\mathbb{Z}}$ with the totally ordered monoid
$\overline{{\mathbb{Z}}}:={\mathbb{Z}}\cup\\{\infty\\}$, where $\infty$ is the
designated largest element and, thus, $a+\infty=\infty$ for all
$a\in\overline{{\mathbb{Z}}}$.

######  Definition 4.

Let $L$ be a strictly monotonic lattice operad and ${\mathcal{P}}$ be a
${\mathbb{K}}$-linear operad with an $L$-filtration $F{\mathcal{P}}$. For all
$n\geq 1$ and $p\in L$, we define

$gr{\mathcal{P}}(n)_{p}:=F_{p}{\mathcal{P}}(n)/\sum\limits_{q\in
L:q<p}F_{q}{\mathcal{P}}(n)$

and $gr{\mathcal{P}}(n):=\bigoplus\limits_{p\in L}{\mathcal{P}}(n)_{p}$

######  Proposition 2.

$gr{\mathcal{P}}=\\{{\mathcal{P}}(n)\\}_{n\geq 1}$ with the
$\circ_{i}$-compositions induced from ${\mathcal{P}}$ is a well-defined
$L$-graded ${\mathbb{K}}$-linear operad. We call it the _associated graded of
${\mathcal{P}}$ with respect to the filtration $F{\mathcal{P}}$_.

###### Proof.

To check that $\circ_{i}$-compositions of ${\mathcal{P}}$ descend properly to
$gr{\mathcal{P}}$, let $\overline{\alpha}\in gr{\mathcal{P}}(m)$,
$\overline{\beta}\in gr{\mathcal{P}}(n)$. By linearity, without loss of
generality, we can assume that $\overline{\alpha}$ and $\overline{\beta}$ have
representatives of the form $\alpha+r_{\alpha}$ and $\beta+r_{\beta}$, where
$\alpha\in F_{p}{\mathcal{P}}(m)$, $r_{\alpha}\in
F_{p^{\prime}}{\mathcal{P}}(m)$ for some $p^{\prime}<p$ and $\beta\in
F_{q}{\mathcal{P}}(n)$, $r_{\beta}\in F_{q^{\prime}}{\mathcal{P}}(m)$ for some
$q^{\prime}<q$. Then verifying that
$\overline{a}\circ_{i}\overline{b}:=\overline{\alpha\circ_{i}\beta}$ is well-
defined amounts to showing that

$\alpha\circ_{i}r_{\beta}+r_{\alpha}\circ_{i}\beta+r_{\alpha}\circ_{i}r_{\beta}\in\sum\limits_{r\in
L:r<p\circ_{i}q}F_{r}{\mathcal{P}}(n).$

This follows from the monotonicity property of an $L$-filtration
$F{\mathcal{P}}$ and strict monotonicity of $L$. Checking associativity is
straightforward. The property of $gr{\mathcal{P}}$ being $L$-graded follows
from the compositional compatibility property of $F{\mathcal{P}}$. ∎

As an immediate simple observation we get the following

######  Lemma 4.

Let $F{\mathcal{P}}$ be a ${M{\mathbb{Z}}}$-filtration of a
${\mathbb{K}}$-linear operad ${\mathcal{P}}$ such that it is a $D$-filtration
in the sense of Example 4(c). Then all operadic commutators $[-,-]_{ij}$ in
$gr{\mathcal{P}}$ vanish.

## Acknowledgements

The author is grateful to Anton Khoroshkin for clarifications concerning the
results of [Kho06, Dot07] and to Martin Markl for helpful discussions and
encouragement. The work is supported by RVO:67985840 of the Institute of
Mathematics of the Czech Academy of Sciences and the Praemium Academiae grant
of M. Markl.

## References

  * [BM22] Denis Bashkirov and Martin Markl  “Calculus of multilinear differential operators, operator $L_{\infty}$-algebras and $IBL_{\infty}$-algebras”  In _J. Geom. Phys._ 173, 2022
  * [Dot07] Vladimir Dotsenko  “An operadic approach to deformation quantization of compatible Poisson brackets. I”  In _J. Gen. Lie Theory Appl._ 1.2, 2007, pp. 107–115
  * [Dot19] Vladimir Dotsenko  “Algebraic structures of F-manifolds via pre-Lie algebras”  In _Annali di Matematica Pura ed Applicata (1923-)_ 198.2 Springer, 2019, pp. 517–527
  * [Dot20] Vladimir Dotsenko  “Word operads and admissible orderings”  In _Appl. Categ. Structures_ 28.4, 2020, pp. 595–600
  * [Eve44] CJ Everett  “Closure operators and Galois theory in lattices”  In _Transactions of the American Mathematical Society_ 55.3 JSTOR, 1944, pp. 514–525
  * [Gir15] Samuele Giraudo  “Combinatorial operads from monoids”  In _J. Algebraic Combin._ 41.2, 2015, pp. 493–538
  * [Kho06] Anton Khoroshkin  “Koszul operads and distributive lattices”  In _Preprint ITEP-TH-24/06_ , 2006
  * [LV12] Jean-Louis Loday and Bruno Vallette  “Algebraic operads” 346, Grundlehren der mathematischen Wissenschaften  Springer, Heidelberg, 2012
  * [MRS01] John C McConnell, James Christopher Robson and Lance W Small  “Noncommutative noetherian rings”  American Mathematical Soc., 2001

## Appendix

In what follows, $\mathcal{N}_{p}$ denotes the suboperad (in ${\mathtt{Lat}}$)
of the nonsymmetric version of ${M{\mathbb{Z}}}$ generated by a single element
$p\in{M{\mathbb{Z}}}(n)$.

|
---|---

Figure 3. $\mathcal{N}_{(1,1)}(3)$ and $\mathcal{N}_{(1,1)}(4)$

|
---|---

Figure 4. $\mathcal{N}_{(-1,1)}(3)$ and $\mathcal{N}_{(-1,1)}(4)$

Figure 5. $\mathcal{N}_{(1,1,1)}(5)$

Let $\mathcal{M}_{(1,1)}$ be the suboperad (in ${\mathtt{Lat}}$) of the
symmetric lattice operad ${M{\mathbb{Z}}}$ generated by
$(1,1)\in{M{\mathbb{Z}}}(2)$.

Figure 6. $\mathcal{M}_{(1,1)}(3)$

A computer-assisted calculation indicates that
$|\mathcal{M}_{(1,1)}{(n)}|=(n-1)^{n}$ for $2\leq n\leq 6$ (OEIS: A065440).