Minimum difference representations of graphs

Ida Kantor
Charles University, Prague

Zoltan Furedi
Renyi Institute of Mathematics, Hungarian Academy of Sciences



Content: In this talk, we want to represent the vertices of a graph with finite sets in such a way that two vertices are adjacent if and only if their sets are ``very different" (this is similar, e.g., to the notion of Kneser graphs). More precisely, a {\em $k$-min-difference representation} of $G$ is an assignment of a set $A_i$ to each vertex $i\in V(G)$ so that \[ ij\in E(G) \Leftrightarrow \min \{|A_i\setminus A_j|,|A_j\setminus A_i| \}\geq k. \] The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $\rho_{\min}(G)$. After Boros, Gurvitch and Meshulam introduced this notion in 2004, it was not even known whether there are any graphs with $\rho_{\min}(G)\geq 3$. Balogh and Prince proved in 2009 that is indeed so: for every $k$ there is a graph $G$ with $\rho_{\min}(G)\geq k$ (in fact they proved more---for every $k$ there is an $n_0$ such that whenever $n>n_0$, then for a graph $G$ on $n$ vertices we have $\rho_{\min}(G)\geq k$ with high probability). However, they used a Ramsey-type result in their proof, and as a consequence the resulting bounds are weak. We improved this, using a different method. The main result of this talk is that there is a constant $c>0$ such that if $n$ is large enough, there is a bipartite graph $G$ on $n$ vertices such that $\rho_{\min}(G)\geq \frac{cn}{\log n}$.

Back to all abstracts