✦ LIBER ✦

On set intersection representations of graphs

✍ Scribed by Stasys Jukna

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 193 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20367

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The intersection dimension of a bipartite graph with respect to a type L is the smallest number t for which it is possible to assign sets A~x~⊆{1, …, t} of labels to vertices x so that any two vertices x and y from different parts are adjacent if and only if |A~x~∩A~y~|∈L. The weight of such a representation is the sum Σ~x~|A~x~| over all vertices x. We exhibit explicit bipartite n × n graphs whose intersection dimension is (i) at least n^1^/|L| with respect to any type L, (ii) at least $\sqrt{n}$ with respect to any type of the form L={k, k+ 1, …}, and (iii) at least n^1^/|R| with respect to any type of the form L={k|k modp∈R}, where p is a prime number. We also show that any intersection representation of a Hadamard graph must have weight about n lnn/ln lnn, independent on the used type L. Finally, we formulate several problems about intersection dimensions of graphs related to some basic open problems in the complexity of boolean functions. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 55‐75, 2009

📜 SIMILAR VOLUMES

Set intersection representations for alm

Set intersection representations for almost all graphs

✍ Eaton, Nancy; Grable, David A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if &(G) is defined to be the minimum number of labels with which G may be repre

Simultaneous intersection representation

Simultaneous intersection representation of pairs of graphs

✍ Tanenbaum, Paul J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 2 views

We characterize the pairs (G 1 , G 2 ) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G 1 is the intersection graph of the subsets and G 2 is the intersection graph of their complements. We also cons

Intersection Representation of Complete

Intersection Representation of Complete Unbalanced Bipartite Graphs

✍ Nancy Eaton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A p-intersection representation of a graph G is a map, f, that assigns each vertex a subset of [1, 2, ..., t] The symbol % p (G) denotes this minimum t such that a p-intersection representation of G exists. In 1966 Erdo s, Goodman, and Po sa showed that for all graphs G on 2n vertices, % 1 (G) % 1

Intersections of graphs

✍ Béla Bollobás; Alex Scott 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB

Let G and H be two graphs of order n. If we place copies of G and H on a common vertex set, how much or little can they be made to overlap? The aim of this article is to provide some answers to this question, and to pose a number of related problems. Along the way, we solve a conjecture of Erd" os,

General results on tolerance intersectio

General results on tolerance intersection graphs

✍ M. S. Jacobson; F. R. McMorris; E. R. Scheinerman 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB 👁 1 views

## Abstract In this paper, general results are presented that are related to ϕ‐tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ϕ‐tolerance intersection graphs for all ϕ, yet for “nice” ϕ, almost no graphs are ϕ‐toleran

On planar intersection graphs with forbi

On planar intersection graphs with forbidden subgraphs

✍ János Pach; Micha Sharir 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent