摘要 :
A number of classical results re ect the fact that if a holomorphic function maps the unit disk into itself, taking the origin into the origin, and if some boundary point b maps to the boundary, then the map is a magnification at ...
展开
A number of classical results re ect the fact that if a holomorphic function maps the unit disk into itself, taking the origin into the origin, and if some boundary point b maps to the boundary, then the map is a magnification at b. We prove a sharp quantitative version of this result which also sharpens a classical result of Loewner. [References: 10]
收起
摘要 :
Szemeredi's regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-...
展开
Szemeredi's regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the regularity method for graphs and has proved useful in graph theory, combinatorial geometry, combinatorial number theory, and theoretical computer science. Here, we report on recent advances in the regularity method for k-uniform hyper-graphs, for arbitrary k ≥ 2. This method, purely combinatorial in nature, gives alternative proofs of density theorems originally due to E. Szemeredi, H. Furstenberg, and Y. Katznelson. Further results in extremal combinato'rics also have been obtained with this approach. The two main components of the regularity method for k-uniform hypergraphs, the regularity lemma and the counting lemma, have been obtained recently: Roedl and Skokan (based on earlier work of Frankl and Roedl) generalized Szemeredi's regularity lemma to k-uniform hypergraphs, and Nagle, Roedl, and Schacht succeeded in proving a counting lemma accompanying the Roedl-Skokan hypergraph regularity lemma. The counting lemma is proved by reducing the counting problem to a simpler one previously investigated by Kohayakawa, Roedl, and Skokan. Similar results were obtained independently by W. T. Gowers, following a different approach.
收起
摘要 :
Szemerédi's regularity lemma proved to be a powerful tool in extremal graph theory. Many of its applications are based on the so-called counting lemma: if G is a k-partite graph with k-partition V1Vk, |V1|==|Vk|=n, where all indu...
展开
Szemerédi's regularity lemma proved to be a powerful tool in extremal graph theory. Many of its applications are based on the so-called counting lemma: if G is a k-partite graph with k-partition V1Vk, |V1|==|Vk|=n, where all induced bipartite graphs G[Vi,Vj] are (d,ε)-regular, then the number of k-cliques Kk in G is . Frankl and R?dl extended Szemerédi's regularity lemma to 3-graphs and Nagle and R?dl established an accompanying 3-graph counting lemma analogous to the graph counting lemma above. In this paper, we provide a new proof of the 3-graph counting lemma.
收起
摘要 :
Green [B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005) 340-376] established a version of the Szemerédi Regularity Lemma for abelian groups and derived the Removal Le...
展开
Green [B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005) 340-376] established a version of the Szemerédi Regularity Lemma for abelian groups and derived the Removal Lemma for abelian groups as its corollary. We provide another proof of his Removal Lemma that allows us to extend its statement to all finite groups. We also discuss possible extensions of the Removal Lemma to systems of equations.
收起
摘要 :
Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and R?dl proved an analogue of Szemerédi's regularity...
展开
Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and R?dl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and R?dl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdos-Stone-Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work.
收起
摘要 :
It is well-known that every weakly convergent sequence in x2802;1 is convergent in the norm topology (Schur's lemma). Phillips' lemma asserts even more strongly that if a sequence (mu n)nEN in x2802;infinity converges pointwise on...
展开
It is well-known that every weakly convergent sequence in x2802;1 is convergent in the norm topology (Schur's lemma). Phillips' lemma asserts even more strongly that if a sequence (mu n)nEN in x2802;infinity converges pointwise on {0, 1}N to 0, then its x2802;1-projection converges in norm to 0. In this note we show how the second category version of Schur's lemma, for which a short proof is included, can be used to replace in Phillips' lemma {0, 1}N by any of its subsets which contains all finite sets and having some kind of interpolation property for finite sets. (c) 2022 Elsevier B.V. All rights reserved.
收起
摘要 :
Moser and Tardos (J. ACM (JACM) 57(2), 11 2010) gave an algorithmic proof of the lopsided Lovasz local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a subset of a collection of...
展开
Moser and Tardos (J. ACM (JACM) 57(2), 11 2010) gave an algorithmic proof of the lopsided Lovasz local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a subset of a collection of independent random variables. For the proof, they define a notion of a lopsided dependency between the events suitable for this framework. In this work, we strengthen this notion, defining a novel directed notion of dependency and prove the LLL for the corresponding graph. We show that this graph can be strictly sparser (thus the sufficient condition for the LLL weaker) compared with graphs that correspond to other extant lopsided versions of dependency. Thus, in a sense, we address the problem "find other simple local conditions for the constraints (in the variable framework) that advantageously translate to some abstract lopsided condition" posed by Szegedy (2013). We also give an example where our notion of dependency graph gives better results than the classical Shearer lemma. Finally, we prove Shearer's lemma for the dependency graph we define. For the proofs, we perform a direct probabilistic analysis that yields an exponentially small upper bound for the probability of the algorithm that searches for the desired assignment to the variables not to return a correct answer within n steps. In contrast, the method of proof that became known as the entropic method, gives an estimate of only the expectation of the number of steps until the algorithm returns a correct answer, unless the probabilities are tinkered with.
收起
摘要 :
Let G be a tripartite graph with N vertices in each vertex class. If each vertex is adjacent to at least (2/3)N vertices in each of the other classes, then either G contains a subgraph that consists of N vertex-disjoint triangles ...
展开
Let G be a tripartite graph with N vertices in each vertex class. If each vertex is adjacent to at least (2/3)N vertices in each of the other classes, then either G contains a subgraph that consists of N vertex-disjoint triangles or G is a specific graph in which each vertex is adjacent to exactly (2/3)N vertices in each of the other classes.
收起
摘要 :
Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox, and Zhao. These inheritance lemmas also imply improved ...
展开
Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox, and Zhao. These inheritance lemmas also imply improved H-counting lemmas for subgraphs of bijumbled graphs, for some H.
收起
摘要 :
We give a self-contained treatment of set-theoretic subsolutions to flow by mean curvature, or, more generally, to flow by mean curvature plus an ambient vector field. The ambient space can be any smooth Riemannian manifold. Most ...
展开
We give a self-contained treatment of set-theoretic subsolutions to flow by mean curvature, or, more generally, to flow by mean curvature plus an ambient vector field. The ambient space can be any smooth Riemannian manifold. Most importantly, we show that if two such set-theoretic subsolutions are initially disjoint, then they remain disjoint provided one of the subsolutions is compact; previously, this was only known for Euclidean space (with no ambient vectorfield). We also give a simple proof of a version of Ilmanen's interpolation theorem.
收起
原文获取