  Markov networks are probabilistic graphical models that employ undirected
graphs to depict conditional independence relationships among variables. Our
focus lies in constraint-based structure learning, which entails learning the
undirected graph from data through the execution of conditional independence
tests. We establish theoretical limits concerning two critical aspects of
constraint-based learning of Markov networks: the number of tests and the sizes
of the conditioning sets. These bounds uncover an exciting interplay between
the structural properties of the graph and the amount of tests required to
learn a Markov network. The starting point of our work is that the graph
parameter maximum pairwise connectivity, $\kappa$, that is, the maximum number
of vertex-disjoint paths connecting a pair of vertices in the graph, is
responsible for the sizes of independence tests required to learn the graph. On
one hand, we show that at least one test with the size of the conditioning set
at least $\kappa$ is always necessary. On the other hand, we prove that any
graph can be learned by performing tests of size at most $\kappa$. This
completely resolves the question of the minimum size of conditioning sets
required to learn the graph. When it comes to the number of tests, our upper
bound on the sizes of conditioning sets implies that every $n$-vertex graph can
be learned by at most $n^{\kappa}$ tests with conditioning sets of sizes at
most $\kappa$. We show that for any upper bound $q$ on the sizes of the
conditioning sets, there exist graphs with $O(n q)$ vertices that require at
least $n^{\Omega(\kappa)}$ tests to learn. This lower bound holds even when the
treewidth and the maximum degree of the graph are at most $\kappa+2$. On the
positive side, we prove that every graph of bounded treewidth can be learned by
a polynomial number of tests with conditioning sets of sizes at most $2\kappa$.
