Edge inducibility via local directed graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916975009071104 |
|---|---|
| author | Chao, Ting-Wei Antonir, Asaf Cohen Li, Anqi Yu, Hung-Hsun Hans |
| author_facet | Chao, Ting-Wei Antonir, Asaf Cohen Li, Anqi Yu, Hung-Hsun Hans |
| contents | In this paper we introduce the edge inducibility problem. This is a common refinement of both the well known Kruskal--Katona theorem and the inducibility question introduced by Pippenger and Golumbic.
Our first result is a hardness result. It shows that for any graph $G$, there is a related graph $G'$ whose edge inducibility determines the vertex inducibility of $G$. Moreover, we determine the edge inducibility of every $G$ with at most $4$ vertices, and make some progress on the cases $G=C_5,P_6$. Lastly, we extend our hardness result to graphs with a perfect matching that is the unique fractional perfect matching. This is done by introducing locally directed graphs, which are natural generalizations of directed graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24064 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Edge inducibility via local directed graphs Chao, Ting-Wei Antonir, Asaf Cohen Li, Anqi Yu, Hung-Hsun Hans Combinatorics Information Theory In this paper we introduce the edge inducibility problem. This is a common refinement of both the well known Kruskal--Katona theorem and the inducibility question introduced by Pippenger and Golumbic. Our first result is a hardness result. It shows that for any graph $G$, there is a related graph $G'$ whose edge inducibility determines the vertex inducibility of $G$. Moreover, we determine the edge inducibility of every $G$ with at most $4$ vertices, and make some progress on the cases $G=C_5,P_6$. Lastly, we extend our hardness result to graphs with a perfect matching that is the unique fractional perfect matching. This is done by introducing locally directed graphs, which are natural generalizations of directed graphs. |
| title | Edge inducibility via local directed graphs |
| topic | Combinatorics Information Theory |
| url | https://arxiv.org/abs/2509.24064 |