Pith. sign in

REVIEW 1 cited by

Antidirected trees in dense digraphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2404.10750 v3 pith:QRK2UIYU submitted 2024-04-16 math.CO

classification math.CO
keywords digraphsantidirectedarcseveryclassconjecturecontainsdigraph
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We show that if $D$ is an $n$-vertex digraph with more than $(k-1)n$ arcs that does not contain any of three forbidden digraphs, then $D$ contains every antidirected tree on $k$ arcs. The forbidden digraphs are those orientations of $K_{2, \lceil k/12\rceil}$ where each of the vertices in the class of size two has either out-degree $0$ or in-degree $0$. This proves a conjecture of Addario-Berry et al. for a broad class of digraphs, and generalises a result for $K_{2, \lfloor k/12\rfloor}$-free graphs by Balasubramanian and Dobson. We also show that every digraph $D$ on $n$ vertices with more than $(k-1)n$ arcs contains every antidirected $k$-arc caterpillar, thus solving the above conjecture for caterpillars. This generalises a result of Perles.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Oriented Trees in Digraphs without Oriented $4$-cycles

    math.CO 2024-11 conditional novelty 6.0 of 10

    If a digraph has no oriented 4-cycles, minimum semidegree at least k/2, and at least one vertex with outdegree and indegree at least k, then it contains every oriented tree with k arcs.

Pith tools