EUVIMEDEUVIMED entdecken
Crossref

Tight paths in fully directed hypergraphs

Richard C. Devine, Kevin G. Milans

Discrete Mathematics · 2027-02 · 350 (2) · 115410

DOI: 10.1016/j.disc.2026.115410 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics, 2027-02. Verfasst von Richard C. Devine und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

It is well-known that every tournament has a spanning path. We consider hypergraph analogues. In an \emph{$r$-uniform fully directed hypergraph}, or \emph{$r$-digraph}, every edge is a list or $r$ distinct vertices. An $(r,k)$-tournament is an $r$-digraph $G$ such that for every $r$-set $S$ of vertices in $G$, exactly $k$ of the orderings of $S$ are edges in $G$. A \emph{directed tight path} is an $r$-digraph $G$ whose vertices can be ordered so that the intervals of size $r$ are the edges in $G$. Let $f(n,r,k)$ be the maximum $s$ such that every $n$-vertex $(r,k)$-tournament contains a tight path on $s$ vertices. Since every tournament has a spanning path, we have $f(n,2,1)=n$. In this paper, we show that the minimum $k$ such that $f(n,r,k)$ tends to infinity with $n$ is in the interval $\left[\left(1-\frac{1}{r}-O(\frac{\log r}{r^2\log\log r})\right)r!, ~\left(1-\frac{1}{r} - \frac{\varphi(r)-1}{r!}\right)r!\right]$ where $\varphi(r)$ is the Euler Totient Function, and we find the exact value when $r\le 5$. We also show that $\Omega(\sqrt{\log n/\log \log n}) \le f(n,3,3) \le O(\log n)$ and $f(n,3,4)\ge \Omega(n^{1/5})$.

Zitieren

APA

Devine, R. C., & Milans, K. G. (2027). Tight paths in fully directed hypergraphs. Discrete Mathematics, 350(2), 115410. https://doi.org/10.1016/j.disc.2026.115410

Vancouver

Devine RC, Milans KG. Tight paths in fully directed hypergraphs. Discrete Mathematics. 2027;350(2):115410. doi:10.1016/j.disc.2026.115410

BibTeX
@article{Devine2027,
  author = {Devine, Richard C. and Milans, Kevin G.},
  title = {Tight paths in fully directed hypergraphs},
  journal = {Discrete Mathematics},
  year = {2027},
  volume = {350},
  number = {2},
  pages = {115410},
  doi = {10.1016/j.disc.2026.115410}
}
Kostenlos starten →