On a packing and covering problem
From MaRDI portal
Publication:1058516
DOI10.1016/S0195-6698(85)80023-8zbMath0565.05016OpenAlexW2088622619WikidataQ105583798 ScholiaQ105583798MaRDI QIDQ1058516
Publication date: 1985
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0195-6698(85)80023-8
Related Items
The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹 ⋮ Weakly saturated hypergraphs and a conjecture of Tuza ⋮ Concentration of non‐Lipschitz functions and applications ⋮ The shortest disjunctive normal form of a random Boolean function ⋮ Probabilistic combinatorics and the recent work of Peter Keevash ⋮ Turán numbers of sunflowers ⋮ Independence numbers and chromatic numbers of the random subgraphs of some distance graphs ⋮ New bounds for Ryser’s conjecture and related problems ⋮ Asymptotic packing via a branching process ⋮ Long gaps between primes ⋮ Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity ⋮ Linear cycles of consecutive lengths ⋮ Avoiding right angles and certain Hamming distances ⋮ Friendly bisections of random graphs ⋮ The Ramsey number R(3, t) has order of magnitude t2/log t ⋮ On Brooks' Theorem for Sparse Graphs ⋮ On asymptotic packing of convex geometric and ordered graphs ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ A proof of the Erdős-Faber-Lovász conjecture ⋮ The number of \(n\)-queens configurations ⋮ Near-optimal distributed edge coloring ⋮ On secret sharing, randomness, and random-less reductions for secret sharing ⋮ Independence numbers of Johnson-type graphs ⋮ Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor ⋮ New bounds on the size of nearly perfect matchings in almost regular hypergraphs ⋮ Coloring unions of nearly disjoint hypergraph cliques ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Perfectly packing graphs with bounded degeneracy and many leaves ⋮ Many Cliques in Bounded-Degree Hypergraphs ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Threshold for Steiner triple systems ⋮ Kalai's conjecture in \(r\)-partite \(r\)-graphs ⋮ Approximate Steiner (r − 1, r, n)‐systems without three blocks on r + 2 points ⋮ Packing cliques in 3‐uniform hypergraphs ⋮ Graph and hypergraph packing ⋮ Prominent examples of flip processes ⋮ On the Maximum Number of Spanning Copies of an Orientation in a Tournament ⋮ Bin Packing with Colocations ⋮ Minimalist designs ⋮ Unnamed Item ⋮ On Tight Cycles in Hypergraphs ⋮ Sparse Hypergraphs with Applications to Coding Theory ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ Almost all Steiner triple systems are almost resolvable ⋮ Coloured and Directed Designs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Unnamed Item ⋮ Turán and Ramsey Properties of Subcube Intersection Graphs ⋮ New constructions for covering designs ⋮ Bootstrap Percolation in High Dimensions ⋮ On the Independence Number of Steiner Systems ⋮ Near-perfect clique-factors in sparse pseudorandom graphs ⋮ New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help ⋮ Note on asymptotically good packings ⋮ Integer and fractional packing of families of graphs ⋮ Connected Covering Numbers ⋮ On the number of partial Steiner systems ⋮ Near-optimal list colorings ⋮ Forbidden Intersections ⋮ The effect of induced subgraphs on quasi-randomness ⋮ Extremal bounds for bootstrap percolation in the hypercube ⋮ Minimum rainbow \(H\)-decompositions of graphs ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Extremal problems for triple systems ⋮ A natural barrier in random greedy hypergraph matching ⋮ Bounds on the Maximum Number of Vectors with given Scalar Products ⋮ Hypergraphs Not Containing a Tight Tree with a Bounded Trunk ⋮ Generalized covering designs and clique coverings ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Supersaturation of even linear cycles in linear hypergraphs ⋮ Pseudorandom hypergraph matchings ⋮ On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs ⋮ Weak quasi-randomness for uniform hypergraphs ⋮ Extremal bounds for bootstrap percolation in the hypercube ⋮ Fractional decompositions of dense hypergraphs ⋮ The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent ⋮ On the upper bound of the size of the \(r\)-cover-free families ⋮ Hypergraph Extensions of the Erdős-Gallai Theorem ⋮ An approximate version of the tree packing conjecture ⋮ All rationals occur as exponents ⋮ Counting Steiner triple systems ⋮ Additive combinatorics and graph theory ⋮ Nearly-perfect hypergraph packing is in NC ⋮ Colouring graphs with sparse neighbourhoods: bounds and applications ⋮ Probabilistic methods ⋮ Near perfect coverings in graphs and hypergraphs ⋮ Distance Ramsey numbers ⋮ On the difference between asymptotically good packings and coverings ⋮ On a combinatorial problem for the set of binary vectors ⋮ Unnamed Item ⋮ What we know and what we do not know about Turán numbers ⋮ On the power of random greedy algorithms ⋮ Fractional v. integral covers in hypergraphs of bounded edge size ⋮ Large independent sets in regular graphs of large girth ⋮ Minimum \(H\)-decompositions of graphs ⋮ Forbidden submatrices ⋮ On two set-systems with restricted cross-intersections ⋮ Nearly perfect matchings in regular simple hypergraphs ⋮ Exact solution of some Turán-type problems ⋮ Representability and boxicity of simplicial complexes ⋮ A Construction of Almost Steiner Systems ⋮ Hierarchical models as marginals of hierarchical models ⋮ New bounds for the distance Ramsey number ⋮ Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths ⋮ A gentle introduction to the differential equation method and dynamic concentration ⋮ On the maximal number of edges in a uniform hypergraph with one forbidden intersection ⋮ On a problem of Erdős and Moser ⋮ On the number of edges of a uniform hypergraph with a range of allowed intersections ⋮ Supersaturation for hereditary properties ⋮ Subspace packings: constructions and bounds ⋮ System of unbiased representatives for a collection of bicolorings ⋮ Lower bounds for coverings of pairs by large blocks ⋮ Unavoidable subhypergraphs: \(\mathbf a\)-clusters ⋮ The existence of \(k\)-radius sequences ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Number of 1-factorizations of regular high-degree graphs ⋮ Decompositions into isomorphic rainbow spanning trees ⋮ Sparse hypergraphs: new bounds and constructions ⋮ Optimal covers with Hamilton cycles in random graphs ⋮ The number of \(t\)-wise balanced designs ⋮ On a covering problem in the hypercube ⋮ Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors ⋮ A note on supersaturated set systems ⋮ Coding for a multiple access OR channel: A survey ⋮ Towards the linear arboricity conjecture ⋮ Generalising Fisher's inequality to coverings and packings ⋮ Tight cycles and regular slices in dense hypergraphs ⋮ Forbidden configurations and Steiner designs ⋮ Asymptotically optimal frugal colouring ⋮ Almost disjoint families of 3-term arithmetic progressions ⋮ Suitable sets of permutations, packings of triples, and Ramsey's theorem ⋮ On a hypergraph matching problem ⋮ A novel use of \(t\)-packings to construct \(d\)-disjunct matrices ⋮ Hamiltonian cycles in Dirac graphs ⋮ On extremal hypergraphs for forests of tight paths ⋮ Constructions and bounds for separating hash families ⋮ Asymptotic estimates on the von Neumann inequality for homogeneous polynomials ⋮ Linear trees in uniform hypergraphs ⋮ Hypergraph extensions of the Erdős-Gallai theorem ⋮ Invitation to intersection problems for finite sets ⋮ Random constructions and density results ⋮ Bounds on the sizes of constant weight covering codes ⋮ On subsets of the hypercube with prescribed Hamming distances ⋮ Chromatic numbers of Kneser-type graphs ⋮ On the realization of subgraphs of a random graph by diameter graphs in Euclidean spaces ⋮ Asymptotic enumeration of linear hypergraphs with given number of vertices and edges ⋮ Matchings and covers in hypergraphs ⋮ Degenerate Turán densities of sparse hypergraphs ⋮ Hypergraphs not containing a tight tree with a bounded trunk. II: 3-trees with a trunk of size 2 ⋮ Near-optimal, distributed edge colouring via the nibble method ⋮ Two-regular subgraphs of hypergraphs ⋮ Triangle packings and 1-factors in oriented graphs ⋮ The minimum likely column cover problem ⋮ Arboricity: an acyclic hypergraph decomposition problem motivated by database theory ⋮ Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping ⋮ Bounding the strong chromatic index of dense random graphs ⋮ Bounds for optimal coverings ⋮ Variable neighborhood descent heuristic for covering design problem ⋮ Partitioning the power set of \([n\) into \(C_k\)-free parts] ⋮ On asymptotic packing of geometric graphs ⋮ Vertex-disjoint claws in graphs ⋮ Asymptotically optimal \(K_k\)-packings of dense graphs via fractional \(K_k\)-decompositions ⋮ Connected coverings and an application to oriented matroids ⋮ Unavoidable subhypergraphs: a-clusters ⋮ Graph imperfection. II ⋮ On the size of partial block designs with large blocks ⋮ Decomposing hypergraphs into cycle factors ⋮ Random triangle removal ⋮ Asymptotic behavior of the chromatic index for hypergraphs ⋮ Covering pairs by \(q^ 2+q+1\) sets ⋮ New upper bound for the chromatic number of a random subgraph of a distance graph ⋮ Probabilistic methods in coloring and decomposition problems ⋮ Packing of partial designs ⋮ Independence numbers and chromatic numbers of some distance graphs
Cites Work
