Kneser ranks of random graphs and minimum difference representations

DOI10.1137/17M1114703zbMATH Open1387.05237arXiv1701.08292OpenAlexW2583794152WikidataQ129868200 ScholiaQ129868200MaRDI QIDQ4641757FDOQ4641757

Authors: Ida Kantor, Zoltán Füredi 

Publication date: 18 May 2018

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

Abstract: Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $vmapsto{A}_v$ to the vertices $vinV$ such that $A_u$ and $A_v$ are disjoint if and only if $uvinE$. The smallest such $k$ is called the Kneser rank of $G$ and denoted by $f_{mKneser}(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0<p<1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$ such that with high probability [ c_1 n/(log n)< f_{ m Kneser}(G) < c_2 n/(log n). ] We apply this for other graph representations defined by Boros, Gurvich and Meshulam. A {em $k$-min-difference representation} of a graph $G$ is an assignment of a set $A_i$ to each vertex $iinV(G)$ such that [ ijin E(G) ,, Leftrightarrow , , min {|A_isetminus A_j|,|A_jsetminus A_i| }geq k. ] The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{min}(G)geqk$. We prove that there are constants $c^{\prime }{\text{'}}_1,c^{\prime }{\text{'}}_2>0$ such that $c^{\prime }{\text{'}}_{1}n/(logn)<f_{min}(G)<c^{\prime }{\text{'}}_{2}n/(logn)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.

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

Recommendations

• Kneser ranks of random graphs and minimum difference representations
• Minimum difference representations of graphs
• On random subgraphs of Kneser and Schrijver graphs
• Kneser representations of graphs
• Sharp bounds for the chromatic number of random Kneser graphs

zbMATH Keywords

intersection graphsrandom graphsKneser graphsclique covers

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Topics in Intersection Graph Theory
• Title not available (Why is that?)
• The probabilistic method
• Graphs of small dimensions
• On a product dimension of graphs
• Unavoidable traces of set systems
• The Representation of a Graph by Set Intersections
• Kneser representations of graphs
• Covering the edges of a random graph by cliques
• Competition graphs and clique dimensions
• The \(p\)-intersection number of a complete bipartite graph and orthogonal double coverings of a clique
• Minimum difference representations of graphs
• Difference graphs
• Title not available (Why is that?)
• Compact representations of the intersection structure of families of finite sets

Cited In (4)

• Kneser ranks of random graphs and minimum difference representations
• Note on strong product graph dimension
• The Minrank of Random Graphs
• Expected values of parameters associated with the minimum rank of a graph

This page was built for publication: Kneser ranks of random graphs and minimum difference representations

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