A Bollobás-Type Problem: From Root Systems to Erdős–Ko–Rado

Patrick J. Browne; Qëndrim R. Gashi; Padraig Catháin

doi:10.48550/arXiv.2404.04867

A Bollobás-Type Problem: From Root Systems to Erdős–Ko–Rado

Patrick J. Browne, Qëndrim R. Gashi, Padraig Catháin

Department of Electrical and Electronic Engineering

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

Abstract

Motivated by an Erdős–Ko–Rado-type problem on sets of strongly orthogonal roots in the A_ℓ root system, we estimate bounds for the size of a family of pairs (A_i,B_i) of k-subsets in {1,2,…,n}, such that A_i∩B_j=∅ and |A_i∩A_j|+|B_i∩B_j|=k for all i≠j. This is reminiscent of a classic problem of Bollobás. We provide upper and lower bounds for this problem, relying on classical results of extremal combinatorics and an explicit construction using the incidence matrix of a symmetric design.

Original language	English
Number of pages	7
Journal	Annals of Combinatorics
Early online date	25 Sep 2024
DOIs	https://doi.org/10.48550/arXiv.2404.04867 https://doi.org/10.1007/s00026-024-00717-y
Publication status	Published - 2024

Keywords

05D05
17B22
Erdős–Ko–Rado
Root system
Strongly orthogonal roots

Access to Document

Cite this

@article{ef9ea8911b4f4db29c9442177e3dc288,

title = "A Bollob{\'a}s-Type Problem: From Root Systems to Erd{\H o}s–Ko–Rado",

abstract = "Motivated by an Erd{\H o}s–Ko–Rado-type problem on sets of strongly orthogonal roots in the Aℓ root system, we estimate bounds for the size of a family of pairs (Ai,Bi) of k-subsets in {1,2,…,n}, such that Ai∩Bj=∅ and |Ai∩Aj|+|Bi∩Bj|=k for all i≠j. This is reminiscent of a classic problem of Bollob{\'a}s. We provide upper and lower bounds for this problem, relying on classical results of extremal combinatorics and an explicit construction using the incidence matrix of a symmetric design.",

keywords = "05D05, 17B22, Erd{\H o}s–Ko–Rado, Root system, Strongly orthogonal roots",

author = "Browne, {Patrick J.} and Gashi, {Q{\"e}ndrim R.} and Padraig Cath{\'a}in",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer Nature Switzerland AG 2024.",

year = "2024",

doi = "10.48550/arXiv.2404.04867",

language = "English",

journal = "Annals of Combinatorics",

issn = "0218-0006",

publisher = "Birkhauser Verlag Basel",

}

TY - JOUR

T1 - A Bollobás-Type Problem

T2 - From Root Systems to Erdős–Ko–Rado

AU - Browne, Patrick J.

AU - Gashi, Qëndrim R.

AU - Catháin, Padraig

N1 - Publisher Copyright: © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - Motivated by an Erdős–Ko–Rado-type problem on sets of strongly orthogonal roots in the Aℓ root system, we estimate bounds for the size of a family of pairs (Ai,Bi) of k-subsets in {1,2,…,n}, such that Ai∩Bj=∅ and |Ai∩Aj|+|Bi∩Bj|=k for all i≠j. This is reminiscent of a classic problem of Bollobás. We provide upper and lower bounds for this problem, relying on classical results of extremal combinatorics and an explicit construction using the incidence matrix of a symmetric design.

AB - Motivated by an Erdős–Ko–Rado-type problem on sets of strongly orthogonal roots in the Aℓ root system, we estimate bounds for the size of a family of pairs (Ai,Bi) of k-subsets in {1,2,…,n}, such that Ai∩Bj=∅ and |Ai∩Aj|+|Bi∩Bj|=k for all i≠j. This is reminiscent of a classic problem of Bollobás. We provide upper and lower bounds for this problem, relying on classical results of extremal combinatorics and an explicit construction using the incidence matrix of a symmetric design.

KW - 05D05

KW - 17B22

KW - Erdős–Ko–Rado

KW - Root system

KW - Strongly orthogonal roots

UR - http://www.scopus.com/inward/record.url?scp=85204803189&partnerID=8YFLogxK

U2 - 10.48550/arXiv.2404.04867

DO - 10.48550/arXiv.2404.04867

M3 - Article

SN - 0218-0006

JO - Annals of Combinatorics

JF - Annals of Combinatorics

ER -

A Bollobás-Type Problem: From Root Systems to Erdős–Ko–Rado

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this