Log in

Relevant bibliographies by topics / Hypergraph regularity lemma / Journal articles

Journal articles on the topic 'Hypergraph regularity lemma'

To see the other types of publications on this topic, follow the link: Hypergraph regularity lemma.

Author: Grafiati

Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 20 journal articles for your research on the topic 'Hypergraph regularity lemma.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

5

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

6

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

Abstract:

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).

APA, Harvard, Vancouver, ISO, and other styles

8

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

Abstract:

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).

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

16

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

18

Sudakov, Benny, and 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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

19

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!