TY - JOUR

T1 - Directed Intersection Representations and the Information Content of Digraphs

AU - Liu, Xujun

AU - Machado, Roberto Assis

AU - Milenkovic, Olgica

N1 - Funding Information:
The work was supported in part by the NSF STC Center for Science of Information under Grant 4101-38050, in part by the Sao Paulo Research Foundation under Grant 2015/11286-8 and Grant NSF CCF 15-26875, and in part by the UIUC Research Board under Grant RB17164.
Funding Information:
Manuscript received July 20, 2019; revised May 22, 2020; accepted September 2, 2020. Date of publication October 22, 2020; date of current version December 21, 2020. The work was supported in part by the NSF STC Center for Science of Information under Grant 4101-38050, in part by the São Paulo Research Foundation under Grant 2015/11286-8 and Grant NSF CCF 15-26875, and in part by the UIUC Research Board under Grant RB17164. This article was presented at the 2019 International Symposium on Information Theory (ISIT). (Corresponding author: Xujun Liu.) Xujun Liu is with the Department of Mathematics, University of Illinois at Urbana–Champaign, Champaign, IL 61801-3028 USA (e-mail: xliu150@illinois.edu).

PY - 2021/1

Y1 - 2021/1

N2 - Consider a directed graph (digraph) in which vertices are assigned color sets, and two vertices are connected if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head. We seek to determine the smallest possible size of the union of the color sets that allows for such a digraph representation. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to introduce the directed intersection number (DIN), the smallest number of colors needed to represent a DAG. Our main results are upper bounds on the DIN of DAGs based on what we call the longest terminal path decomposition of the vertex set, and constructive lower bounds.

AB - Consider a directed graph (digraph) in which vertices are assigned color sets, and two vertices are connected if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head. We seek to determine the smallest possible size of the union of the color sets that allows for such a digraph representation. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to introduce the directed intersection number (DIN), the smallest number of colors needed to represent a DAG. Our main results are upper bounds on the DIN of DAGs based on what we call the longest terminal path decomposition of the vertex set, and constructive lower bounds.

KW - Directed intersection number

KW - directed acyclic graph

KW - intersection representation

UR - http://www.scopus.com/inward/record.url?scp=85098555243&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098555243&partnerID=8YFLogxK

U2 - 10.1109/TIT.2020.3033168

DO - 10.1109/TIT.2020.3033168

M3 - Article

AN - SCOPUS:85098555243

VL - 67

SP - 347

EP - 357

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

M1 - 9236641

ER -