TY - JOUR
T1 - Minimum difference representations of graphs
AU - Balogh, József
AU - Prince, Noah
N1 - Funding Information:
Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Research Board 06139 and 07048, and OTKA 049398. Research supported in part by UIUC Campus Research Board 07048.
PY - 2010/2
Y1 - 2010/2
N2 - Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets {S(v): v ∈ V(G)} such that u and v are adjacent in G if and only if min{{pipe}S(u)-S(v){pipe}, {pipe}S(v)-S(u){pipe}} ≥ k. Define ρmin(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρmin(G)} is unbounded. In particular, we prove that for every k there is an n0 such that for n > n0 'almost all' graphs of order n satisfy ρmin(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.
AB - Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets {S(v): v ∈ V(G)} such that u and v are adjacent in G if and only if min{{pipe}S(u)-S(v){pipe}, {pipe}S(v)-S(u){pipe}} ≥ k. Define ρmin(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρmin(G)} is unbounded. In particular, we prove that for every k there is an n0 such that for n > n0 'almost all' graphs of order n satisfy ρmin(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.
KW - Graph representation
KW - Random graphs
KW - Trace of hypergraphs
UR - http://www.scopus.com/inward/record.url?scp=77949425196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77949425196&partnerID=8YFLogxK
U2 - 10.1007/s00373-010-0875-3
DO - 10.1007/s00373-010-0875-3
M3 - Article
AN - SCOPUS:77949425196
VL - 25
SP - 647
EP - 655
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
SN - 0911-0119
IS - 5
ER -