CS Paper Radar

Prescribed and simultaneous failures of log-concavity in trees with perfect matchings

Heshun Fan

cs.LO math.CO ·submitted 2026-10-13 13:12 UTC · v1
code/data

Abstract

We construct trees with perfect matchings and independence sequences that fail log-concavity near the independence number $α$. For every integer $k\geq1$, one family fails at $α-k$ and has a witness of order $O(k^2\log(k+2))$. For every integer $t\geq2$, a single tree has simultaneous failures at $α-1,α-3,\ldots,α-(2t-1)$, with a witness of order $O(t^3)$. All these trees satisfy $α=N/2$, where $N$ is the number of vertices, and contradict Conjecture 4.2 of Ramos and Sun. A sufficient condition uses a fixed tree and the numbers of attached leaves. For fixed $k$ or $t$, explicit bounds give geometric decay of $a_j^2/(a_{j-1}a_{j+1})$ at these indices as the trees grow; $a_j$ counts independent $j$-sets. The proofs count independent sets by empty matching pairs. The Lean proof assistant checks formal proofs of the parameterized results and their quantitative bounds; exact 90- and 180-vertex examples illustrate the constructions.

Comment
21 pages, 1 figure. Lean formalization included as ancillary files. Code available at: https://github.com/HUSTFRED/Math_open_problems

Closest papers

Nearest neighbours by meaning across the whole index.

Counting Paths and Trees via Exterior Algebra

cs.DS ·2026-09-13 ·Fahad Panolan, Saket Saurabh, Meirav Zehavi, Jie Xue
similarity 0.69
Abstract · Counting k-paths, Counting k-trees, Exterior Algebra

We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host vertices and edges or arcs, ε is the relative error, and δ is the failure probability. Our main results are: 1. Paths: We approximate the number of directed paths on $k$ vertices in $2^k k^{O(1)}(n+m)\varepsilon^{-2}\log(2/δ)$ arithmetic operations. 2. Trees and forests: For every fixed $η>0$, we approximate the number of non-induced copies of a given forest on $k$ vertices in $(2+η)^k n^{O_η(1)}\varepsilon^{-2}\log(2/δ)$ arithmetic operations. Our path algorithm resolves a conjecture of Koutis and Williams~[CACM 2016] and answers an open question of Lokshtanov, Saurabh, and Zehavi~[SODA 2021] by giving a $2^k poly(n,\varepsilon^{-1})$-time approximation scheme. Our algorithms combine exterior algebra with random matrix estimators, using the tensor-train moment bound of Rakhshan and Rabusseau~[AISTATS 2020]. For forests, we use a small-component separator to evaluate the estimator efficiently.

0.04

Barrier Log-Concavity of Large Forests

cs.DM math.COmath.PR ·2026-10-15 ·Vadim E. Levit
theory similarity 0.69
Abstract · 26 pages, 2 figures; optional 16-page quantitative supplement and verification code/data in ancillary files

We prove that the independence sequence of every sufficiently large forest is strictly barrier log-concave: whenever $i_{k+1}>i_k$, one has $i_k^2>i_{k-1}i_{k+1}$. Consequently, every common downward coefficient tilt is unimodal, with one order threshold valid simultaneously for all $0<t\le1$. As an application, we prove that every sufficiently large well-covered tree has a strictly log-concave independence polynomial. More generally, the latter conclusion holds for well-covered forests with sufficiently large matching number. Every sufficiently large forest with a palindromic independence polynomial is also strictly log-concave, with its modes at the central ranks. The proof establishes local coefficient-curvature estimates uniformly over forests of unbounded maximum degree and over activities tending to zero. Combined with the fixed-density theorem of Fang, Lu, Nevo, Yao, and Zheng, these estimates complete the strict log-concavity interval down to rank one through $\lfloor17α/25\rfloor$; the terminal fraction is inherited. The classical decreasing tail then yields the barrier property. A cumulative-coefficient corona theorem transfers barrier log-concavity of the base forest to full strict log-concavity of its leaf corona.

0.50

On (Pathwidth, Clique)-boundedness

cs.DM math.CO ·2026-11-17 ·Amir Nikabadi
theory similarity 0.66
Abstract

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

0.07

Induced Forest Minor Theorem for Graphs Without an Induced Star

