Acceder

Bibliografías temáticas / Hypergraph regularity lemma / Artículos de revistas

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Hypergraph regularity lemma.

Artículos de revistas sobre el tema "Hypergraph regularity lemma"

Autor: Grafiati

Publicado: 25 de mayo de 2024

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 20 mejores artículos de revistas para su investigación sobre el tema "Hypergraph regularity lemma".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

1

Nagle, Brendan, Vojtěch Rödl y Mathias Schacht. "An algorithmic hypergraph regularity lemma". Random Structures & Algorithms 52, n.º 2 (7 de diciembre de 2017): 301–53. http://dx.doi.org/10.1002/rsa.20739.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

CUTLER, JONATHAN y A. J. RADCLIFFE. "Hypergraph Independent Sets". Combinatorics, Probability and Computing 22, n.º 1 (11 de octubre de 2012): 9–20. http://dx.doi.org/10.1017/s0963548312000454.

Texto completo

Resumen

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices isj-independentif its intersection with any edge has size strictly less thanj. The Kruskal–Katona theorem implies that in anr-uniform hypergraph with a fixed size and order, the hypergraph with the mostr-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number ofj-independent sets in anr-uniform hypergraph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

HAXELL, P. E., T. ŁUCZAK, Y. PENG, V. RÖDL, A. RUCIŃSKI y J. SKOKAN. "The Ramsey Number for 3-Uniform Tight Hypergraph Cycles". Combinatorics, Probability and Computing 18, n.º 1-2 (marzo de 2009): 165–203. http://dx.doi.org/10.1017/s096354830800967x.

Texto completo

Resumen

LetC(3)ndenote the 3-uniformtight cycle, that is, the hypergraph with verticesv1, .–.–.,vnand edgesv1v2v3,v2v3v4, .–.–.,vn−1vnv1,vnv1v2. We prove that the smallest integerN=N(n) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph withNvertices contains a monochromatic copy ofC(3)nis asymptotically equal to 4n/3 ifnis divisible by 3, and 2notherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

Lyall, Neil y Ákos Magyar. "Weak hypergraph regularity and applications to geometric Ramsey theory". Transactions of the American Mathematical Society, Series B 9, n.º 5 (17 de marzo de 2022): 160–207. http://dx.doi.org/10.1090/btran/61.

Texto completo

Resumen

Let Δ = Δ 1 × … × Δ d ⊆ R n \Delta =\Delta _1\times \ldots \times \Delta _d\subseteq \mathbb {R}^n , where R n = R n 1 × ⋯ × R n d \mathbb {R}^n=\mathbb {R}^{n_1}\times \cdots \times \mathbb {R}^{n_d} with each Δ i ⊆ R n i \Delta _i\subseteq \mathbb {R}^{n_i} a non-degenerate simplex of n i n_i points. We prove that any set S ⊆ R n S\subseteq \mathbb {R}^n , with n = n 1 + ⋯ + n d n=n_1+\cdots +n_d of positive upper Banach density necessarily contains an isometric copy of all sufficiently large dilates of the configuration Δ \Delta . In particular any such set S ⊆ R 2 d S\subseteq \mathbb {R}^{2d} contains a d d -dimensional cube of side length λ \lambda , for all λ ≥ λ 0 ( S ) \lambda \geq \lambda _0(S) . We also prove analogous results with the underlying space being the integer lattice. The proof is based on a weak hypergraph regularity lemma and an associated counting lemma developed in the context of Euclidean spaces and the integer lattice.

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

KRIVELEVICH, MICHAEL, MATTHEW KWAN y BENNY SUDAKOV. "Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs". Combinatorics, Probability and Computing 25, n.º 6 (14 de marzo de 2016): 909–27. http://dx.doi.org/10.1017/s0963548316000079.

Texto completo

Resumen

We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a densek-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

