Department of Mathematics - Master Calendar

View Full Calendar

Graph Theory & Combinatorics Seminar

Event Type
Department of Mathematics
Altgeld 241
Mar 7, 2023   1:00 pm  
Zoltán Füredi
Originating Calendar
Events - Department of Mathematics
Zoltán Füredi (Rényi Institute of Mathematics)
The clique number of Xor powers of Kneser graphs
Abstract: A Kneser graph G:=KG(N,k) has an N-element base set A, the vertex set of G consists of the k-element subsets of A, and a pair {U,V} forms an edge of G when its members are disjoint, U\cap V=\emptyset. Given two graphs G=(V(G), E(G)) and H=(V(H), E(H)) their Xor product G \cdot H is a graph with the vertex set V(G) \times V(H) and two vertices (g,h) and (g',h') are connected in  G \cdot H  if and only if:
either gg' is an edge of G and hh' is not an edge of H,
or gg' is not an edge of G and hh' is an edge of H.

The Xor product is not as well understood as other graph products but there are a number of highly nontrivial results about it, e.g., by Alon and Lubetzky~2007 and by Thomason~1997. We investigate the clique number of Xor products of Kneser graphs. We also examine generalizations and propose problems.
This is joint work with A. Imolay and A. Schweitzer.
link for robots only