Clique number of Xor products of Kneser graphs

DOI10.1016/J.DISC.2022.112886MaRDI QIDQ2138983zbMATH OpenOpenAlexFDO

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

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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$.

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

Cites work

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

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)