Buchumschlag

Conflict-free hypergraph matchings and coverings

Recent work showing the existence of conflict-free almost-perfect hypergraph matchings has found many applications. We show that, assuming certain simple degree and codegree conditions on the hypergraph H \mathcal{H} and the conflicts to be avoided, a conflict-free almost-perfect matching can be ext...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Joos, Felix (VerfasserIn) , Mubayi, Dhruv (VerfasserIn) , Smith, Zachary (VerfasserIn)
Dokumenttyp: Article (Journal)
Sprache:Englisch
Veröffentlicht: March 2026
In: Combinatorics, probability & computing
Year: 2026, Jahrgang: 35, Heft: 2, Pages: 230-254
ISSN:1469-2163
DOI:10.1017/S0963548325100291
Online-Zugang:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1017/S0963548325100291
Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/conflictfree-hypergraph-matchings-and-coverings/40E8318628BA6C937FD4AA46CC8A7595
Volltext
Verfasserangaben:Felix Joos, Dhruv Mubayi and Zak Smith

MARC

LEADER 00000naa a2200000 c 4500
001 1962580881
003 DE-627
005 20260225124131.0
007 cr uuu---uuuuu
008 260225s2026 xx |||||o 00| ||eng c
024 7 |a 10.1017/S0963548325100291  |2 doi 
035 |a (DE-627)1962580881 
035 |a (DE-599)KXP1962580881 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 28  |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 Conflict-free hypergraph matchings and coverings  |c Felix Joos, Dhruv Mubayi and Zak Smith 
264 1 |c March 2026 
300 |b Illustrationen 
300 |a 25 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Zuerst online veröffentlicht: 4. Dezember 2025 
500 |a Gesehen am 25.02.2026 
520 |a Recent work showing the existence of conflict-free almost-perfect hypergraph matchings has found many applications. We show that, assuming certain simple degree and codegree conditions on the hypergraph H \mathcal{H} and the conflicts to be avoided, a conflict-free almost-perfect matching can be extended to one covering all vertices in a particular subset of V(H) V(\mathcal{H}), by using an additional set of edges; in particular, we ensure that our matching avoids all additional conflicts, which may consist of both old and new edges. This setup is useful for various applications in design theory and Ramsey theory. For example, our main result provides a crucial tool in the recent proof of the high-girth existence conjecture due to Delcourt and Postle. It also provides a black box which encapsulates many long and tedious calculations, greatly simplifying the proofs of results in generalised Ramsey theory. 
650 4 |a 05C65 
650 4 |a 05C70 
650 4 |a hypergraph 
650 4 |a local lemma 
650 4 |a matching and covering 
650 4 |a Ramsey theory 
650 4 |a random process 
700 1 |a Mubayi, Dhruv  |e VerfasserIn  |4 aut 
700 1 |a Smith, Zachary  |e VerfasserIn  |0 (DE-588)1391277139  |0 (DE-627)1962581101  |4 aut 
773 0 8 |i Enthalten in  |t Combinatorics, probability & computing  |d Cambridge : Cambridge Univ. Press, 1992  |g 35(2026), 2 vom: März, Seite 230-254  |h Online-Ressource  |w (DE-627)271601256  |w (DE-600)1481145-5  |w (DE-576)07870927X  |x 1469-2163  |7 nnas  |a Conflict-free hypergraph matchings and coverings 
773 1 8 |g volume:35  |g year:2026  |g number:2  |g month:03  |g pages:230-254  |g extent:25  |a Conflict-free hypergraph matchings and coverings 
856 4 0 |u https://doi.org/10.1017/S0963548325100291  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext  |7 1 
856 4 0 |u https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/conflictfree-hypergraph-matchings-and-coverings/40E8318628BA6C937FD4AA46CC8A7595  |x Verlag  |z lizenzpflichtig  |3 Volltext  |7 1 
951 |a AR 
992 |a 20260225 
993 |a Article 
994 |a 2026 
998 |g 1391277139  |a Smith, Zachary  |m 1391277139:Smith, Zachary  |d 110000  |d 110300  |d 110000  |e 110000PS1391277139  |e 110300PS1391277139  |e 110000PS1391277139  |k 0/110000/  |k 1/110000/110300/  |k 0/110000/  |p 3  |y j 
998 |g 1075006171  |a Joos, Felix  |m 1075006171:Joos, Felix  |d 110000  |d 110300  |e 110000PJ1075006171  |e 110300PJ1075006171  |k 0/110000/  |k 1/110000/110300/  |p 1  |x j 
999 |a KXP-PPN1962580881  |e 4922242430 
BIB |a Y 
SER |a journal 
JSO |a {"origin":[{"dateIssuedDisp":"March 2026","dateIssuedKey":"2026"}],"type":{"bibl":"article-journal","media":"Online-Ressource"},"language":["eng"],"note":["Zuerst online veröffentlicht: 4. Dezember 2025","Gesehen am 25.02.2026"],"title":[{"title_sort":"Conflict-free hypergraph matchings and coverings","title":"Conflict-free hypergraph matchings and coverings"}],"id":{"eki":["1962580881"],"doi":["10.1017/S0963548325100291"]},"recId":"1962580881","name":{"displayForm":["Felix Joos, Dhruv Mubayi and Zak Smith"]},"physDesc":[{"noteIll":"Illustrationen","extent":"25 S."}],"person":[{"given":"Felix","display":"Joos, Felix","family":"Joos","role":"aut"},{"family":"Mubayi","role":"aut","display":"Mubayi, Dhruv","given":"Dhruv"},{"display":"Smith, Zachary","given":"Zachary","role":"aut","family":"Smith"}],"relHost":[{"part":{"issue":"2","extent":"25","year":"2026","volume":"35","pages":"230-254","text":"35(2026), 2 vom: März, Seite 230-254"},"language":["eng"],"disp":"Conflict-free hypergraph matchings and coveringsCombinatorics, probability & computing","origin":[{"publisher":"Cambridge Univ. Press","publisherPlace":"Cambridge","dateIssuedDisp":"1992-","dateIssuedKey":"1992"}],"type":{"bibl":"periodical","media":"Online-Ressource"},"id":{"eki":["271601256"],"issn":["1469-2163"],"zdb":["1481145-5"]},"recId":"271601256","note":["Gesehen am 05.03.2018"],"title":[{"title_sort":"Combinatorics, probability & computing","title":"Combinatorics, probability & computing","subtitle":"CPC"}],"titleAlt":[{"title":"CPC"}],"pubHistory":["1.1992 -"],"physDesc":[{"extent":"Online-Ressource"}]}]} 
SRT |a JOOSFELIXMCONFLICTFR2026 

Ähnliche Einträge