PaperlayerView exact revision on arXiv

Source-linked AI summary

Note on near-spanning balanced antidirected trees missing from regular tournaments

Gregory Gutin, Yiming Hao

arXiv:2610.02390v1math.COcs.DM

TL;DR

Uniform semidegree and pseudo-semidegree assertions concern whether the thresholds suffice across target trees, rather than only for a prescribed degree bound. We construct regular vertex-transitive tournaments and near-spanning balanced antidirected caterpillars; for every sufficiently large odd n, the target has n−1 vertices and is not contained in its host.

  • Problem

    The uniform assertions ask whether the semidegree and pseudo-semidegree thresholds suffice beyond a single prescribed degree bound.

    Source: §1 · p. 2

  • Method

    For every sufficiently large odd n, we construct a regular vertex-transitive tournament and a balanced antidirected caterpillar target.

    Source: §1 · p. 2

  • Results

    For every sufficiently large odd n, the balanced antidirected caterpillar has n−1 vertices and is not contained in the regular vertex-transitive tournament.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The n−1-vertex target order is best possible under the strict semidegree hypothesis, and the examples address uniform assertions rather than weaker formulations.

    Source: §1 · p. 2

    The construction does not settle the corresponding assertions for growing targets with bounded or polylogarithmic maximum degree in full generality.

    Source: §3 · p. 6

Abstract

from arXiv · show

We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precisely, for every sufficiently large odd integer $n$, we exhibit a regular vertex-transitive tournament on $n$ vertices and a balanced antidirected caterpillar on $n-1$ vertices with maximum degree at most $(1+o(1))n/\log_2 n$ that is not contained in the tournament. The host satisfies the strict $k/2$ threshold in both the semidegree and pseudo-semidegree settings, where $k$ is the number of arcs of the target tree. Consequently, this gives counterexamples to the uniform sublinear-degree interpretations of Conjectures~6.8 and~7.6 in Stein's survey (2024). The order $n-1$ of the target is best possible under the strict semidegree hypothesis. We also give a six-vertex balanced antidirected double-star missing from the seven-vertex Paley tournament, and show that seven is the smallest host order for a pseudo-semidegree counterexample with this fixed double-star.

1 Introduction

The introduction gives near-spanning balanced antidirected trees that evade regular vertex-transitive tournaments, challenging uniform sublinear-degree versions of the k/2 embedding conjectures. It outlines an extension-property construction and distinguishes these counterexamples from weaker formulations and earlier obstructions.

1 Introduction

  • The examples contradict the uniform sublinear-degree interpretations of the semidegree and pseudo-semidegree k/2 conjectures, but not every weaker formulation.The uniform assertion quantifies over every sublinear degree bound; the authors explicitly leave weaker formulations unaddressed.Source: §1 · pp. 1–2
  • The earlier seven-vertex obstruction yields fixed-target examples in disconnected oriented hosts, whereas Theorem 1 removes both limitations.The introduction also distinguishes prior non-antidirected tree obstructions from the balanced antidirected setting considered here.Source: §1 · pp. 2–3
  • For every sufficiently large odd n, a regular vertex-transitive tournament Dn omits a balanced antidirected caterpillar Tn of order n−1, with Δ(Tn)=o(n).The target can be chosen as a function of n alone.Source: §1 · p. 2
  • The n−1 target order is maximal under the strict semidegree condition, and the construction attains it while keeping maximum degree o(n).For an n-vertex tournament, δ0(D)>(n−2)/2 forces a k-arc tree to have at most n−1 vertices.Source: §1 · p. 2
  • The proof combines an existential-extension host with a balanced caterpillar whose embedded spine leaves no compatible position for a leaf.A spine of order about log2 n distributes the remaining vertices as evenly as possible; the one unused host vertex is included among the prescribed adjacencies.Source: §1 · pp. 2–3

2 A seven-vertex obstruction

The section gives a balanced six-vertex antidirected double-star missing from the seven-vertex Paley tournament despite the strict half-arc threshold, and shows that seven is the smallest host order for this fixed target under the pseudo-semidegree condition.

2 A seven-vertex obstruction

  • The earlier Pal_7 obstruction for antidirected Hamilton paths is unbalanced and meets only equality at the half-arc threshold, unlike this example.The earlier path has seven vertices and six arcs; it is not itself a counterexample to the stated assertions.Source: §2 · pp. 3–4
  • After an automorphism normalizes the central arc to 0→1, the required leaf images collide at vertex 4, ruling out an embedding.The two leaf pairs must map to {2, 4} and {4, 6}, respectively.Source: §2 · p. 4
  • The balanced antidirected double-star S is absent from Pal_7 even though the host satisfies the strict k/2 condition.S has six vertices and five arcs.Source: §2 · pp. 3–4
  • Seven is the smallest order of an oriented graph with pseudo-semidegree greater than 5/2 that avoids S.For hosts of order at most six, the degree condition forces three sources and three sinks with every source adjacent to every sink, yielding S.Source: §2 · p. 4
  • Disjoint unions of Pal_7 give arbitrarily large oriented hosts avoiding S, but they are not tournaments when there is more than one component.These examples keep the target fixed at five arcs and maximum degree three; the main theorem removes both restrictions.Source: §2 · p. 4
  • A bounded maximum-degree condition alone does not repair an embedding assertion that permits a fixed target in arbitrarily large oriented hosts.The example has k = 5 and Δ(S) = 3 throughout; it does not address variants requiring target size to grow.Source: §2 · p. 4

3 Proof of the main theorem

The proof combines existential closure with a leaf obstruction to construct a near-spanning balanced antidirected caterpillar omitted by a regular vertex-transitive tournament. It also identifies limits on what the counterexample establishes about degree bounds.

3 Proof of the main theorem

  • An s-existentially closed tournament omits an n−1-vertex antidirected tree when all vertices outside U are leaves attached to U and |U| + 1 ≤ s.In the proof, the unique unused host vertex is included among prescribed adjacencies, forcing a vertex whose orientation conflicts with every possible leaf position.Source: §3 · pp. 4–5
  • The proof chooses a longest equally balanced alternating source–sink spine allowed by the existential-closure parameter, then distributes leaves evenly on both sides.The resulting tree is a balanced antidirected caterpillar on n−1 vertices with n−2 arcs.Source: §3 · p. 5
  • The construction gives n-vertex tournaments omitting balanced antidirected trees with n−2 arcs and sublinear maximum degree, contradicting the uniform sublinear-degree assertions.The obstruction persists for targets with k_n ≥ ηn for any fixed η in (0, 1).Source: §3 · p. 5
  • Replacing the condition Δ(T) = o(n) with Δ(T) = o(k) alone does not avoid the near-spanning counterexamples.Here k_n/n tends to 1.Source: §3 · p. 5
  • For fixed maximum degree, a cited spanning-tree theorem yields embeddings of near-spanning trees in sufficiently large regular tournaments.The deduction extends to every orientation of the target, but only for fixed degree; it gives no conclusion for a prescribed growing polylogarithmic degree bound.Source: §3 · p. 6
  • The construction does not establish n/log n as an optimal maximum-degree scale; its sharp feature is the one-vertex order deficit.The corresponding assertions for growing targets of bounded or polylogarithmic maximum degree are not addressed in full generality.Source: §3 · p. 6

Statement on AI-assisted research

GPT 6 Astra assisted with literature retrieval, proof verification, and refining the manuscript’s presentation.

Statement on AI-assisted research

Loading 2610.02390v1…