The authors and Fischer recently proved that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing the following (ordered) matrix removal lemma: For any finite alphabet @math , any hereditary property @math of matrices over @math , and any @math , there exists @math such that for any matrix @math over @math that is @math -far from satisfying @math , most of the @math submatrices of @math do not satisfy @math . Here being @math -far from @math means that one needs to modify at least an @math -fraction of the entries of @math to make it satisfy @math . However, in the above general removal lemma, @math grows very fast as a function of @math , even when @math is characterized by a single forbidden submatrix. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: For any fixed @math binary matrix @math and any @math there exists @math polynomial in @math , such that for any binary matrix @math in which less than a @math -fraction of the @math submatrices are equal to @math , there exists a set of less than an @math -fraction of the entries of @math that intersects every @math -copy in @math . We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas.
The induced graph removal lemma was later extended to infinite families @cite_5 , stating the following. For any finite or infinite family @math of graphs and any @math there exists @math with the following property. If an @math -vertex graph @math is @math -far from @math -freeness, then with probability at least @math , a random induced subgraph of @math on @math vertices contains a graph from @math . Note that when @math is finite, the statement of the infinite induced removal lemma is indeed equivalent to that of the finite version of the induced removal lemma.
@cite_5
2611059716 2949304946 2963708029 1960457407
We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of @math -dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS'05, SICOMP'08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix properties. The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that for any finite or infinite family @math of forbidden vertex-ordered graphs, and any @math , there exist @math and @math so that any vertex-ordered graph which is @math -far from being @math -free contains at least @math copies of some @math (with the correct vertex order) where @math . The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for @math -partite graphs with "undesirable" edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph. Given a discrete random walk on a finite graph @math , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step @math . These sets induce subgraphs of the underlying graph. Let @math be the subgraph of @math induced by the vacant set of the walk at step @math . Similarly, let @math be the subgraph of @math induced by the edges of the vacant net. For random @math -regular graphs @math , it was previously established that for a simple random walk, the graph @math of the vacant set undergoes a phase transition in the sense of the phase transition on Erd os -Renyi graphs @math . Thus, for @math there is an explicit value @math of the walk, such that for @math , @math has a unique giant component, plus components of size @math , whereas for @math all the components of @math are of size @math . We establish the threshold value @math for a phase transition in the graph @math of the vacant net of a simple random walk on a random @math -regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a non-backtracking random walk, and, for @math even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random @math -regular graphs. The main findings are the following: As @math increases the threshold for the vacant set converges to @math in all three walks. For the vacant net, the threshold converges to @math for both the simple random walk and non-backtracking random walk. When @math is even, the threshold for the vacant net of the unvisited edge process converges to @math , which is also the vertex cover time of the process. The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r > 1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r > 1, the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an n-vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly n − 1 2 (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. For instance, the larger the maximum independent set of the pattern graph is the more efficient algorithms are known. The situation seems to be substantially different in the case of induced subgraph isomorphism for pattern graphs of fixed size. We present two results which provide evidence that no topology of an induced subgraph of fixed size can be easier to detect or count than an independent set of related size. We show that: Any fixed pattern graph that has a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on k vertices is not easier to detect than an independent set on ⌈k 2 ⌉ vertices, and that an induced even cycle on k vertices is not easier to detect than an independent set on k 2 vertices. In view of linear time upper bounds on induced paths of length three and four, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and induced complete split graphs. For an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Finally, we show that the so called diamond, paw and C 4 are not easier to detect as induced subgraphs than an independent set on three vertices.