Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 16 of 16 for “"Regularity lemma"”.

  1. TOWARDS A REGULARITY LEMMA FOR HIGHER ARITY DISTAL STRUCTURES

    … nature. In the 1970s, Szemerédi proved his noted Regularity Lemma for graphs. Since then, much work has been devoted to proving stronger analogues of this result for restricted classes of graphs. We prove results in the direction of a regularity lemma for higher arity distal structures. Our main …

    maryland Repository record for TOWARDS A REGULARITY LEMMA FOR HIGHER ARITY DISTAL STRUCTURES (opens in a new tab)

  2. 2-Unstable Configurations

    … we can obtain a stronger result in the Szemerédi regularity lemma if we restrict our attention to graphs which are sufficiently stable. Other model theoretic tameness notions have been shown to give similar strengthenings of the regularity lemma. Each of these tameness notions are fundamentally …

    penn Repository record for 2-Unstable Configurations (opens in a new tab)

  3. Utilization of Partitions in Graph Structures

    … problems and conjectures which require the Regularity lemma require unique methods to improve the bounds on known results. In this work the upper bounds for Gallai-Ramsey using $k$ colors is lowered to at most $k(n-1) +3n$ for even cycles and $(2^{k+3}-3)n \log n$ for odd cycles. Also, with …

    gsu Repository record for Utilization of Partitions in Graph Structures (opens in a new tab)

  4. Distality to and from combinatorics

    … satisfying an improved version of Szemerédi regularity lemma, a classical theorem in extremal combinatorics. Thus, motivated by distality, we discover an interaction between two areas of extremal combinatorics. Chapter 5 demonstrates both the to and the from directions. We show that the …

    whiterose Download PDF for Distality to and from combinatorics (opens in a new tab)

  5. A Hypergraph Regularity Method for Linear Hypergraphs

    Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and …

    usf Repository record for A Hypergraph Regularity Method for Linear Hypergraphs (opens in a new tab)

  6. Precise Partitions Of Large Graphs

    First by using an easy application of the Regularity Lemma, we extend some known results about cycles of many lengths to include a specified edge on the cycles. The results in this chapter will help us in rest of this thesis. In 2000, Enomoto and Ota posed a conjecture on the existence of path …

    gsu Repository record for Precise Partitions Of Large Graphs (opens in a new tab)

  7. An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs

    Szemere´di’s Regularity Lemma [32, 33] is an important tool in combinatorics, with numerous appli- cations in combinatorial number theory, discrete geometry, extremal graph theory, and theoretical computer science. The Regularity Lemma hinges on the following concepts. Let G = (V, E) be a graph and …

    usf Repository record for An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs (opens in a new tab)

  8. Turing machine algorithms and studies in quasi-randomness

    … and a lower bound for two different kinds of regularity lemmas. Our algorithm for FK-regularity is derived using a spectral characterization of quasi-randomness. We also use a similar spectral connection to also answer an open question about quasi-random tournaments. We then provide a "Wowzer" …

    gatech Repository record for Turing machine algorithms and studies in quasi-randomness (opens in a new tab)

  9. Improved Robustness and Versatility of Lattice-Based Cryptography

    … towards a ring analogue of the Leftover Hash Lemma (LHL). The LHL is a mathematical tool often used in the analysis of various lattice-based cryptosystems, as well as their leakage-resilient counterparts. However, it does not hold in the ring setting, which is typical for efficient …

    maryland Repository record for Improved Robustness and Versatility of Lattice-Based Cryptography (opens in a new tab)

  10. Embedding Problems for Graphs and Hypergraphs

    … and one for hypergraphs. I will also discuss the regularity lemma for graphs and hypergraphs, an important tool which underpins these and many similar embedding results. Finally, I will also discuss graph and hypergraph Ramsey numbers, since two of the embedding results have important applications …

    birmingham Download PDF for Embedding Problems for Graphs and Hypergraphs (opens in a new tab)

  11. Topics in and around higher-order Fourier analysis

    … as [2].</p> <p>Green and Tao’s arithmetic regularity lemma and counting lemma together apply to systems of linear forms which satisfy a particular algebraic criterion known as the ‘flag condition’. In Chapter 4 we give an arithmetic regularity lemma and counting lemma which applies to all …

    oxford Repository record for Topics in and around higher-order Fourier analysis (opens in a new tab)

  12. On Some Hypergraph Coloring Algorithms

    Of a given bipartite graph G = (V, E), it is elementary to construct a bipartition in timeO(|V |+|E|). For a given k-graph H = H(k) with k ≥ 3 fixed, Lovász proved that deciding whether H is bipartite is NP-complete. In this thesis, we consider the average running time of this problem. For that, …

    usf Repository record for On Some Hypergraph Coloring Algorithms (opens in a new tab)

  13. On learning, fairness, and complexity

    … connected to complexity theory through the Regularity Lemma and its various implications [CDV24].<br><br>We provide a thorough study of the connections between multigroup fairness notions, the central learning primitive of weak agnostic learning, and the fundamental Hardcore Lemma in …

    oxford Repository record for On learning, fairness, and complexity (opens in a new tab)

  14. The Removal Property for Linear Configurations in Compact Abelian Groups

    The combinatorial removal lemma states that, if a (hyper)graph K has not many copies of the fixed (hyper)graph H , then K can be made free of copies of H by removing a small set of (hyper)edges from K. In this thesis we show results for homomorphisms in finite abelian groups, and for integer linear …

    toronto-retro Repository record for The Removal Property for Linear Configurations in Compact Abelian Groups (opens in a new tab)

  15. Extremal problems on special graph colorings

    Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms

    uiuc Repository record for Extremal problems on special graph colorings (opens in a new tab)