cs.DM math.CO ·2026-09-09 ·Robert Hickingbotham, Gwenaël Joret
theory similarity 0.64
Abstract

Motivated by recent work on tree independence number, we study the path independence number of a graph $G$: the minimum integer $k$ such that there is a path decomposition of $G$ where each bag induces a graph with independence number at most $k$. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milani{č}, Munaro, Štorgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest $H$ and integer $t$, there is a polynomial-time algorithm to test whether a $K_{1,t}$-induced-subgraph-free graph contains $H$ as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on $K_{1,t}$-induced-subgraph-free graphs that exclude $H$ as an induced minor.

0.34

Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using $\tilde{O}(n^{2/3})$ space

cs.DS ·2026-09-16 ·Andrew McGregor
similarity 0.64
Abstract

The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $α$. The algorithm uses $O(\varepsilon^{-4/3}α^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $α$ and $\varepsilon$, this improves the best known previous space bound from $O(n^{4/5} \text{polylog} n)$ to $O(n^{2/3} \text{polylog} n)$. The algorithm is a linear sketch and requires no bounds on the number of deletions or on the arboricity of intermediate graphs.

0.24

Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth

cs.DS cs.DM ·2026-11-02 ·Noy Rotbart
similarity 0.63
Abstract · 23 pages, 9 figures

Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size $\log n+O(k\log\log n)$ for graphs of treewidth at most $k$, and asked whether $\log n+O(k)$ bits suffice. We give a labeling scheme of size $\log n+O(\log\log^* n)$ for every fixed $k$, the first improvement of the second-order term for any $k\ge 2$. Equivalently, there is an induced-universal graph with $n(\log^* n)^{O_k(1)}$ vertices for this family. We work with laminar families of intervals, in which a vertex finds each earlier neighbor as the owner of an interval of a given nesting depth around it. As long as every subtree occupies consecutive positions, the nesting depth must be logarithmic, and $\log\log n$ bits per neighbor follow. We give up contiguity. Heavy subtrees are moved out, which brings the depth down to $O(\log^* n)$; the intervals broken by the moves are repaired with $2^{O(k^3)}$ additional intervals per vertex; and the bits needed to find these intervals are paid for by the moved subtrees.

0.30

Logarithmic edge-length ratios for planar drawings of 2-trees

cs.CG math.CO ·2026-10-20 ·Zahra Sabaei, Fatemeh Emami, Yasmin Tousinejad
theory similarity 0.62
Abstract · minor corrections; author metadata corrected to match the transcript

For a planar graph $G$ with at least one edge, let $ρ(G)$ be the infimum of the ratio of the longest to the shortest edge length over all planar straight-line drawings of $G$. We prove that every $n$-vertex $2$-tree $G$ satisfies $ρ(G)\le4+5\lfloor\log_2(2n-3)\rfloor$. This improves the known $O(\sqrt n)$ upper bound and, together with the lower bound of Blažej, Fiala and Liotta, shows that the maximum of $ρ(G)$ over $n$-vertex $2$-trees is $Θ(\log n)$. The proof adapts Biedl's recursive bar construction using nonintegral heights and applies a height-preserving straightening theorem.

0.16

The Tight Competitive Ratio of Greedy for Online Steiner Forest

cs.DS ·2026-10-29 ·Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade
theory similarity 0.62
Abstract

The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges connecting each pair. The natural greedy algorithm connects each terminal pair by a shortest path after making all previously purchased edges free. Awerbuch, Azar, and Bartal (SODA 1996) proved that this algorithm is $O(log^2 k)$-competitive and conjectured an $O(log k)$ bound, where $k$ is the number of terminal pairs. Bamas, Drygala, and Maggiori (SODA 2022) obtained an $O(\log \NumPairs\log\log \NumPairs)$ bound for greedy on a restricted class of inputs, leaving the general case open. In this paper, we resolve the competitive ratio of the greedy algorithm for online Steiner Forest, proving that it is tightly $Θ(log(k) log log(k))$. Specifically, we establish an $O(log(k) log log(k))$ upper bound for arbitrary instances and construct a matching $Ω(log(k) log log(k))$ lower bound. Our results refute the $O(log k)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight $Θ(log log k)$ separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.

0.23