Clique number of Xor products of Kneser graphs

DOI10.1016/J.DISC.2022.112886zbMATH Open1489.05151arXiv2104.13505OpenAlexW3158912403MaRDI QIDQ2138983FDOQ2138983

Authors: András Imolay, Anett Kocsis, Ádám Schweitzer 

Publication date: 17 May 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in "A general 2-part ErdH{o}s-Ko-Rado theorem" by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic $KG(N,k)$ Kneser graphs. Denote this number with $f(k,N)$. We give lower and upper bounds on $f(k,N)$, and we solve the problem up to a constant deviation depending only on $k$, and find the exact value for $f(2,N)$ if $N$ is large enough. We also compute that $f(k,k^2)$ is asymptotically equivalent to $k^2$.

Full work available at URL: https://arxiv.org/abs/2104.13505

Recommendations

• Extremal problems concerning Kneser-graphs
• Codes and Xor graph products
• Independence number of products of Kneser graphs
• A note on induced cycles in Kneser graphs
• On the chromatic number of the general Kneser-graph

zbMATH Keywords

extremal set theoryintersecting familiesXor product

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Extremal set theory (05D05)

Cites Work

• On the diameter of Kneser graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Mutually orthogonal Latin squares: A brief survey of constructions
• Kneser's conjecture, chromatic number, and homotopy
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Almost Intersecting Families of Sets
• Intersecting families of discrete structures are typically trivial
• Two-part set systems
• Graph products and monochromatic multiplicities
• Independence number of products of Kneser graphs
• Results on intersecting families of subsets, a survey
• Codes and Xor graph products

Cited In (1)

• Codes and Xor graph products

This page was built for publication: Clique number of Xor products of Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138983)