All Questions

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...

While trying to characterize constraint satisfaction problems which can be solved by the Linear Programming relaxation, I've run into a few perplexing puzzles related to the existence of certain ...

Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...

Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...

Consider for $n\in\mathbb{N}, n\geq 6$ the discrete triangle $\nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}$. This is basically the lower "half" of a chess board if you cut it along ...