Hypergraphs of bounded disjointness
A κ-uniform hypergraph is s-almost intersecting if every edge is disjoint from exactly s other edges. Gerbner et al. [SIAM J. Discrete Math., 26 (2012), pp. 1657 1669] conjectured that for every κ, and s s0(κ), every k-uniform s-almost intersecting hypergraph has at most (s+1)(2k-2 k-1 edges. We pro...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Society for Industrial and Applied Mathematics
2014
|
| _version_ | 1826258895843098624 |
|---|---|
| author | Scott, A Wilmer, E |
| author_facet | Scott, A Wilmer, E |
| author_sort | Scott, A |
| collection | OXFORD |
| description | A κ-uniform hypergraph is s-almost intersecting if every edge is disjoint from exactly s other edges. Gerbner et al. [SIAM J. Discrete Math., 26 (2012), pp. 1657 1669] conjectured that for every κ, and s s0(κ), every k-uniform s-almost intersecting hypergraph has at most (s+1)(2k-2 k-1 edges. We prove a strengthened version of this conjecture and determine the extremal graphs. We also give some related results and conjectures. |
| first_indexed | 2024-03-06T18:41:16Z |
| format | Journal article |
| id | oxford-uuid:0cf0bea3-ff4a-4912-b1f5-db2ec930b451 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:41:16Z |
| publishDate | 2014 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:0cf0bea3-ff4a-4912-b1f5-db2ec930b4512022-03-26T09:37:51ZHypergraphs of bounded disjointnessJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0cf0bea3-ff4a-4912-b1f5-db2ec930b451Symplectic Elements at OxfordSociety for Industrial and Applied Mathematics2014Scott, AWilmer, EA κ-uniform hypergraph is s-almost intersecting if every edge is disjoint from exactly s other edges. Gerbner et al. [SIAM J. Discrete Math., 26 (2012), pp. 1657 1669] conjectured that for every κ, and s s0(κ), every k-uniform s-almost intersecting hypergraph has at most (s+1)(2k-2 k-1 edges. We prove a strengthened version of this conjecture and determine the extremal graphs. We also give some related results and conjectures. |
| spellingShingle | Scott, A Wilmer, E Hypergraphs of bounded disjointness |
| title | Hypergraphs of bounded disjointness |
| title_full | Hypergraphs of bounded disjointness |
| title_fullStr | Hypergraphs of bounded disjointness |
| title_full_unstemmed | Hypergraphs of bounded disjointness |
| title_short | Hypergraphs of bounded disjointness |
| title_sort | hypergraphs of bounded disjointness |
| work_keys_str_mv | AT scotta hypergraphsofboundeddisjointness AT wilmere hypergraphsofboundeddisjointness |