We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A bipartite version of the Erdős–McKay conjecture.
- Authors
Long, Eoin; Ploscaru, Laurenţiu
- Abstract
An old conjecture of Erdős and McKay states that if all homogeneous sets in an $n$ -vertex graph are of order $O(\!\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an $n \times n$ bipartite graph are of order $O(\!\log n)$ , then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$.
- Subjects
BIPARTITE graphs; LOGICAL prediction; RAMSEY theory; SUBGRAPHS
- Publication
Combinatorics, Probability & Computing, 2023, Vol 32, Issue 3, p465
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548322000347