RÖDL, VOJTĚCH y MATHIAS SCHACHT. "Regular Partitions of Hypergraphs: Regularity Lemmas". Combinatorics, Probability and Computing 16, n.º 6 (noviembre de 2007): 833–85. http://dx.doi.org/10.1017/s0963548307008553.

Texto completo

Resumen

Szemerédi's regularity lemma for graphs has proved to be a powerful tool with many subsequent applications. The objective of this paper is to extend the techniques developed by Nagle, Skokan, and the authors and obtain a stronger and more ‘user-friendly’ regularity lemma for hypergraphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

RÖDL, VOJTĚCH y MATHIAS SCHACHT. "Regular Partitions of Hypergraphs: Counting Lemmas". Combinatorics, Probability and Computing 16, n.º 6 (noviembre de 2007): 887–901. http://dx.doi.org/10.1017/s0963548307008565.

Texto completo

Resumen

We continue the study of regular partitions of hypergraphs. In particular, we obtain corresponding counting lemmas for the regularity lemmas for hypergraphs from our paper ‘Regular Partitions of Hypergraphs: Regularity Lemmas’ (in this issue).

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

Czygrinow, Andrzej y Vojtech Rödl. "An Algorithmic Regularity Lemma for Hypergraphs". SIAM Journal on Computing 30, n.º 4 (enero de 2000): 1041–66. http://dx.doi.org/10.1137/s0097539799351729.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

Rödl, Vojtěch y Jozef Skokan. "Regularity Lemma for k-uniform hypergraphs". Random Structures & Algorithms 25, n.º 1 (9 de junio de 2004): 1–42. http://dx.doi.org/10.1002/rsa.20017.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

Rödl, Vojtěch y Jozef Skokan. "Applications of the regularity lemma for uniform hypergraphs". Random Structures and Algorithms 28, n.º 2 (2006): 180–94. http://dx.doi.org/10.1002/rsa.20108.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Chung, Fan R. K. "Regularity lemmas for hypergraphs and quasi-randomness". Random Structures & Algorithms 2, n.º 2 (junio de 1991): 241–52. http://dx.doi.org/10.1002/rsa.3240020208.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

GYÁRFÁS, ANDRÁS y GÁBOR N. SÁRKÖZY. "The 3-Colour Ramsey Number of a 3-Uniform Berge Cycle". Combinatorics, Probability and Computing 20, n.º 1 (2 de julio de 2010): 53–71. http://dx.doi.org/10.1017/s0963548310000209.

Texto completo

Resumen

The asymptotics of 2-colour Ramsey numbers of loose and tight cycles in 3-uniform hypergraphs were recently determined [16, 17]. We address the same problem for Berge cycles and for 3 colours. Our main result is that the 3-colour Ramsey number of a 3-uniform Berge cycle of length n is asymptotic to $\frac{5n}{4}$. The result is proved with the Regularity Lemma via the existence of a monochromatic connected matching covering asymptotically 4n/5 vertices in the multicoloured 2-shadow graph induced by the colouring of Kn(3).

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

Fox, Jacob, János Pach y Andrew Suk. "A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing". SIAM Journal on Computing 45, n.º 6 (enero de 2016): 2199–223. http://dx.doi.org/10.1137/15m1007355.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

TAO, TERENCE. "Norm convergence of multiple ergodic averages for commuting transformations". Ergodic Theory and Dynamical Systems 28, n.º 2 (abril de 2008): 657–88. http://dx.doi.org/10.1017/s0143385708000011.

Texto completo

Resumen

