Colourings without monochromatic disjoint pairs

DOI10.1016/J.EJC.2017.12.006zbMATH Open1384.05084arXiv1612.04510OpenAlexW2584177032MaRDI QIDQ1746571FDOQ1746571

Authors: Xianqiang Yang 

Publication date: 25 April 2018

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The ErdH{o}s-Rothschild problem, introduced in 1974 by ErdH{o}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 ErdH{o}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 ErdH{o}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 ErdH{o}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 ErdH{o}s-Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.

Full work available at URL: https://arxiv.org/abs/1612.04510

Recommendations

• Colouring set families without monochromatic \(k\)-chains
• Multicoloured extremal problems
• A rainbow Erdös-Rothschild problem
• A rainbow Erdős-Rothschild problem
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques

zbMATH Keywords

Erdős-Rothschild problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Intersection theorems for systems of finite vector spaces
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete nontrivial-intersection theorem for systems of finite sets
• Title not available (Why is that?)
• The exact bound in the Erdős-Ko-Rado theorem
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting families of discrete structures are typically trivial
• Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• Title not available (Why is that?)
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Title not available (Why is that?)
• The Erdős-Ko-Rado theorem for vector spaces
• Intersecting families of permutations
• Maximum degree and fractional matchings in uniform hypergraphs
• Stability for \(t\)-intersecting families of permutations
• Edge colourings of graphs avoiding monochromatic matchings of a given size
• On colourings of hypergraphs without monochromatic Fano planes
• Hypergraphs with many Kneser colorings
• An unstable hypergraph problem with a unique optimal solution
• Exact results on the number of restricted edge colorings for some families of linear hypergraphs
• A structural result for hypergraphs with many restricted edge colorings
• A Hilton-Milner theorem for vector spaces
• Edge-colorings of uniform hypergraphs avoiding monochromatic matchings
• On intersecting families of finite sets
• A coloring problem for intersecting vector spaces
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques

Cited In (14)

• Title not available (Why is that?)
• Remarks on an edge-coloring problem
• Multicoloured extremal problems
• Coloring Ordered Sets to Avoid Monochromatic Maximal Chains
• Colouring set families without monochromatic \(k\)-chains
• Integer colorings with forbidden rainbow sums
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• A coloring problem for intersecting vector spaces
• Rainbow Erdös-Rothschild problem for the Fano plane
• Title not available (Why is that?)
• Maximum number of triangle-free edge colourings with five and six colours
• Erdős-Ko-Rado and Hilton-Milner theorems for two-forms
• On the maximum number of integer colourings with forbidden monochromatic sums
• Coloring cross-intersecting families

This page was built for publication: Colourings without monochromatic disjoint pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1746571)