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 -