An extremal problem for sets with applications to graph theory

DOI10.1016/0097-3165(85)90048-2MaRDI QIDQ1066141zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon

Publication date 1985

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(85)90048-2

zbMATH Keywords

saturated graphssaturated hypergraphsset partition

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Recommendations

• scientific article; zbMATH DE number 3880761
• Solution of an extremal problem for sets using resultants of polynomials
• Extremal problems concerning Kneser-graphs
• scientific article; zbMATH DE number 1234983
• On extremal problems of graphs and generalized graphs

Cites work

• A Problem in Graph Theory
• A simple proof of the upper bound theorem
• An extremal problem for two families of sets
• scientific article; zbMATH DE number 3920492 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3530031 (Why is no real title available?)
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 3239217 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• scientific article; zbMATH DE number 3370377 (Why is no real title available?)
• Hyperconnectivity of graphs
• Intersection patterns of convex sets
• On a Conjecture of Erdos, Hajnal and Moon
• On generalized graphs
• Solution of a problem of A. Ehrenfeucht and J. Mycielski

Cited in

(73)

• A simple proof of the upper bound theorem
• Hyperconnectivity of graphs
• Covering graphs by the minimum number of equivalence relations
• On the kernel of intersecting families
• A note on induced cycles in Kneser graphs
• Asymptotic growth of sparse saturated structures is locally determined
• An extremal problem for sets: A new approach via Bezoutians
• Matchings and covers in hypergraphs
• The extreme set condition of a graph
• A sharp threshold for bootstrap percolation in a random hypergraph
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Bollobás-type theorems for hemi-bundled two families
• Strong edge coloring of Cayley graphs and some product graphs
• \(K_{r,s}\) graph bootstrap percolation
• Weak saturation numbers of complete bipartite graphs in the clique
• Exact bounds for some hypergraph saturation problems
• Collapsibility of simplicial complexes of hypergraphs
• Counting contours on trees
• The partite saturation number of spider
• Minimum C_k-saturated graphs
• Graph bootstrap percolation
• scientific article; zbMATH DE number 3880761 (Why is no real title available?)
• scientific article; zbMATH DE number 15459 (Why is no real title available?)
• scientific article; zbMATH DE number 1234983 (Why is no real title available?)
• Linear algebra and bootstrap percolation
• The solution and applications of a combinatorial problem
• scientific article; zbMATH DE number 637337 (Why is no real title available?)
• scientific article; zbMATH DE number 736306 (Why is no real title available?)
• \(K_{s,t}\)-saturated bipartite graphs
• scientific article; zbMATH DE number 878901 (Why is no real title available?)
• Cycle-saturated graphs with minimum number of edges
• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Combinatorics in the exterior algebra and the Bollobás two families theorem
• On the maximum running time in graph bootstrap percolation
• Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs
• Saturation in the hypercube and bootstrap percolation
• scientific article; zbMATH DE number 969992 (Why is no real title available?)
• scientific article; zbMATH DE number 4185671 (Why is no real title available?)
• Extremal Uniquely Resolvable Multisets
• Weakly saturated hypergraphs and a conjecture of Tuza
• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Long running times for hypergraph bootstrap percolation
• Weak saturation stability
• Problems and results on 1-cross-intersecting set pair systems
• On the running time of hypergraph bootstrap percolation
• Weak saturation number of a complete bipartite graph
• Weakly saturated subgraphs of random graphs
• Rainbow Saturation for Complete Graphs
• Fractional Helly theorem for Cartesian products of convex sets
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Strictly monotonic multidimensional sequences and stable sets in pillage games
• Maximal matroids in weak order posets
• The rainbow saturation number is linear
• The weak saturation number of \(K_{2,t}\)
• \(K_r\)-saturated graphs and the two families theorem
• Weak saturation numbers in random graphs
• The maximum length of K_r-bootstrap percolation
• Weak saturation numbers for the union of disjoint graphs
• Some new Bollobás-type inequalities
• An extension of a fixed point problem for simple graphs
• On Bollobás-type theorems of d-tuples
• Variations on Bollobás systems of d-partitions
• Bollobás set pair inequalities for compositions
• Weak rainbow saturation numbers of graphs
• Weak saturation in graphs: a combinatorial approach
• Saturation of K₄ subdivisions in multidimensional grids
• Colorful fractional Helly theorem via weak saturation
• A saturation problem in meshes
• A note on weak saturation number of trees
• Clique number of xor-powers of Kneser graphs
• A short proof of Tuza's conjecture for weak saturation in hypergraphs
• Solution of an extremal problem for sets using resultants of polynomials

This page was built for publication: An extremal problem for sets with applications to graph theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1066141)