Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

The hypergraph regularity method and its applications.

V Rödl1, B Nagle, J Skokan

  • 1Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA.

Proceedings of the National Academy of Sciences of the United States of America
|May 28, 2005
PubMed
Summary

The regularity method, using Szemeredi's regularity lemma and counting lemma, now extends to k-uniform hypergraphs. This advances combinatorial mathematics and theoretical computer science with new proofs and extremal results.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Periodontal pathogens affect the level of protease inhibitors in gingival crevicular fluid.

Molecular oral microbiology·2012
Same author

Malignant rhabdoid tumours of the jejunum, chest wall and adrenal glands.

Histopathology·2007
Same author

Remission of severely impaired subjective wellbeing in 727 patients with schizophrenia treated with amisulpride.

Acta psychiatrica Scandinavica·2007
Same author

Comparison of olanzapine and risperidone in 367 first-episode patients with non-affective or affective psychosis: results of an open retrospective medical record study.

Pharmacopsychiatry·2005
Same author

[The initial dysphoric reaction (IDR) to the first dose of neuroleptics].

Der Nervenarzt·2004
Same author

Pharmacotherapy: strategies to control drug costs in managed care.

Geriatrics·1998

Area of Science:

  • Combinatorics
  • Graph Theory
  • Theoretical Computer Science

Background:

  • Szemeredi's regularity lemma decomposes graphs into random-like subgraphs.
  • This enables subgraph enumeration via the counting lemma for graphs.
  • The regularity method combines these for applications in various mathematical fields.

Purpose of the Study:

  • To report recent advances in the regularity method for k-uniform hypergraphs (k >= 2).
  • To provide alternative combinatorial proofs for density theorems.
  • To explore new results in extremal combinatorics using this approach.

Main Methods:

  • Generalization of Szemeredi's regularity lemma to k-uniform hypergraphs by Rodl and Skokan.
  • Development of a counting lemma for k-uniform hypergraphs by Nagle, Rodl, and Schacht.

Related Experiment Videos

  • Reduction of the counting problem to a previously studied simpler problem.

    • Main Results:

    • Successful extension of the regularity method to k-uniform hypergraphs.
    • New combinatorial proofs for density theorems.
    • Advancements in extremal combinatorics.

    Conclusions:

    • The regularity method is now applicable to k-uniform hypergraphs.
    • This provides powerful tools for combinatorial enumeration and density problems.
    • Independent confirmation of similar results by Gowers validates the approach.