Independent sets in hypergraphs

DOI10.1090/S0894-0347-2014-00816-XzbMath1310.05154arXiv1204.6530WikidataQ105584049 ScholiaQ105584049MaRDI QIDQ5247664

József Balogh, Robert Morris, Wojciech Samotij

Publication date: 27 April 2015

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.6530

zbMATH Keywords

sparse random sets sparse random setting

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Density (toughness, etc.) (05C42)

Related Items

On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles, Large Rainbow Cliques in Randomly Perturbed Dense Graphs, Interview with Yufei Zhao, Rainbow Perfect Matchings for 4-Uniform Hypergraphs, Diagonal Ramsey via effective quasirandomness, Rectilinear approximation and volume estimates for hereditary bodies via [0, 1‐decorated containers], The size‐Ramsey number of cubic graphs, List Ramsey numbers, The Success Probability in Levine’s Hat Problem, and Independent Sets in Graphs, Four‐term progression free sets with three‐term progressions in all large subsets, Approximately counting independent sets in bipartite graphs via graph containers, Asymmetric Ramsey properties of random graphs involving cliques and cycles, Down‐set thresholds, Sharp threshold for the Erdős–Ko–Rado theorem, Balanced supersaturation for some degenerate hypergraphs, On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza, Lower tails via relative entropy, On the maximum $F_5$-free subhypergraphs of a random hypergraph, Intersecting families of sets are typically trivial, On the number of high‐dimensional partitions, Multistage positional games, Finding Cliques in Social Networks: A New Distribution-Free Model, Unnamed Item, Extremal problems in hypergraph colourings, On a topological version of Pach's overlap theorem, The Typical Approximate Structure of Sets with Bounded Sumset, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, The regularity of almost all edge ideals, The asymptotics of $r(4,t)$, On an extremal problem for locally sparse multigraphs, The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups, A Short Proof of the Random Ramsey Theorem, Simple Containers for Simple Hypergraphs, Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability, Unnamed Item, The Structure of Typical Eye-Free Graphs and a Turán-Type Result for Two Weighted Colours, Ramsey-type numbers involving graphs and hypergraphs with large girth, Counting configuration-free sets in groups, Independent sets in the hypercube revisited, Spatially independent martingales, intersections, and applications, Ramsey Goodness of Clique Versus Paths in Random Graphs, The Maker--Breaker Rado Game on a Random Set of Integers, Counting configuration-free sets in groups, Online Ramsey games for more than two colors, Mantel's theorem for random hypergraphs, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems, The Typical Structure of Gallai Colorings and Their Extremal Graphs, Many $T$ copies in $H$-free graphs, Rainbow Erdös--Rothschild Problem for the Fano Plane, List colorings of multipartite hypergraphs, On Erdős–Ko–Rado for Random Hypergraphs II, An efficient container lemma, On Komlós’ tiling theorem in random graphs, Nearly Perfect Matchings in Uniform Hypergraphs, Ramsey properties of randomly perturbed graphs: cliques and cycles, Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties, On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion, The regularity method for graphs with few 4‐cycles, Independent sets in algebraic hypergraphs, On the number of sum-free triplets of sets, Pattern avoidance over a hypergraph, Polynomial configurations in subsets of random and pseudo-random sets, On the structure of large sum-free sets of integers, Ramsey properties of random graphs and folkman numbers, The number of $C_{2\ell}$-free graphs, Arcs in $\mathbb{F}_q^2$, Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs, TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM, THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS, Integer colorings with no rainbow 3-term arithmetic progression, The number of hypergraphs without linear cycles, Integer colorings with no rainbow $k$-term arithmetic progression, A sharp bound on the number of maximal sum-free sets, Ramsey-type numbers involving graphs and hypergraphs with large girth, Online containers for hypergraphs, with applications to linear equations, Normal limiting distributions for systems of linear equations in random sets, The number of $k$-dimensional corner-free subsets of grids, Mantel's theorem for random graphs, The number of the maximal triangle-free graphs, A new proof of the KŁR conjecture, Combinatorial theorems in sparse random sets, Maximum number of sum-free colorings in finite abelian groups, Improved Bound on the Maximum Number of Clique-Free Colorings with Two and Three Colors, A note on sparse supersaturation and extremal results for linear homogeneous systems, Counting $r$-graphs without forbidden configurations, On solution-free sets of integers, On the maximum number of integer colourings with forbidden monochromatic sums, Triangle resilience of the square of a Hamilton cycle in random graphs, The threshold bias of the clique-factor game, Multicolor chain avoidance in the Boolean lattice, Extremal problems for multigraphs, Supersaturation in posets and applications involving the container method, On the number of sets with a given doubling constant, On the probability of nonexistence in binomial subsets, On the stability of the Erdős-Ko-Rado theorem, A probabilistic threshold for monochromatic arithmetic progressions, On vertex independence number of uniform hypergraphs, On an anti-Ramsey threshold for random graphs, On a question of Vera T. Sós about size forcing of graphons, Applications of graph containers in the Boolean lattice, Avoider-forcer games on hypergraphs with small rank, A better bound on the size of rainbow matchings, SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS, List Coloring with a Bounded Palette, A Rainbow Erdös--Rothschild Problem, The number of multiplicative Sidon sets of integers, Independence in 5-uniform hypergraphs, Infinite Sidon Sets Contained in Sparse Random Sets of Integers, A Note on Induced Ramsey Numbers, Structure and enumeration theorems for hereditary properties in finite relational languages, Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers, Extremal results in sparse pseudorandom graphs, A note on improved upper bounds on the transversal number of hypergraphs, A short nonalgorithmic proof of the containers theorem for hypergraphs, On the cycle space of a random graph, Sum-Free Sets of Integers with a Forbidden Sum, On the KŁR conjecture in random graphs, The counting version of a problem of Erdős, An analogue of the Erdős-Gallai theorem for random graphs, Blowup Ramsey numbers, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Lower bounds on Tuza constants for transversals in linear uniform hypergraphs, On the number of monotone sequences, Hypergraph containers, On the number of independent sets in uniform, regular, linear hypergraphs, Triangle-Free Subgraphs of Random Graphs, An analytic approach to sparse hypergraphs: hypergraph removal, On the number of points in general position in the plane, Forbidding induced even cycles in a graph: typical structure and counting, On the structure of oriented graphs and digraphs with forbidden tournaments or cycles, The typical structure of graphs with no large cliques, An exponential-type upper bound for Folkman numbers, On the complexity of finding and counting solution-free sets of integers, Intersecting families of discrete structures are typically trivial, Counting sum-free sets in abelian groups, Random sum-free subsets of abelian groups, The typical structure of sparse $K_{r+1}$-free graphs, The lower tail: Poisson approximation revisited, Bivariate fluctuations for the number of arithmetic progressions in random sets, On the singularity of random symmetric matrices, Rainbow matchings for 3-uniform hypergraphs, On “stability” in the Erdös--Ko--Rado Theorem, On the number of generalized Sidon sets, Ramsey games near the critical threshold, A new lower bound on Hadwiger-Debrunner numbers in the plane, Maximum-size antichains in random set-systems, A sharp threshold for van der Waerden's theorem in random subsets, The number of independent sets in an irregular graph, Counting Gallai 3-colorings of complete graphs, Number of $A + B \neq C$ solutions in abelian groups and application to counting independent sets in hypergraphs, Unified approach to the generalized Turán problem and supersaturation, On the threshold for the Maker-BreakerH-game, Random Van der Waerden theorem, Colouring set families without monochromatic $k$-chains, An asymmetric random Rado theorem: 1-statement, Counting independent sets in graphs, A relative Szemerédi theorem, On the number of union-free families

Cites Work