AbstractLet T1,…,Tl:X→X be commuting measure-preserving transformations on a probability space $(X, \mathcal {X}, \mu )$. We show that the multiple ergodic averages $\bfrac {1}{N} \sum _{n=0}^{N-1} f_1(T_1^n x) \cdots f_l(T_l^n x)$ are convergent in $L^2(X,\mathcal {X},\mu )$ as $N \to \infty $ for all $f_1,\ldots ,f_l \in L^\infty (X,\mathcal {X},\mu )$; this was previously established for l=2 by Conze and Lesigne [J. P. Conze and E. Lesigne. Théorèmes ergodique por les mesures diagonales. Bull. Soc. Math. France112 (1984), 143–175] and for general l assuming some additional ergodicity hypotheses on the maps Ti and TiTj−1 by Frantzikinakis and Kra [N. Frantzikinakis and B. Kra. Convergence of multiple ergodic averages for some commuting transformations. Ergod. Th. & Dynam. Sys.25 (2005), 799–809] (with the l=3 case of this result established earlier by Zhang [Q. Zhang. On the convergence of the averages $\bfrac {1}{N} \sum _{n=1}^N f_1(R^n x) f_2(S^n x) f_3(T^n x)$. Mh. Math.122 (1996), 275–300]). Our approach is combinatorial and finitary in nature, inspired by recent developments regarding the hypergraph regularity and removal lemmas, although we will not need the full strength of those lemmas. In particular, the l=2 case of our arguments is a finitary analogue of those by Conze and Lesigne.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

FOX, JACOB y BENNY SUDAKOV. "Decompositions into Subgraphs of Small Diameter". Combinatorics, Probability and Computing 19, n.º 5-6 (9 de junio de 2010): 753–74. http://dx.doi.org/10.1017/s0963548310000040.

Texto completo

Resumen

We investigate decompositions of a graph into a small number of low-diameter subgraphs. Let P(n, ε, d) be the smallest k such that every graph G = (V, E) on n vertices has an edge partition E = E0 ∪ E1 ∪ ⋅⋅⋅ ∪ Ek such that |E0| ≤ εn2, and for all 1 ≤ i ≤ k the diameter of the subgraph spanned by Ei is at most d. Using Szemerédi's regularity lemma, Polcyn and Ruciński showed that P(n, ε, 4) is bounded above by a constant depending only on ε. This shows that every dense graph can be partitioned into a small number of ‘small worlds’ provided that a few edges can be ignored. Improving on their result, we determine P(n, ε, d) within an absolute constant factor, showing that P(n, ε, 2) = Θ(n) is unbounded for ε < 1/4, P(n, ε, 3) = Θ(1/ε2) for ε > n−1/2 and P(n, ε, 4) = Θ(1/ε) for ε > n−1. We also prove that if G has large minimum degree, all the edges of G can be covered by a small number of low-diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, Rödl, Ruciński and Szemerédi.

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

Han, Jie. "On Perfect Matchings in k-Complexes". International Mathematics Research Notices, 11 de enero de 2020. http://dx.doi.org/10.1093/imrn/rnz343.

Texto completo

Resumen

Abstract Keevash and Mycroft [ 19] developed a geometric theory for hypergraph matchings and characterized the dense simplicial complexes that contain a perfect matching. Their proof uses the hypergraph regularity method and the hypergraph blow-up lemma recently developed by Keevash. In this note we give a new proof of their results, which avoids these complex tools. In particular, our proof uses the lattice-based absorbing method developed by the author and a recent probabilistic argument of Kohayakawa, Person, and the author.

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

Tao, Terence. "A Quantitative Ergodic Theory Proof of Szemerédi's Theorem". Electronic Journal of Combinatorics 13, n.º 1 (6 de noviembre de 2006). http://dx.doi.org/10.37236/1125.

Texto completo

Resumen

