Colourings without monochromatic disjoint pairs
From MaRDI portal
Publication:1746571
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3487496 (Why is no real title available?)
- scientific article; zbMATH DE number 881297 (Why is no real title available?)
- scientific article; zbMATH DE number 3041944 (Why is no real title available?)
- A Hilton-Milner theorem for vector spaces
- A coloring problem for intersecting vector spaces
- A structural result for hypergraphs with many restricted edge colorings
- An unstable hypergraph problem with a unique optimal solution
- Edge colourings of graphs avoiding monochromatic matchings of a given size
- Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number
- Edge-colorings of uniform hypergraphs avoiding monochromatic matchings
- Exact results on the number of restricted edge colorings for some families of linear hypergraphs
- Hypergraphs with many Kneser colorings
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersecting families of discrete structures are typically trivial
- Intersecting families of permutations
- Intersection theorems for systems of finite vector spaces
- Maximum degree and fractional matchings in uniform hypergraphs
- On colourings of hypergraphs without monochromatic Fano planes
- On intersecting families of finite sets
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Stability for \(t\)-intersecting families of permutations
- THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
- The Erdős-Ko-Rado theorem for vector spaces
- The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
- The complete nontrivial-intersection theorem for systems of finite sets
- The exact bound in the Erdős-Ko-Rado theorem
- The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
Cited in
(14)- Maximum number of triangle-free edge colourings with five and six colours
- Coloring cross-intersecting families
- Integer colorings with no rainbow \(k\)-term arithmetic progression
- Erdős-Ko-Rado and Hilton-Milner theorems for two-forms
- Remarks on an edge-coloring problem
- A coloring problem for intersecting vector spaces
- Colouring set families without monochromatic \(k\)-chains
- Rainbow Erdös-Rothschild problem for the Fano plane
- scientific article; zbMATH DE number 2140323 (Why is no real title available?)
- Coloring Ordered Sets to Avoid Monochromatic Maximal Chains
- Integer colorings with forbidden rainbow sums
- scientific article; zbMATH DE number 6750761 (Why is no real title available?)
- On the maximum number of integer colourings with forbidden monochromatic sums
- Multicoloured extremal problems
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)
