kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Clique number of xor-powers of Kneser graphs
Alfréd Rényi Institute for Mathematics, Reáltanoda u. 13–15, H-1364 Budapest, Hungary.
Eötvös Loránd University, H-1117 Budapest, Pázmány Péter sétány 1/C, Hungary.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Algebra, Combinatorics and Topology.ORCID iD: 0000-0001-8328-4667
2026 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 33, no 2, article id P2.47Article in journal (Refereed) Published
Abstract [en]

Let fℓ (n, k) denote the clique number of the xor-product of ℓ isomorphic Kneser graphs KG(n, k). Alon and Lubetzky investigated the case of complete graphs as a coding theory problem and showed fℓ (n, 1) ⩽ℓn+1. Imolay, Kocsis, and Schweitzer proved that f2 (n, k) ⩽⌊ ⌋ n k+c(k). ( Here, the order of magnitude of c(k) is determined to be Θ k( ))2k k . By explicit constructions and by an algebraic proof, it is shown that ℓn − 2ℓ − 1 ⩽ fℓ (n, 1) ⩽ℓn − ℓ + 1 (for all n ⩾ 1 and ℓ ⩾ 3). Finally, it is proved that the order of magnitude of f lies between Ω( n⌊log (ℓ+1)⌋)2 and O (n⌊ ℓ+1 2 ⌋) (as ℓ, k are given and n → ∞). We conjecture that the lower bound gives the correct exponent.

Place, publisher, year, edition, pages
The Electronic Journal of Combinatorics , 2026. Vol. 33, no 2, article id P2.47
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-383913DOI: 10.37236/14969ISI: 001787937500001Scopus ID: 2-s2.0-105041050836OAI: oai:DiVA.org:kth-383913DiVA, id: diva2:2084987
Note

QC 20260707

Available from: 2026-07-07 Created: 2026-07-07 Last updated: 2026-07-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Schweitzer, Ádám

Search in DiVA

By author/editor
Schweitzer, Ádám
By organisation
Algebra, Combinatorics and Topology
In the same journal
The Electronic Journal of Combinatorics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf