Fractional cycle decompositions in hypergraphs
We prove that for any integer and , there is an integer such that any k-uniform hypergraph on n vertices with minimum codegree at least has a fractional decomposition into (tight) cycles of length (-cycles for short) whenever and n is large in terms of . This is essentially tight. This immediately y...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
14 December 2021
|
| In: |
Random structures & algorithms
Year: 2022, Volume: 61, Issue: 3, Pages: 425-443 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21070 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1002/rsa.21070 Verlag, kostenfrei, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21070 
|
| Author Notes: | Felix Joos, Marcus Kühn |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1826817042 | ||
| 003 | DE-627 | ||
| 005 | 20230117203132.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 221212s2022 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1002/rsa.21070 |2 doi | |
| 035 | |a (DE-627)1826817042 | ||
| 035 | |a (DE-599)KXP1826817042 | ||
| 035 | |a (OCoLC)1360436668 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 245 | 1 | 0 | |a Fractional cycle decompositions in hypergraphs |c Felix Joos, Marcus Kühn |
| 264 | 1 | |c 14 December 2021 | |
| 300 | |a 19 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 12.12.2022 | ||
| 520 | |a We prove that for any integer and , there is an integer such that any k-uniform hypergraph on n vertices with minimum codegree at least has a fractional decomposition into (tight) cycles of length (-cycles for short) whenever and n is large in terms of . This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into -cycles. Moreover, for graphs this even guarantees integral decompositions into -cycles and solves a problem posed by Glock, Kühn, and Osthus. For our proof, we introduce a new method for finding a set of -cycles such that every edge is contained in roughly the same number of -cycles from this set by exploiting that certain Markov chains are rapidly mixing. | ||
| 650 | 4 | |a cycles | |
| 650 | 4 | |a hypergraph decompositions | |
| 650 | 4 | |a random walk | |
| 700 | 1 | |a Kühn, Marcus |d 1992- |e VerfasserIn |0 (DE-588)1262516110 |0 (DE-627)1810215870 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Random structures & algorithms |d New York, NY [u.a.] : Wiley, 1990 |g 61(2022), 3, Seite 425-443 |h Online-Ressource |w (DE-627)306711141 |w (DE-600)1500812-5 |w (DE-576)082436185 |x 1098-2418 |7 nnas |a Fractional cycle decompositions in hypergraphs |
| 773 | 1 | 8 | |g volume:61 |g year:2022 |g number:3 |g pages:425-443 |g extent:19 |a Fractional cycle decompositions in hypergraphs |
| 856 | 4 | 0 | |u https://doi.org/10.1002/rsa.21070 |x Verlag |x Resolving-System |z kostenfrei |3 Volltext |
| 856 | 4 | 0 | |u https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21070 |x Verlag |z kostenfrei |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20221212 | ||
| 993 | |a Article | ||
| 994 | |a 2022 | ||
| 998 | |g 1262516110 |a Kühn, Marcus |m 1262516110:Kühn, Marcus |d 110000 |d 110300 |e 110000PK1262516110 |e 110300PK1262516110 |k 0/110000/ |k 1/110000/110300/ |p 2 |y j | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |d 110000 |d 110300 |d 700000 |d 728500 |e 110000PJ1075006171 |e 110300PJ1075006171 |e 700000PJ1075006171 |e 728500PJ1075006171 |k 0/110000/ |k 1/110000/110300/ |k 0/700000/ |k 1/700000/728500/ |p 1 |x j | ||
| 999 | |a KXP-PPN1826817042 |e 4229124570 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"recId":"1826817042","person":[{"display":"Joos, Felix","given":"Felix","role":"aut","family":"Joos"},{"display":"Kühn, Marcus","given":"Marcus","role":"aut","family":"Kühn"}],"note":["Gesehen am 12.12.2022"],"name":{"displayForm":["Felix Joos, Marcus Kühn"]},"language":["eng"],"relHost":[{"recId":"306711141","origin":[{"dateIssuedKey":"1990","publisherPlace":"New York, NY [u.a.]","publisher":"Wiley","dateIssuedDisp":"1990-"}],"title":[{"title_sort":"Random structures & algorithms","title":"Random structures & algorithms"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"issn":["1098-2418"],"eki":["306711141"],"doi":["10.1002/(ISSN)1098-2418"],"zdb":["1500812-5"]},"pubHistory":["1.1990 -"],"note":["Gesehen am 17.02.05"],"language":["eng"],"part":{"volume":"61","year":"2022","text":"61(2022), 3, Seite 425-443","issue":"3","extent":"19","pages":"425-443"},"titleAlt":[{"title":"Random structures and algorithms"}],"disp":"Fractional cycle decompositions in hypergraphsRandom structures & algorithms","type":{"bibl":"periodical","media":"Online-Ressource"}}],"origin":[{"dateIssuedDisp":"14 December 2021","dateIssuedKey":"2022"}],"title":[{"title":"Fractional cycle decompositions in hypergraphs","title_sort":"Fractional cycle decompositions in hypergraphs"}],"type":{"media":"Online-Ressource","bibl":"article-journal"},"id":{"eki":["1826817042"],"doi":["10.1002/rsa.21070"]},"physDesc":[{"extent":"19 S."}]} | ||
| SRT | |a JOOSFELIXKFRACTIONAL1420 | ||