Matchings and covers in hypergraphs

DOI10.1007/BF01864160zbMath0820.05051OpenAlexW2005616548MaRDI QIDQ1813100

Zoltan Fueredi

Publication date: 25 June 1992

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01864160

zbMATH Keywords

hypergraphmatchingcoverscovering problem

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (93)

On sizes of 1-cross intersecting set pair systems ⋮ Combinatorics in the exterior algebra and the Bollobás Two Families Theorem ⋮ Nearly-perfect hypergraph packing is in NC ⋮ Fractional isomorphism of graphs ⋮ Domination in intersecting hypergraphs ⋮ Efficient constructions of Hitting Sets for systems of linear functions ⋮ The \(p\)-intersection number of a complete bipartite graph and orthogonal double coverings of a clique ⋮ A note on a conjecture of Ryser ⋮ Uniform intersecting families with covering number four ⋮ On a conjecture of Tuza about packing and covering of triangles ⋮ Fractional v. integral covers in hypergraphs of bounded edge size ⋮ Minimal connected \(\tau\)-critical hypergraphs ⋮ On two set-systems with restricted cross-intersections ⋮ Packing directed cycles efficiently ⋮ The skiving stock problem and its relation to hypergraph matchings ⋮ A note on \(\tau\)-critical linear hypergraphs ⋮ On fractional Ramsey numbers ⋮ Approximating set multi-covers ⋮ Maximal intersection critical families of finite sets ⋮ Matching and domination numbers in \(r\)-uniform hypergraphs ⋮ On a theorem of Lovász on covers in \(r\)-partite hypergraphs ⋮ Discrepancies of spanning trees and Hamilton cycles ⋮ On the size of 3-uniform linear hypergraphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Fractional covers of hypergraphs with bounded multi-intersection ⋮ On Brooks' Theorem for Sparse Graphs ⋮ Tuza's conjecture for random graphs ⋮ Problems and results on 1-cross-intersecting set pair systems ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl ⋮ Disjoint systems ⋮ Extremal hypergraphs for matching number and domination number ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Saturating sets in projective planes and hypergraph covers ⋮ A survey on hypergraph products ⋮ A Rainbow r-Partite Version of the Erdős–Ko–Rado Theorem ⋮ A broadcast key distribution scheme based on block designs ⋮ Covers in 4-uniform intersecting families with covering number three ⋮ The existence of \(k\)-radius sequences ⋮ On homomorphisms from the Hamming cube to \(\mathbb{Z}\) ⋮ Sequential legislative lobbying ⋮ Ramsey numbers of path-matchings, covering designs, and 1-cores ⋮ Weighted arcs, the finite Radon transform and a Ramsey problem ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ A note on induced cycles in Kneser graphs ⋮ Covering \(t\)-element sets by partitions ⋮ Blocking sets of the classical unital ⋮ Multiply-intersecting families ⋮ Relative blocking in posets ⋮ Unnamed Item ⋮ A fractional version of the Erdős-Faber-Lovász conjecture ⋮ On covering expander graphs by hamilton cycles ⋮ On the fractional matching polytope of a hypergraph ⋮ On large minimal blocking sets in PG(2,q) ⋮ The finite projective plane and the 5-uniform linear intersecting hypergraphs with domination number four ⋮ On a problem of Erdős and Lovász: Random lines in a projective plane ⋮ Near-perfect clique-factors in sparse pseudorandom graphs ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Small complete arcs in André planes of square order ⋮ A spectrum result on minimal blocking sets with respect to the planes of \(\text{PG}(3, q)\), \(q\) odd ⋮ On a hypergraph matching problem ⋮ On approximation of the vertex cover problem in hypergraphs ⋮ A note on a conjecture by Füredi ⋮ Unnamed Item ⋮ Nearly neighbourly families of standard boxes ⋮ A bound for 1-cross intersecting set pair systems ⋮ Near-perfect clique-factors in sparse pseudorandom graphs ⋮ On Ryser's conjecture for linear intersecting multipartite hypergraphs ⋮ A generalization of Hall's theorem for $k$-uniform $k$-partite hypergraphs ⋮ Domination and matching in power and generalized power hypergraphs ⋮ Invitation to intersection problems for finite sets ⋮ Covering graphs by monochromatic trees and Helly-type results for hypergraphs ⋮ On some covering problems in geometry ⋮ Random constructions and density results ⋮ On the number of pairwise non-isomorphic minimal blocking sets in \(\mathrm{PG}(2,q)\) ⋮ The structure of large non-trivial \(t\)-intersecting families of finite sets ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey ⋮ Blocking sets in Desarguesian affine and projective planes ⋮ Covering graphs: The covering problem solved ⋮ Covers in Block Designs ⋮ On the stochastic independence properties of hard-core distributions ⋮ Triangle packings and 1-factors in oriented graphs ⋮ Small complete arcs in André planes of square order ⋮ Matching criticality in intersecting hypergraphs ⋮ Bounds for optimal coverings ⋮ Pseudorandom hypergraph matchings ⋮ A spectrum result on maximal partial ovoids of the generalized quadrangle \(Q(4,q)\), \(q\) even ⋮ Packing and covering triangles in graphs ⋮ Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number ⋮ The fractional dimension of subsets of Boolean lattices and cartesian products ⋮ Small blocking sets of Hermitian designs ⋮ Intersecting designs from linear programming and graphs of diameter two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Sperner theorem on unrelated chains of subsets
• On the fractional matching polytope of a hypergraph
• Intersection patterns of convex sets
• Minimal coverings of pairs by triples
• On disjointly representable sets
• An intersection problem with 6 extremes
• On Helly families of maximal size
• Large graphs with given degree and diameter. II
• Helly-type hypergraphs and Sperner families
• On coverings of a finite set: Depth and subcovers
• Geometrical solution of an intersection problem for two hypergraphs
• Covering pairs by \(q^ 2+q+1\) sets
• Covering the complete graph by partitions
• Upper bound for transversals of tripartite hypergraphs
• On large sets of disjoint Steiner triple systems. I
• On a packing and covering problem
• Hypergraphs without a large star
• Lower bounds on blocking sets
• On generalized Ramsey numbers for trees
• An extremal problem for sets with applications to graph theory
• Asymptotically good coverings
• A simple proof of the upper bound theorem
• Blocking sets in block designs
• Non-trivial intersecting families
• Critical hypergraphs and interesting set-pair systems
• Families of finite sets in which no set is covered by the union of \(r\) others
• Covering triples by quadruples: an asymptotic solution
• Decomposition of the complete hypergraph into delta-systems. I
• Decomposition of the complete hypergraph into delta-systems. II
• An upper-bound theorem for families of convex sets
• t-expansive and t-wise intersecting hypergraphs
• Embedding maximal cliques of sets in maximal cliques of bigger sets
• Ramsey numbers for the path with three edges
• More on maximal intersecting families of finite sets
• Matching theory
• Inequalities for two set systems with prescribed intersections
• Near perfect coverings in graphs and hypergraphs
• On the representing number of intersecting families
• On the nuclei of a pointset of a finite projective plane
• A lower bound for 0,1,* tournament codes
• A bound for blocking sets of Rédei type in finite projective planes
• Finite projective spaces and intersecting hypergraphs
• On the kernel of intersecting families
• Coverings of pairs by quintuples
• Symmetric designs as the solution of an extremal problem in combinatorial set theory
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Fractional matchings and covers in infinite hypergraphs
• Coverings pairs by quintuples: The case v congruent to 3 (mod 4)
• Bounds of neighborly families of convex polytopes
• On 3-chromatic hypergraphs
• On maximal intersecting families of finite sets
• Coloring n-sets red and blue
• Neighborly families of \(2^ k\) k-simplices in \(E^ k\).
• On the combinatorial problems which I would most like to see solved
• An extremal problem for two families of sets
• Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
• Families of finite sets in which no set is covered by the union of two others
• Golden ratios in a pairs covering problem
• On blocking sets in symmetric BIBD's with \(\lambda\geq 2\)
• Maximum degree and fractional matchings in uniform hypergraphs
• Upper bound on the order of tau-critical hypergraphs
• The chromatic index of cyclic Steiner 2-designs
• Interpolation of functions over a measure space and conjectures about memory
• The orchard problem
• Mutually disjoint families of 0-1 sequences
• On the ratio of optimal integral and fractional covers
• Degrees and matchings
• On two minimax theorems in graph
• Covering finite fields with cosets of subspaces
• The blocking number of an affine space
• Regularisable graphs I
• Helly families of maximal size
• Solution of two fractional packing problems of Lovász
• Long induced paths and cycles in Kneser graphs
• Maximal intersecting families and affine regular polygons in \(PG(2,q)\)
• A Helly type theorem for hypersurfaces
• Matchings in n-partite n-graphs
• Extremal problems among subsets of a set
• Two combinatorial covering theorems
• Solution of a problem of A. Ehrenfeucht and J. Mycielski
• On coverings
• On a family of line-critical graphs
• An extension of a theorem of the Bruijn and Erdős on combinatorial designs
• Normal hypergraphs and the perfect graph conjecture
• Establishing the matching polytope
• On the covering of pairs by quadruples. I
• Intersection theorems for systems of sets
• Edmonds polytopes and a hierarchy of combinatorial problems
• Blocking sets, k-arcs and nets of order ten
• On the covering of pairs by quadruples. II
• An existence theory for pairwise balanced designs. I: Composition theorems and morphisms
• No nine neighborly tetrahedra exist
• A Conjecture Concerning Neighboring Tetrahedra
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection Theorems for Systems of Sets
• Shellable Decompositions of Cells and Spheres.
• Blocking Sets in Finite Projective Planes
• Blocking and anti-blocking pairs of polyhedra
• The 1-Factors of Oriented Graphs
• On a Problem of Additive Number Theory
• Primes in short intervals
• On intersecting families of finite sets
• On intersecting families of finite sets
• DISJOINT r-TUPLES IN AN r-GRAPH WITH GIVEN MAXIMUM DEGREE
• Large Graphs with Given Degree and Diameter—Part I
• On the Fractional Solution to the Set Covering Problem
• Arrangements of Lines with a Large Number of Triangles
• The Number of Edges in a k–Helly Hypergraph
• τ–Critical Hypergraphs and the Helly Property
• On two Combinatorial Problems Arising from Automata Theory
• Partial Parallel Classes in Steiner System S(2, 3, 19)
• Packing Problems and Hypergraph Theory: A Survey
• AN EXTREMAL PROBLEM IN GRAPH THEORY
• Hyperclaw Decomposition of Complete Hypergraphs
• On the Size of a Maximum Transversal in a Steiner Triple System
• Sets of finite sets satisfying union conditions
• Large Graphs with Given Degree and Diameter III
• ON THE WEIGHT DISTRIBUTION IN BINARY CODES GENERATED BY PROJECTIVE PLANES
• 2-Matchings and 2-covers of hypergraphs
• DISJOINT TRIPLES IN A 3-GRAPH WITH GIVEN MAXIMAL DEGREE
• Maximal matchings in graphs with given minimal and maximal degrees
• A generalization of max flow—min cut
• Extremal problems in graph theory
• On the Shannon capacity of a graph
• Graph Theory and Integer Programming
• Neighborly Families of Congruent Convex Polytopes
• Maximal Intersecting Families of Finite Sets and n-Uniform Hjelmslev Planes
• Blocking Sets in Affine Planes
• Properties of vertex packing and independence system polyhedra
• On the Fractional Covering Number of Hypergraphs
• A Problem in Graph Theory
• A Theorem on k-Saturated Graphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Paths, Trees, and Flowers
• On generalized graphs
• Maximum matching and a polyhedron with 0,1-vertices
• On a Conjecture of Erdos, Hajnal and Moon
• On a Problem of C. E. Shannon in Graph Theory
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On a property of families of sets
• On a combinatorial problem. II
• Baer subplanes and blocking sets
• A finite set covering theorem
• The maximum numbers of faces of a convex polytope
• Hide and Seek, Data Storage, and Entropy

This page was built for publication: Matchings and covers in hypergraphs