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:

1. 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.
2. 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?

Advertisements