A bipartite version of the Erdős--McKay conjecture

Eoin Long; Ioan Laurentiu Ploscaru

doi:10.1017/S0963548322000347

A bipartite version of the Erdős--McKay conjecture

Eoin Long, Ioan Laurentiu Ploscaru

Mathematics

Research output: Contribution to journal › Article › peer-review

73 Downloads (Pure)

Abstract

An old conjecture of Erdős and McKay states that if all homogeneous sets in an nvertex graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n²)}. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an n×n bipartite graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n²)}.

Original language	English
Pages (from-to)	1-13
Journal	Combinatorics, Probability and Computing
Early online date	9 Dec 2022
DOIs	https://doi.org/10.1017/S0963548322000347
Publication status	E-pub ahead of print - 9 Dec 2022

Keywords

Ramsey theory
homogeneous sets
edge sizes
probabilistic combinatorics

Access to Document

10.1017/S0963548322000347Licence: Creative Commons: Attribution-NonCommercial-ShareAlike (CC BY-NC-SA)

LongE2022ABipartiteFinal published version, 359 KBLicence: Creative Commons: Attribution-NonCommercial-ShareAlike (CC BY-NC-SA)

Cite this

@article{1a5107a0abf34fd7b7aba13cfd2c5fe2,

title = "A bipartite version of the Erd{\H o}s--McKay conjecture",

abstract = "An old conjecture of Erd{\H o}s and McKay states that if all homogeneous sets in an nvertex graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n2)}. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an n×n bipartite graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n2)}. ",

keywords = "Ramsey theory, homogeneous sets, edge sizes, probabilistic combinatorics",

author = "Eoin Long and Ploscaru, {Ioan Laurentiu}",

year = "2022",

month = dec,

day = "9",

doi = "10.1017/S0963548322000347",

language = "English",

pages = "1--13",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - A bipartite version of the Erdős--McKay conjecture

AU - Long, Eoin

AU - Ploscaru, Ioan Laurentiu

PY - 2022/12/9

Y1 - 2022/12/9

N2 - An old conjecture of Erdős and McKay states that if all homogeneous sets in an nvertex graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n2)}. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an n×n bipartite graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n2)}.

AB - An old conjecture of Erdős and McKay states that if all homogeneous sets in an nvertex graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n2)}. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an n×n bipartite graph are of order O(log n) then the graph contains induced subgraphs of each size from {0, 1, . . . , Ω(n2)}.

KW - Ramsey theory

KW - homogeneous sets

KW - edge sizes

KW - probabilistic combinatorics

U2 - 10.1017/S0963548322000347

DO - 10.1017/S0963548322000347

M3 - Article

SN - 0963-5483

SP - 1

EP - 13

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -

A bipartite version of the Erdős--McKay conjecture

Abstract

Keywords

Access to Document

Fingerprint

Cite this