Supersaturated graphs and hypergraphs
From MaRDI portal
In this paper are investigated supersaturated graphs and hypergraphs. Let \(\mathcal L\) be a family of graphs (hypergraphs) and ex \((n,\mathcal L)\) denote the maximum number of edges (hyperedges) of a graph (hypergraph) on \(n\) vertices which do not contain a subgraph from \(\mathcal L\). A graph (hypergraph) with \(n\) vertices containing more than \(\text{ex}(n,\mathcal L)\) edges es called a supersaturated graph (hypergraph). The problem solved in this paper is to determine the number of copies of a subgraph from \(\mathcal L\) which must occur in a supersaturated graph (hypergraph) with \(\text{ex}(n,\mathcal L)+k\) edges. There are given some lower bounds for the number of subgraphs from \(\mathcal L\) with respect to value of \(k\). In the case of ordinary graphs the characterisation of supersaturated graphs with a low number of prohibited subgraphs is given.
Recommendations
- Supersaturated sparse graphs and hypergraphs
- scientific article; zbMATH DE number 3900799
- On the super domination number of graphs
- scientific article; zbMATH DE number 5762364
- Supereulerian graphs: A survey
- Publication:4731211
- Super domination in graphs
- Supersaturation for subgraph counts
- Super-pancyclic hypergraphs and bipartite graphs
- Super dominating sets in graphs
Cites work
- Compactness results in extremal graph theory
- scientific article; zbMATH DE number 3821782 (Why is no real title available?)
- scientific article; zbMATH DE number 3188526 (Why is no real title available?)
- On complete subgraphs of different orders
- On extremal problems of graphs and generalized graphs
- On some extremal problems on r-graphs
- On the Structure of Edge Graphs II
- On the structure of linear graphs
Cited in
(only showing first 100 items - show all)- The SAT-UNSAT transition for random constraint satisfaction problems
- Some Turán type results on the hypercube
- Extremal problems concerning Kneser-graphs
- The maximum number of disjoint pairs in a family of subsets
- A note on superbrittle graphs
- Some Ramsey-Turán type results for hypergraphs
- Exact solution of some Turán-type problems
- Superextensions and the depth of median graphs
- Supersaturation of C₄: from Zarankiewicz towards Erdős-Simonovits-Sidorenko
- Supersaturation in posets and applications involving the container method
- Strong forms of stability from flag algebra calculations
- A fractional Helly theorem for convex lattice sets
- Multiplicities of subgraphs
- On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
- Some sharp results on the generalized Turán numbers
- On Hamiltonian cycles in hypergraphs with dense link graphs
- Convex graphon parameters and graph norms
- Unified approach to the generalized Turán problem and supersaturation
- Supersaturation for subgraph counts
- Spanning surfaces in \(3\)-graphs
- Cut distance identifying graphon parameters over weak* limits
- Multicolor Turán numbers
- Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
- Intersection patterns of planar sets
- Super-pancyclic hypergraphs and bipartite graphs
- Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs
- Minimum pair degree condition for tight Hamiltonian cycles in 4-uniform hypergraphs
- Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph
- Supergraphs and the cubic Leigh-Strassler model
- Finitely forcible graphons
- Ordered graphs and large bi-cliques in intersection graphs of curves
- The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
- \(F\)-factors in hypergraphs via absorption
- Berge's theorem, fractional Helly, and art galleries
- Forbidding complete hypergraphs as traces
- Pairs of SAT-assignments in random Boolean formulæ
- Non-uniform Turán-type problems
- The co-degree density of the Fano plane
- A hypergraph extension of Turán's theorem
- A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
- On the number of halving planes
- Co-degree density of hypergraphs
- Impartial digraphs
- The Turán number of blow-ups of trees
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
- Constructing designs straightforwardly: Worst arising cases
- The number of the maximal triangle-free graphs
- The codegree threshold for 3-graphs with independent neighborhoods
- The complexity of vertex coloring problems in uniform hypergraphs with high degree
- scientific article; zbMATH DE number 426325 (Why is no real title available?)
- Complete partite subgraphs in dense hypergraphs
- scientific article; zbMATH DE number 3885945 (Why is no real title available?)
- Online containers for hypergraphs, with applications to linear equations
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Sidorenko's conjecture for blow-ups
- DIAMOND GRAPHS AND SUPER-REFLEXIVITY
- Turán number of generalized triangles
- Extremal graph theory and face numbers of flag triangulations of manifolds
- Extremal results for random discrete structures
- Combinatorial theorems in sparse random sets
- On the Minimal Density of Triangles in Graphs
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- scientific article; zbMATH DE number 3900799 (Why is no real title available?)
- The Chromatic Number of Kneser Hypergraphs
- Supersaturation for hereditary properties
- SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
- Point Selections and Weak ε-Nets for Convex Hulls
- Sharp thresholds for certain Ramsey properties of random graphs
- Independent sets in hypergraphs and Ramsey properties of graphs and the integers
- Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
- Tverberg’s theorem is 50 years old: A survey
- Turán problems on non-uniform hypergraphs
- On the KŁR conjecture in random graphs
- Turán and Ramsey properties of subcube intersection graphs
- Turánnical hypergraphs
- Supersaturation and stability for forbidden subposet problems.
- On the number of monotone sequences
- Decompositions into subgraphs of small diameter
- Hypergraph containers
- Supersaturation of even linear cycles in linear hypergraphs
- Estimating parameters associated with monotone properties
- Snarks, hypohamiltonian graphs and non-supereulerian graphs
- On the extremal number of subdivisions
- The exact minimum number of triangles in graphs with given order and size
- Relative Turán problems for uniform hypergraphs
- Supersaturated sparse graphs and hypergraphs
- Independent sets in hypergraphs
- The number of additive triples in subsets of abelian groups
- On the Chromatic Thresholds of Hypergraphs
- Simple containers for simple hypergraphs
- Exact minimum codegree threshold for K^-_4-factors
- Nerves, minors, and piercing numbers
- Stability results for random discrete structures
- There exist graphs with super‐exponential Ramsey multiplicity constant
- Flag algebras
- scientific article; zbMATH DE number 2192110 (Why is no real title available?)
- Dense flag triangulations of 3-manifolds via extremal graph theory
- A geometric theory for hypergraph matching
- Testing subgraphs in directed graphs
This page was built for publication: Supersaturated graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q787158)
