CS Paper Radar

An asymptotic bound for Yuster's independent transversal factor conjecture

Xin Zhang

cs.DM math.CO ·submitted 2026-11-19 15:32 UTC · v1
theory

Abstract

An $[r,n,1]$-graph has $r$ independent parts of size $n$, with a matching between each pair of parts. Yuster conjectured in 2021 that every such graph has a partition into independent transversals whenever $n\ge 2\lceil r/2\rceil$. We prove that there is an absolute constant $A>0$ such that, for all sufficiently large $r$, this partition exists whenever $n\ge\lceil r+A r^{20/21}\rceil$. Thus $f(r)\le r+O(r^{20/21})$, where $f(r)$ is the least $n_0$ such that every $[r,n,1]$-graph has such a partition whenever $n\ge n_0$. In particular, $f(r)/r\to1$, giving an asymptotic form of the conjecture.

Closest papers

Nearest neighbours by meaning across the whole index.

An $O(k\log(n/k))$ Bound on Spanning Bipartite Connectivity

cs.DM math.CO ·2026-09-20 ·G. Gutin, Y. Hao, Y. Zhou
theory similarity 0.66
Abstract · All proofs were written by the authors without the assistance of AI. However, GPT-6 Astra was used to check the correctness of our proofs, a…

For integers $1\le k\le n/2$, let $f(k,n)$ be the least integer $s$ such that every $s$-connected graph on $n$ vertices contains a spanning bipartite $k$-connected subgraph. Thomassen conjectured that $f(k,n)$ is bounded by a function of $k$ alone. Delcourt and Ferber proved $f(k,n)=O(k^3\log n)$, and Yuster subsequently obtained $f(k,n)\le22k^2\log_2 n$. We prove that, for $2\le k\le n/2$, \[ f(k,n)\le\min\left\{n-1,\, \left\lfloor6(k-1)\log_2\frac{n}{k-1}\right\rfloor\right\}. \] In particular, $f(k,n)=O(k\log(n/k))$.

0.32

Supersaturation and reconfiguration diameter of independent transversals

cs.DM math.CO ·2026-11-16 ·Wouter Cames van Batenburg, Penny Haxell, Ross J. Kang, Ronen Wdowinski
theory similarity 0.63
Abstract · 14 pages, 1 figure

Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree $Δ$. It is a classic result that when all parts have size at least $2Δ$, the collection is nonempty. Recently, it was found that if the parts have size at least $2Δ+1$, then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least $2Δ$, and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least $4Δ$.

0.32

Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

cs.DS math.COmath.LO ·2026-09-20 ·Leonardo N. Coregliano, Fernando G. Jeronimo
similarity 0.62
Abstract · 170 pages, 2 figures, 1 table

In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $\operatorname{Lit}(G)\leq\ell$ has a regular equipartition into excellent sets with $(1 + o_{ε\to 0,\ell}(1))\cdotε^{-\ell-1}$ parts and in the other direction, for every $\ell\in\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose equipartitions into good sets must have size at least $(1 + o_{ε\to 0,\ell}(1))\cdotε^{-\ell-1}$. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative $\log(1/ε)$: every graph $G$ with $\operatorname{Lit}(G)\leq\ell$ has a regular partition into excellent sets with $(1 + o_{ε\to 0,\ell}(1))\cdotε^{-\ell}\cdot\ln(1/ε)$ parts and in the other direction, for every $\ell\in\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose partitions into good sets must have size at least $(1 + o_{ε\to 0,\ell}(1))\cdotε^{-\ell}$. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the $o_{ε\to 0,\ell}(1)$ term above by a constant $c > 0$, we obtain randomized $O_{c,ε,\ell}(n\cdot\log(n))$-time algorithms for partitions/equipartitions into good sets, a deterministic $O_{c,ε,\ell}(n^2)$-time algorithm for partitions into good sets, a deterministic $O_{c,ε,\ell}(n^6)$-time algorithm for equipartitions into good sets, a deterministic $O_{c,\ell,ε}(1)\cdot n^{O(\ell\cdot 2^{2\cdot\ell+4})}$-time algorithm for partitions/equipartitions into excellent sets, and $O_{c,ε,\ell}(\log(n+1))$-space algorithms for partitions/equipartitions into good/excellent sets.

