### Abstract

Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. 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 describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values.

Original language | English (US) |
---|---|

Title of host publication | 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 1477-1481 |

Number of pages | 5 |

ISBN (Electronic) | 9781538692912 |

DOIs | |

State | Published - Jul 2019 |

Event | 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: Jul 7 2019 → Jul 12 2019 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2019-July |

ISSN (Print) | 2157-8095 |

### Conference

Conference | 2019 IEEE International Symposium on Information Theory, ISIT 2019 |
---|---|

Country | France |

City | Paris |

Period | 7/7/19 → 7/12/19 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

### Cite this

*2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings*(pp. 1477-1481). [8849253] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849253