CS Paper Radar

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

G. Gutin, Y. Hao, Y. Zhou

cs.DM math.CO ·submitted 2026-09-20 00:42 UTC · v1
theory

Abstract

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))$.

Comment
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, and no mistakes were found

Closest papers

Nearest neighbours by meaning across the whole index.

New bounds on the boxicity of Kneser graphs

cs.DM math.CO ·2026-11-12 ·L. Sunil Chandran, Suraj Kumar Sahoo
theory similarity 0.67
Abstract

For a graph $G=(V,E)$, the boxicity $\operatorname{box}(G)$ is the least integer $d$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The Kneser graph $K(n,k)$ is the graph whose vertex set corresponds to the family of $k$ sized subsets of an $n$ sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. In this short paper, we provide new bounds for the boxicity of $K(n,k)$. We first show that for $k\ge 2$ and $n\ge 2k+1$, $\operatorname{box}(K(n,k))\ge n-2k$, thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when $n\geq 3k+1$ and $k\ge 3$. The proof of this result uses the topological method and follows a strategy similar to Greene's proof of the Kneser's conjecture on the chromatic number of $K(n,k)$. We also show that for $k\ge 2$, $t\ge 1$ and $n=2k+t$, $\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ).$ In particular, for every $t=t(k)\ge1$ with $t^3\log k=o(k)$, $\operatorname{box}(K(2k+t,k))=o(k)$. This is the first upper bound on the boxicity of $K(n,k)$ that is sublinear in $n$. We also show that for large enough $k$, $\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}$.

0.28

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.66
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

Optimal-Size Strong Connectivity Preservers under Two Edge Failures in Subcubic Time

cs.DS ·2026-11-12 ·Wanhee Lee, Chenglin Fan
theory similarity 0.65
Abstract · 43 pages

A $k$-edge-failure strong connectivity preserver of a directed graph on $N$ vertices is a spanning subgraph that has the same strongly connected components as the input after each set of at most $k$ edge deletions. The lower-bound construction of Baswana, Choudhary, and Roditty [BCR18], adapted to strong connectivity in [CC20], gives the previous best bound of $Ω(2^kN)$ necessary edges. Hoppenworth, Saranurak, and Wang [HSW25] prove an $O(k4^kN\log N)$ upper bound, leaving a logarithmic gap for fixed $k$. We close this gap by giving an explicit strongly connected graph on $N=2^d$ vertices with $N-1+(N/2)\log_2N$ edges, every one of which is necessary in a two-failure preserver. Together with the upper bound of [HSW25], this proves that the optimal size in the worst case is $Θ_k(N\log N)$ for every fixed $k\geq2$, whereas it is $Θ(N)$ for $k=1$ [GIP20]. The same graph has a one-failure preserver with at most $3(N-1)$ edges. We also give a randomized algorithm that either returns a spanning subgraph or reports failure. For every fixed $c,\varepsilon>0$, with probability at least $1-N^{-c}$ it returns a correct preserver for $k=2$ with $O(N\log N)$ edges, in $\widetilde O(N^{(ω+3)/2+\varepsilon})$ time and $\widetilde O(N^2)$ space. Here $ω$ is the matrix multiplication exponent over a fixed finite field.

0.18

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.63
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

A proof of a conjecture on bipartite correspondence packing

cs.DM math.CO ·2026-11-16 ·Xin Zhang
theory similarity 0.61
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.09

Tarski Fixed Points in Quasi-FPT Queries

cs.CC cs.DS ·2026-10-05 ·Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis
publishedtheoryhighly cited similarity 0.61
Abstract

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{Ω(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$, \[ Ω\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le \operatorname{Tarski}(n,k)\le O\left(5^k(\log n)^{\lceil \log k\rceil}\right). \] Succinctly, up to the fixed-parameter factor of $5^k$, the complexity is settled at $(\log n)^{Θ(\log k )}$. In particular, we obtain the first super-polynomial query lower bound for this problem.

0.59

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

cs.LO math.CO ·2026-10-13 ·Heshun Fan
code/data similarity 0.61
Abstract · 21 pages, 1 figure. Lean formalization included as ancillary files. Code available at: https://github.com/HUSTFRED/Math_open_problems

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.

0.57

Counting $6$-Cliques in $O(n^{5.97})$ time and $O(\log n)$ space

cs.DS ·2026-11-18 ·Afrouz Jabal Ameli, Niklas Mohrin, Jesper Nederlof
similarity 0.61
Abstract

We present an algorithm that, given read-only access to the adjacency matrix of an $n$-vertex graph $G$, computes the number of $6$-cliques in $G$ using $O(n^{5.97})$ time and $O(\log n)$ space. We achieve this by exploiting a decomposition of an equality indicator function underlying, among others, the refutations of the Exponential Time Hypothesis by OpenAI and Anthropic, and of the $k$-Clique Conjecture by Vassilevska Williams and Zamir [arXiv, 2026]. Via known reductions, this implies an $O(1.994^n)$ time and polynomial space algorithm for Max Cut on $n$-vertex graphs.

0.08