Finite Compactness?
Looking for more in Property Testing
Oded Goldreich is one of the world leaders in theory. He has done seminal work in several areas including randomness in computation and cryptography, and has written very important books.
Today Ken and I wish to define a finite version of the classic notion of compactness.
We both are big fans of Oded’s work and are sorry that neither of us has ever had the chance to work with him. Our loss.
One of the real services Oded and several like-minded people provide is writing surveys:
sur-vey/`sər,vā/
Noun: A general view, examination, or description of someone or something.
Verb: (of a person or their eyes) Look carefully and thoroughly at (someone or something), esp. so as to appraise them.
Surveys collect into one place ideas that can often be lost when distributed among various papers in diverse places. We have written previously about the iceberg effect of foundational results in a paper being obscured by main results that get the top-level attention. Surveys emphasize the progression of ideas building from below, and help us see the whole iceberg. Especially good surveys do this—and those are the only kind Oded writes.
Sometimes even a survey is not enough, and what you need is a book or a blog. Oded has written many books; now we will try the blog’s turn. We wish to draw out some ideas that have been beneath the iceberg’s surface in property testing, and collide them with a concept called compactness in logic that we think has steamboat power in computational complexity. (Maybe that is not a good analogy.)
Finite Compactness – The Idea
The classic notion of compactness in logic states roughly this: suppose some property holds for all finite subsets of an infinite set , then it holds for all of
. This is a powerful notion that is true for first order logic—it is a corollary of the Completeness Theorem of Kurt Gödel. One way to think about this is:
Recently we realized there is a notion that we will call finite compactness. The rough idea is that even for finite objects there can be a kind of compactness. Here is how it will go:
In this post the objects we focus on are graphs. Here is a concrete definition for undirected graphs:
Definition 1 A graph property
is
–compact provided for all graphs
of large enough size
, if all the subgraphs induced by
vertices of
have
, then there are at least
vertices of
that induce a subgraph
having property
. It is finitely compact if it is
-compact for some
and
.
Note that and
are independent of
. We could allow them to depend on
, or alternately consider the stronger condition that for all
there exists
such that
is
-compact; combining these might yield conditions under which
can have
nodes. The notion can be extended to any reasonable family of mathematical objects defined as formal structures on a ground set
.
Are There Finitely Compact Properties?
Here is our prime candidate: Let be the property of being bipartite, i.e., 2-colorable. Is
finitely compact? In particular, is there an absolute constant
such that for all
, the property is
compact?
A yes answer says that if a graph is “partially” 2-colorable, then the graph is close to being 2-colorable. This is the finite version of the notion of compactness.
Property Testing
The idea of finite compactness is related to property testing. Property testing started explicitly with the work of Manuel Blum, Michael Luby, and Ronitt Rubinfeld, and since then there has been a vast literature of what properties can be tested and which cannot.
The general setup is this: One is presented with a graph and some property
. The usual goal is to determine whether
has the property
or not. This can be easy for some properties and hard for others. But we make the problem much harder: we only allow a small number of probes of
—we cannot examine the entire graph. Clearly, for almost any property it is impossible to test the property without at least looking at all of the graph.
One of the great insights in lower bound theory is that usually an algorithm must at least look at all of the input. But that is wrong, if one relaxes the notion of correctness. The magic of property testing is that if we relax the goal we can often solve the a computational problem in much less time than the size of the input. Indeed it is often possible to make the algorithm run in time independent of the size of the input. The relaxation requires only that the randomized algorithm works as follows:
- If
has the property
, then after the probing the algorithm
says `yes’ with probability at least
. In the one-sided model, the algorithm always says `yes’ in this case.
- If the graph does not have
, and is not “near” a graph in
, then
returns a `no’ with probability at least
.
Here “near” is defined via a parameter that is also given to the algorithm. Two graphs
are
-close if they have the same size
and for all but
pairs
,
. The query complexity
of the tester is the maximum number of edge probes, and is always a function of
. Sometimes it is a function of
, or in case of an exponential-sized graph with
, a function of
usually bounded by
.
For more on property testing, check out Dana Ron’s surveys here or (longer) here, and Oded’s here. These are great surveys.
Cognizance and Compactness?
Our intent is that the hypothesis of -compactness leads the tester
to accept
, which implies that
is
-close to a graph
with property
, and then use the existence of
to produce
. There are two obstacles:
- The tester
need not work by probing small subgraphs for the property
itself.
- The closeness condition counts edges, and might not carry over to vertex-induced subgraphs.
We address the former issue by strengthening a notion called “canonical” in Oded’s survey. This is referenced to a paper by him with Luca Trevisan, but the key point for us is credited to a private communication from Noga Alon and brought to fruition in “Appendix D” of that paper. We will give it a fresh name, hope the authors don’t mind:
Definition 2 A property testing algorithm
for
is cognizant if it generates one or more vertex-induced subgraphs
of
, probing only the edges in
, and accepts if and only if the majority of the probed graphs have property
.
A property is closed under induced subgraphs if whenever
has
and
is a vertex-induced subgraph of
, then
has
. Bipartiteness is such a property; indeed it is closed under edge-induced subgraphs as well. So is
-colorability for any
. Ignoring some slippage in bounds, the gist of Appendix D is:
Theorem 3 Every testable property that is closed under induced subgraphs has a cognizant tester.
This yields a weak “edge-induced” notion of finite compactness. An -vertex graph is dense if it has
edges, where we intend
and fixed. For the property of bipartiteness the weaker version of compactness is achieved this way:
Theorem 4 There is an absolute constant
such that for all dense graphs
and sufficiently large
, if all
-node subgraphs of
are bipartite, then by deleting at most
edges we can obtain a bipartite graph
.
Proof: Given , the cognizant tester in Oded’s survey (Algorithm 2.3) selects
vertices uniformly at random, and accepts iff the subgraph
they induce is bipartite. This makes
. Suppose
is a graph for which all
-node subgraphs are bipartite. Then the tester accepts with certainty. By definition of being a tester,
is near a graph
in
, which here entails that
edges can be deleted from
to yield
. (In fact, as observed in a comment after the proof, a suitable
can be described succinctly in terms of choices that accompany
.)
Can We Get Vertex-Induced Subgraphs?
The issue, however, is that need not be a vertex-induced subgraph. Indeed,
edges can easily be incident on all
vertices, in such a way that all
-vertex induced subgraphs
have many of the bad edges from
.
Note, however, that our condition of compactness is stronger than what one needs for a tester
to accept, even given that
is a cognizant tester. The question is whether the stronger condition sufficies for the desired stronger conclusion.
Is every subgraph-closed testable property finitely compact?
We’ve thought about this in the particular case of bipartiteness. Here is a general kind of attempt to break the desired conclusion.
Bipartite Case
Let be a multiple of 4, and let two copies of
give rise to partitions
and
. For some function
, say
, connect every
-vertex to its
-neighbors and vice-versa. That is, each crossing edge goes just a short
distance `up’ or `down.’ Call this bipartite graph
. (We will also consider adding a few more “rogue” crossing edges.)
Now add “violating edges” to each partition, connecting
to
(mod
) for each
, and similarly for each
. We added
edges total. This gives the graph
.
is near
, because
when
). Moreover, we claim that every
-subset
for
up to about
, the graph induced by
is bipartite. The reason is that if not, then
has a violating edge, say between nodes in
. In order to use that violating edge, there has to be a path within
that connects those endpoints. However, the endpoints are
apart, and a path within
that gets
apart has to have non-constant many steps. The violating edges in
don’t help shorten this path because they too all jump
places forward or backward around the graph.
Thus satisfies the
-compactness hypothesis. No problem with the bipartite tester: it accepts and
is near a bipartite graph, so fine. The question is whether
—or some further modification of
—has large vertex subsets
that induce a bipartite graph.
For itself the answer is yes, but in a fairly narrow manner. By
,
has to contain at least half of the violating edges (i.e. at least
of those
edges). To make
bipartite, we seem forced to do something like this: Make the violating edges be consecutive, say by taking vertices
and
on both sides. Then the point is that between
and
we have no vertices so we have killed all the paths within
that could have gone from the left block to the right block. So
is bipartite. But if
also has a few “rogue” crossing edges that jump further up or down than
, then they could destroy any
being bipartite without making a tiny size-
non-bipartite subgraph.
We don’t know whether this extends to a counterexample to our hypothesis that bipartite graphs are finitely compact. Maybe the answer is around the corner, and we could find it, but … both of us have impending deliveries of somewhat different kinds …
Finitely Compact Time?
The moral that goes with this tale is that proving new results with the deadline pressures of getting out the next post are not very compatible. Not even close. One idea was to not make this into a post at all—keep it secret from everyone. After all it is a failure. Another idea is to stop here and keep thinking about finite compactness.
After long discussion and thinking the GLL staff, Ken and I, decided to post this and even explain in more details more about our ideas. Just be aware that this is new stuff, not well debugged—it could be silly, or could be neat. We do not know yet.
Open Problems
What properties are finitely compact? Are there any interesting ones? And what properties are not?
Does the notion of finite compactness sharpen some of the issues in efficient property testing? What extra impact might the logical form of sentences defining the property have?
Hi Dick,
If I understand your definition correctly, bipartiteness is not finitely compact. Take a constant-degree highly expanding graph of logarithmic girth. Then every vertex-induced subset of, say, N/2 vertices is not bipartite, because if you assume, toward a contradiction, that it were bipartite then you would have an independent set of size at least N/4 in the graph, which is incompatible with the expander mixing lemma. On the other hand, because of the high girth, every constant-size subset of vertices induces a tree, which is bipartite.
Thanks! That’s a nice example of expert knowledge completing what one’s vague intuition was trying to do—I wrote the “Bipartite Case” section.
Well, we did write the post in a way we could joke about our ship being sunk and what kind of salvage operation can be done… Perhaps the notion can still be put into reasonable effect by letting k vary as (log N)^2, say?
Before you gave your definition for finite compactness, I initially thought you might be referring to Helly-type theorems, which strike me as a more direct analogy with the infinite case. (i.e. there is no epsilon involved)