Jozsef Balogh

About

József Balogh is a professor of mathematics at the University of Illinois, with research interests in graph theory, extremal combinatorics, and additive combinatorics. His main work involves the development of the container theorem and discovering several surprising applications of this method. The container theorem states that in an r-uniform hypergraph, there exists a small collection of vertex subsets (containers) such that every independent set is contained within one of these subsets, which do not induce too many edges. This method has proven to be an effective tool for obtaining probabilistic and counting variants of classical results in graph theory and has contributed to resolving or making breakthroughs on several old conjectures, including those related to Erdös. It has applications across various fields such as Ramsey theory, discrete geometry, and theoretical computer science, and has been utilized in over 40 papers as a main tool. Balogh's work has significantly advanced the understanding of hypergraph structures and combinatorial problems.

Research topics

• Discrete mathematics
• Combinatorics
• Mathematics

Selected publications

• Independent sets in the middle two layers of Boolean lattice

  Journal of Combinatorial Theory Series A · 2020 · 15 citations

  1st authorCorresponding
  DOI

• A Note on Color-Bias Perfect Matchings in Hypergraphs

  SIAM Journal on Discrete Mathematics · 2024-10-04 · 4 citations

  articleOpen access1st authorCorresponding

  A result of Balogh et al. yields the minimum degree threshold that ensures a 2-coloured graph contains a perfect matching of significant colour-bias (i.e., a perfect matching that contains significantly more than half of its edges in one colour). In this note we prove an analogous result for perfect matchings in k-uniform hypergraphs. More precisely, for each 2≤ℓ<k and r≥2 we determine the minimum ℓ-degree threshold for forcing a perfect matching of significant colour-bias in an r-coloured k-…

  PublisherDOI

• On the Maximum F$$ F $$‐Free Induced Subgraphs in Kt$$ {K}_t $$‐Free Graphs

  Random Structures and Algorithms · 2024-12-06 · 3 citations

  articleOpen access1st author

  ABSTRACT For graphs and , let be the minimum possible size of a maximum ‐free induced subgraph in an ‐vertex ‐free graph. This notion generalizes the Ramsey function and the Erdős–Rogers function. Establishing a container lemma for the ‐free subgraphs, we give a general upper bound on , assuming the existence of certain locally dense ‐free graphs. In particular, we prove that for every graph with , where , we have For the cases where is a complete multipartite graph, letting , we prove that We a…

  PublisherOA PDFDOI

• A Sharp Threshold for a Random Version of Sperner's Theorem

  Random Structures and Algorithms · 2024-09-08 · 2 citations

  articleOpen access1st authorCorresponding

  ABSTRACT The Boolean lattice consists of all subsets of partially ordered under the containment relation. Sperner's Theorem states that the largest antichain of the Boolean lattice is given by a middle layer: the collection of all sets of size , or also, if is odd, the collection of all sets of size . Given , choose each subset of with probability independently. We show that for every constant , the largest antichain among these subsets is also given by a middle layer, with probability tending t…

  PublisherDOI

• Non-degenerate hypergraphs with exponentially many extremal constructions

  Journal of Combinatorial Theory Series B · 2025-06-13 · 1 citations

  article1st authorCorresponding
  PublisherDOI

Recent grants

• FRG: Collaborative Research: Extremal Combinatorics and Flag Algebras

  NSF · $509k · 2022–2027

• RTG: Research in Combinatorics

  NSF · $2.5M · 2020–2027

• CAREER: Methods and Outreach in Modern Combinatorics

  NSF · $530k · 2008–2015

Frequent coauthors

• Béla Bollobás

  138 shared

• Robert Morris

  89 shared

• Andrew Treglown

  46 shared

• Felix Christian Clemen

  43 shared

• András Pluhár

  38 shared

• Mark Walters

  37 shared

• Béla Csaba

  37 shared

• Michael Krivelevich

  36 shared

Awards & honors

• NSF CAREER Award, Methods and Outreach in Modern Combinatori…
• Simons Fellow (2013–2014)
• Marie Curie Fellow (2013–2017)
• George Pólya Prize in Combinatorics, SIAM, 2016

Similar researchers at University of Illinois Urbana-Champaign

• Christopher Doddh-60
• William Yun Chenh-40
• Yuliy Baryshnikovh-26