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 {"language":["eng"],"note":["Gesehen am 12.12.2022"],"physDesc":[{"extent":"19 S."}],"relHost":[{"language":["eng"],"disp":"Fractional cycle decompositions in hypergraphsRandom structures & algorithms","physDesc":[{"extent":"Online-Ressource"}],"note":["Gesehen am 17.02.05"],"origin":[{"dateIssuedKey":"1990","dateIssuedDisp":"1990-","publisher":"Wiley","publisherPlace":"New York, NY [u.a.]"}],"titleAlt":[{"title":"Random structures and algorithms"}],"title":[{"title_sort":"Random structures & algorithms","title":"Random structures & algorithms"}],"type":{"bibl":"periodical","media":"Online-Ressource"},"part":{"volume":"61","text":"61(2022), 3, Seite 425-443","extent":"19","year":"2022","pages":"425-443","issue":"3"},"pubHistory":["1.1990 -"],"id":{"doi":["10.1002/(ISSN)1098-2418"],"issn":["1098-2418"],"zdb":["1500812-5"],"eki":["306711141"]},"recId":"306711141"}],"origin":[{"dateIssuedKey":"2022","dateIssuedDisp":"14 December 2021"}],"title":[{"title_sort":"Fractional cycle decompositions in hypergraphs","title":"Fractional cycle decompositions in hypergraphs"}],"type":{"bibl":"article-journal","media":"Online-Ressource"},"person":[{"role":"aut","given":"Felix","roleDisplay":"VerfasserIn","display":"Joos, Felix","family":"Joos"},{"family":"Kühn","roleDisplay":"VerfasserIn","given":"Marcus","display":"Kühn, Marcus","role":"aut"}],"name":{"displayForm":["Felix Joos, Marcus Kühn"]},"id":{"eki":["1826817042"],"doi":["10.1002/rsa.21070"]},"recId":"1826817042"} | ||
| SRT | |a JOOSFELIXKFRACTIONAL1420 | ||