Search

Your search keyword '"Rödl, V."' showing total 241 results
Start Over Author "Rödl, V."
241 results on '"Rödl, V."'

68. Equivalent Conditions for Regularity (Extended Abstract).

Author

Gonnet, Gastón H., Panario, Daniel, Viola, Alfredo, Kohayakawa, Y., Rödl, V., and Skokan, J.

Abstract

Haviland and Thomason and Chung and Graham were the first to investigate systematically some properties of quasi-random hypergraphs. In particular, in a series of articles, Chung and Graham considered several quite disparate properties of random-like hypergraphs of density 1/2 and proved that they are in fact equivalent. The central concept in their work turned out to be the so called deviation of a hypergraph. Chung and Graham proved that having small deviation is equivalent to a variety of other properties that describe quasi-randomness. In this note, we consider the concept of discrepancy for k-uniform hypergraphs with an arbitrary constant density d(0 < d < 1) and prove that the condition of having asymptotically vanishing discrepancy is equivalent to several other quasi-random properties of $\mathcal{H}$, similar to the ones introduced by Chung and Graham. In particular, we give a proof of the fact that having the correct ‘spectrum' of the s-vertex subhypergraphs is equivalent to quasi-randomness for any s ≥ 2k. Our work can be viewed as an extension of the results of Chung and Graham to the case of an arbitrary constant valued density. Our methods, however, are based on different ideas. [ABSTRACT FROM AUTHOR]

Published
2000
Full Text
View/download PDF

69. Algorithmic Aspects of Regularity.

Author

Gonnet, Gastón H., Panario, Daniel, Viola, Alfredo, Kohayakawa, Y., and Rödl, V.

Abstract

Szemerédi's celebrated regularity lemma proved to be a fundamental result in graph theory. Roughly speaking, his lemma states that any graph may be approximated by a union of a bounded number of bipartite graphs, each of which is ‘pseudorandom'. As later proved by Alon, Duke, Lefmann, Rödl, and Yuster, there is a fast deterministic algorithm for finding such an approximation, and therefore many of the existential results based on the regularity lemma could be turned into constructive results. In this survey, we discuss some recent developments concerning the algorithmic aspects of the regularity lemma. [ABSTRACT FROM AUTHOR]

Published
2000
Full Text
View/download PDF

79. AN ALGORITHMIC VERSION OF THE HYPERGRAPH REGULARITY METHOD.

Author

Haxell, P. E., Nagle, B., and Rödl, V.

Subjects
HYPERGRAPHS, GRAPH theory, SET theory, MONADS (Mathematics), HOMOLOGICAL algebra, ALGORITHMS
Abstract

Extending the Szemerédi regularity lemma for graphs, P. Frankl and V. Rödl [Random Structures Algorithms, 20 (2002), pp. 131-164] established a 3-graph regularity lemma triple systems Gn admit bounded partitions of their edge sets, most classes of which consist of regularly distributed triples. Many applications of this lemma require a companion counting lemma [B. Nagle and V. Rödl, Random Structures Algorithms, 23 (2003), pp. 264-332] allowing one to find and enumerate subhypergraphs of a given isomorphism type in a "dense and regular" environment created by the 3-graph regularity lemma. Combined applications of these lemmas are known as the 3-graph regularity method. In this paper, we provide an algorithmic version of the 3-graph regularity lemma which, as we show, is compatible with a counting lemma. We also discuss some applications. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

86. Large triangle-free subgraphs in graphs without K.

Author

Frankl, P. and Rödl, V.

Abstract

It is shown that for arbitrary positive ε there exists a graph without K and so that all its subgraphs containing more than 1/2 + ε portion of its edges contain a triangle (Theorem 2). This solves a problem of Erdös and Nešetřil. On the other hand it is proved that such graphs have necessarily low edge density (Theorem 4). Theorem 3 which is needed for the proof of Theorem 2 is an analog of Goodman's theorem [8], it shows that random graphs behave in some respect as sparse complete graphs. Theorem 5 shows the existence of a graph on less than 10 vertices, without K and which is edge-Ramsey for triangles. [ABSTRACT FROM AUTHOR]

Published
1986
Full Text
View/download PDF

87. On K4-free subgraphs of random graphs.

Author

Kohayakawa, Y., Łuczak, T., and Rödl, V.

Abstract

For 0<γ≤1 and graphs G and H, write G→γ H if any γ-proportion of the edges of G spans at least one copy of H in G. As customary, write K r for the complete graph on r vertices. We show that for every fixed real η>0 there exists a constant C= C(η) such that almost every random graph G n,p with p= p(n)≥ Cn−2/5 satisfies G n,p→2/3+η K4. The proof makes use of a variant of Szemerédi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerning H-free subgraphs of random graphs in the spirit of the Erdős-Stone theorem are discussed. [ABSTRACT FROM AUTHOR]

Published
1997
Full Text
View/download PDF

88. Coloring graphs with locally few colors

Author

Erdös, P, Füredi, Z, Hajnal, A, Komjáth, P, Rödl, V, and Seress, Á

Subjects
Greedy coloring, Vertex (graph theory), Discrete mathematics, Combinatorics, Edge coloring, Discrete Mathematics and Combinatorics, Graph coloring, Complete coloring, Fractional coloring, Theoretical Computer Science, Brooks' theorem, Mathematics, List coloring
Abstract

Let G be a graph, m > r ⩾1 integers. Suppose that it has a good coloring with m colors which uses at most r colors in the neighborhood of every vertex. We investigate these so-called local r -colorings. One of our results (Theorem 2.4) states: The chromatic number of G , Chr( G )⩽ r 2 r log 2 log 2 m (and this value is the best possible in a certain sense). We consider infinite graphs as well.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results