DC FieldValueLanguage
dc.contributor.authorClemens, Dennis-
dc.contributor.authorDas, Shagnik-
dc.contributor.authorTran, Tuan-
dc.date.accessioned2019-07-12T15:47:18Z-
dc.date.available2019-07-12T15:47:18Z-
dc.date.issued2018-05-
dc.identifier.citationEuropean Journal of Combinatorics (70): 99-124 (2018-05)de_DE
dc.identifier.issn0195-6698de_DE
dc.identifier.urihttp://hdl.handle.net/11420/2947-
dc.description.abstractThe typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.en
dc.language.isoende_DE
dc.relation.ispartofEuropean journal of combinatoricsde_DE
dc.titleColourings without monochromatic disjoint pairsde_DE
dc.typeArticlede_DE
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.abstract.englishThe typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.de_DE
tuhh.publisher.doi10.1016/j.ejc.2017.12.006-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.type.opus(wissenschaftlicher) Artikel-
tuhh.institute.germanMathematik E-10de
tuhh.institute.englishMathematik E-10de_DE
tuhh.gvk.hasppnfalse-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.volume70de_DE
tuhh.container.startpage99de_DE
tuhh.container.endpage124de_DE
dc.identifier.scopus2-s2.0-85044674911-
datacite.resourceTypeJournal Article-
datacite.resourceTypeGeneralText-
item.grantfulltextnone-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.creatorGNDClemens, Dennis-
item.creatorGNDDas, Shagnik-
item.creatorGNDTran, Tuan-
item.openairetypeArticle-
item.fulltextNo Fulltext-
item.cerifentitytypePublications-
item.creatorOrcidClemens, Dennis-
item.creatorOrcidDas, Shagnik-
item.creatorOrcidTran, Tuan-
item.languageiso639-1en-
item.mappedtypeArticle-
crisitem.author.deptMathematik E-10-
crisitem.author.orcid0000-0001-5940-6556-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik-
Appears in Collections:Publications without fulltext
Show simple item record

Page view(s)

126
Last Week
1
Last month
1
checked on Aug 17, 2022

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
checked on Jun 30, 2022

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.