A famous theorem of Szemerédi asserts that given any density $0 < \delta \leq 1$ and any integer $k \geq 3$, any set of integers with density $\delta$ will contain infinitely many proper arithmetic progressions of length $k$. For general $k$ there are essentially four known proofs of this fact; Szemerédi's original combinatorial proof using the Szemerédi regularity lemma and van der Waerden's theorem, Furstenberg's proof using ergodic theory, Gowers' proof using Fourier analysis and the inverse theory of additive combinatorics, and the more recent proofs of Gowers and Rödl-Skokan using a hypergraph regularity lemma. Of these four, the ergodic theory proof is arguably the shortest, but also the least elementary, requiring passage (via the Furstenberg correspondence principle) to an infinitary measure preserving system, and then decomposing a general ergodic system relative to a tower of compact extensions. Here we present a quantitative, self-contained version of this ergodic theory proof, and which is "elementary" in the sense that it does not require the axiom of choice, the use of infinite sets or measures, or the use of the Fourier transform or inverse theorems from additive combinatorics. It also gives explicit (but extremely poor) quantitative bounds.

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

Sudakov, Benny y István Tomon. "Ramsey properties of algebraic graphs and hypergraphs". Forum of Mathematics, Sigma 10 (2022). http://dx.doi.org/10.1017/fms.2022.85.

Texto completo

Resumen

Abstract One of the central questions in Ramsey theory asks how small the largest clique and independent set in a graph on N vertices can be. By the celebrated result of Erdős from 1947, a random graph on N vertices with edge probability $1/2$ contains no clique or independent set larger than $2\log _2 N$ , with high probability. Finding explicit constructions of graphs with similar Ramsey-type properties is a famous open problem. A natural approach is to construct such graphs using algebraic tools. Say that an r-uniform hypergraph $\mathcal {H}$ is algebraic of complexity $(n,d,m)$ if the vertices of $\mathcal {H}$ are elements of $\mathbb {F}^{n}$ for some field $\mathbb {F}$ , and there exist m polynomials $f_1,\dots ,f_m:(\mathbb {F}^{n})^{r}\rightarrow \mathbb {F}$ of degree at most d such that the edges of $\mathcal {H}$ are determined by the zero-patterns of $f_1,\dots ,f_m$ . The aim of this paper is to show that if an algebraic graph (or hypergraph) of complexity $(n,d,m)$ has good Ramsey properties, then at least one of the parameters $n,d,m$ must be large. In 2001, Rónyai, Babai and Ganapathy considered the bipartite variant of the Ramsey problem and proved that if G is an algebraic graph of complexity $(n,d,m)$ on N vertices, then either G or its complement contains a complete balanced bipartite graph of size $\Omega _{n,d,m}(N^{1/(n+1)})$ . We extend this result by showing that such G contains either a clique or an independent set of size $N^{\Omega (1/ndm)}$ and prove similar results for algebraic hypergraphs of constant complexity. We also obtain a polynomial regularity lemma for r-uniform algebraic hypergraphs that are defined by a single polynomial that might be of independent interest. Our proofs combine algebraic, geometric and combinatorial tools.

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

Chernikov, Artem y Sergei Starchenko. "Definable Regularity Lemmas for NIP Hypergraphs". Quarterly Journal of Mathematics, 12 de marzo de 2021. http://dx.doi.org/10.1093/qmath/haab011.

Texto completo

Resumen

Abstract We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and Lov\'asz-Szegedy for graphs of bounded VC-dimension. We also consider the two extremal cases of regularity for stable and distal hypergraphs, improving and generalizing the corresponding results for graphs in the literature. Finally, we consider a related question of the existence of large (approximately) homogeneous definable subsets of NIP hypergraphs and provide some positive results and counterexamples, in particular for graphs definable in the p-adics.

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

Dodos, Pandelis, Vassilis Kanellopoulos y Thodoris Karageorgos. "Szemerédi's Regularity Lemma via Martingales". Electronic Journal of Combinatorics 23, n.º 3 (22 de julio de 2016). http://dx.doi.org/10.37236/5585.

Texto completo

Resumen

We prove a variant of the abstract probabilistic version of Szemerédi's regularity lemma, due to Tao, which applies to a number of structures (including graphs, hypergraphs, hypercubes, graphons, and many more) and works for random variables in $L_p$ for any $p>1$. Our approach is based on martingale difference sequences.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!