0.17

Optimal girth-dependent bounds for the Bethe approximation of the permanent

cs.DS math.CO ·2026-09-02 ·Dingding Dong, Vishesh Jain
theoryhot direction similarity 0.62
Abstract · 21 pages; comments welcome!

For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$ has girth at least an even integer $g \geq 4$, then \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).\] The upper bound is attained by the adjacency matrix of a disjoint union of $g$-cycles.

0.47

A proof of a conjecture on bipartite correspondence packing

cs.DM math.CO ·2026-11-16 ·Xin Zhang
theory similarity 0.62
Abstract

A correspondence cover assigns a set of possible colors to each vertex of a graph. For each edge, a matching between the two endpoint color sets specifies the forbidden color pairs. A correspondence coloring selects one color at each vertex so that no forbidden pair is selected. A full correspondence packing is a collection of such colorings that uses every color at each vertex exactly once. We prove a conjecture of Cambie, Cames van Batenburg, Davies, and Kang [Random Structures & Algorithms 64 (2024), 62--93]. For every sufficiently large $D$, there is a positive integer $k(D)=(1+o(1))D/\log D$ such that every correspondence cover of any finite bipartite graph has a full correspondence packing if each color has at most $D$ forbidden partners and each vertex has $k(D)$ colors. More precisely, we prove this conclusion with \[ k(D)=\left\lceil\frac{D}{\log D-2\log\log D-6}\right\rceil \] for every integer $D\ge\lceil e^{20}\rceil$.

0.10

Multiway Partition is FPT for Connectivity Functions

cs.DM math.CO ·2026-08-11 ·Tony Huynh, Eun Jung Kim, Sang-il Oum, Roohani Sharma, Marek Sokołowski
theory similarity 0.62
Abstract · New title and strengthened main theorem that only needs posimodularity. Application to Hypergraph Multiway Partition is also added. 9 Pages,…

Let $E$ be a set of $n$ elements, $f\colon2^E\to\mathbb Z_{\ge0}$ be submodular, $t_1,\ldots,t_r\in E$ be distinct, and $k\in\mathbb N$. The Submodular Multiway Partition problem asks whether $E$ has a partition $(P_1,\ldots,P_r)$ with $t_i\in P_i$ for all $i$ and $\sum_i f(P_i)\le k$. We prove that this problem can be solved in $r^{O(k)}n^{O(1)}$ time whenever $f$ is posimodular. This covers monotone submodular functions, matroid rank functions, and nonnegative combinations of monotone and symmetric submodular functions. When $f$ is a connectivity function, we remove the dependence on the number of terminals and obtain a $k^{O(k)}n^{O(1)}$-time algorithm. The proof is entirely elementary, and is arguably the simplest proof that Edge Multiway Cut is fixed-parameter tractable. As a new consequence, our main result immediately implies that Hypergraph Multiway Partition is fixed-parameter tractable.

0.10

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.62
Abstract

Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=Θ_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--Füredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.

0.27

Nonisomorphic Graphs Can Share an Arbitrarily Large Fraction of Their Vertex-Deleted Cards

cs.DM math.CO ·2026-08-12 ·Sergey Ivanov
similarity 0.62
Abstract

For a graph $G$, its vertex deck is the multiset of graphs obtained by deleting one vertex. Bowler, Brown, and Fenner (BBF) proposed $2\lfloor(n-1)/3\rfloor$ as the maximum possible overlap between the decks of two nonisomorphic $n$-vertex graphs, for all sufficiently large $n$. We first give an explicit pair of connected nonisomorphic graphs on $78$ vertices with at least $51$ common cards, exceeding BBF's predicted value of $50$. We then construct, for every even $r\ge4$, families at arbitrarily large orders whose overlap fraction is asymptotically at least $1-1/r$. Consequently, for every $α<1$, infinitely many pairs have more than $αn$ common cards, so the attainable fraction is arbitrarily close to the full deck. For representative instances, the predicted overlaps were also checked by complete deck generation and isomorphism testing with Brendan McKay's nauty tools.

0.38