CS Paper Radar

Property B for random non-uniform hypergraphs

Grzegorz Ryn, Jakub Kozik

cs.DM math.COmath.PR ·submitted 2026-10-05 20:49 UTC · v1

Abstract

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to each $k$-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

Closest papers

Nearest neighbours by meaning across the whole index.

Streaming Hypergraph Coloring via Palette Sparsification

cs.DM math.COcs.DS ·2026-08-20 ·Artur Czumaj, Pan Peng, Ruizhe Shi, Christian Sohler
theory similarity 0.75
Abstract · 25 pages. This revision merges the original manuscript with independent work by Czumaj, Peng, and Sohler

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $Δ$ with $O(Δ^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $Θ(\sqrt{\log n})$ colors from a palette of size $O(Δ^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of $Δ$ for which any deterministic one-pass algorithm requires $\exp(Δ^{Ω(1)})$ colors.

0.37

Almost All 3-uniform Hypergraphs are Class 1

cs.DM math.CO ·2026-11-03 ·Arnab Chaterjee, Asaf Ferber, Marcelo Sales, Mason Shurman
similarity 0.75
Abstract

The chromatic index $χ'(H)$ of a hypergraph $H$ is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree $Δ(H)$, and when $χ'(H)= Δ(H)$, we say that $H$ is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs. We show for $n^{-2/3-1/200}\leq p \leq 0.99$ that the $3$-uniform binomial random hypergraph $H\sim H_{n,p}^{(3)}$ is Class 1 with high probability. We also show that this result doesn't hold for uniformities above $3$. For a broad range of $p$, when $k \geq 4$ and $k \nmid n$, the hypergraph $H \sim H_{n,p}^{(k)}$ is with high probability not Class 1.

0.16

An Improved Bound for Testing $k$-Colorability

cs.DM ·2026-10-22 ·Bangjie Xu
theory similarity 0.73
Abstract

We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\varepsilon$-far from being $k$-colorable if at least $\varepsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that a uniformly random induced subgraph on $O(k\log k/\varepsilon)$ vertices is non-$k$-colorable with probability at least $2/3$ whenever the original graph is $\varepsilon$-far from $k$-colorable. The proof combines a palette-based coloring process with a container-style encoding-and-reconstruction argument. This yields $O(k\log k/\varepsilon)$, which is no worse than the previous state of the art $O(k\log (1/\varepsilon)/\varepsilon)$ throughout the nonvacuous parameter range, and is an improvement when $\log k=o(\log(1/\varepsilon))$. For each fixed $k$, combining this upper bound with the known $Ω(\log k/\varepsilon)$ lower bound gives $Θ(1/\varepsilon)$ dependence on $\varepsilon$.

0.06

On the Critical Window for Adaptable 2-Colorability

cs.DM math.CO ·2026-09-10 ·Thomas Snow
theory similarity 0.72
Abstract · 37 pages; typo corrected in reference

We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erd$ő$s-R$é$nyi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on $O(\log{n})$ many vertices.

0.21

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.71
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21

Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{Ω(1)} n$ Colors

cs.CC ·2026-10-27 ·Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles
hot direction similarity 0.70
Abstract · 20 pages

We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.

0.26

Power of Conditional Sampling on Hypergraphs

cs.DS ·2026-10-16 ·Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, Gopinath Mishra
theory similarity 0.70
Abstract

Let $G=(V,E)$ be a $d$-uniform hypergraph with $|V|=n$ and $|E|=m$. Estimating $m$ from uniformly random hyperedge samples requires $Θ(\sqrt{m})$ samples by a birthday-paradox argument. We investigate the power of conditional sampling through a hierarchy of oracles: for an integer $1\le s\le d$, given pairwise disjoint subsets $X_1,\ldots,X_s\subseteq V$, the $s$-colorful oracle returns a hyperedge chosen uniformly at random from all hyperedges contained in $X_1\cup\cdots\cup X_s$ that intersect every $X_i$, provided one exists. For $s=1$, this samples a uniformly random hyperedge induced by $X_1$. For every $1\le s\le d$, we give a randomized algorithm that outputs $\widehat{m}\in[(1-\varepsilon)m,(1+\varepsilon)m]$ with probability at least $2/3$ using $O_{s,d}(\operatorname{poly}(1/\varepsilon,\log n))$ conditional samples, where the exponent of $\log n$ is an absolute constant independent of both $s$ and $d$. Conditional sampling thus yields an exponential separation over uniform hyperedge sampling. We also study the decision version, in which the oracle only reports whether a qualifying hyperedge exists. For every $1\le s<d$, we prove that any algorithm using the $s$-colorful decision oracle requires $\widetildeΩ_{s,d}(n^{\frac{d-s}{d-s+1}})$ queries. Hence, for $s<d$, access to uniformly random witness hyperedges (random certificates) is exponentially more powerful than existence queries. For $s=d$, decision queries alone achieve $\operatorname{poly}(1/\varepsilon,\log n)$ query complexity, but the exponent of $\log n$ is known to be $Θ(d)$. The colorful hierarchy thus exhibits a phase transition at $s=d$: for $s<d$, random certificates are essential for polylogarithmic-query estimation, whereas at $s=d$ decision queries suffice, yet random certificates still provably reduce the exponent of $\log n$ from $Θ(d)$ to an absolute constant.

0.21

Improved Space Bounds for Promise Graph Coloring in Adversarial Streams

cs.DS cs.CC ·2026-10-17 ·Sergio Thoumi
theory similarity 0.69
Abstract

We study promise graph coloring in one pass insertion-only adversarial streams. We give a randomized algorithm that distinguishes 3-colorable graphs from graphs that are not 6-colorable using $O(n^{3/2}\log(n/\varepsilon)\log n)$ bits of space. This provides a truly subquadratic space algorithm for a constant coloring gap, answering an open problem posed by Assadi, Sundaresan, and Yazdanyar [SODA 2026] for $q=3$. Combining this algorithm with the vertex-sampling lemma of Assadi et al.\ yields, for any $144\lceil\log_2 n\rceil\le Q\le n$, a one-pass decision algorithm distinguishing $3$-colorable graphs from graphs that are not $Q$-colorable using $O((n/Q)^{3/2}\log^5 n)$ bits of space. This improves upon the $\widetilde{O}((n/Q)^2)$ bound achievable via dynamic streaming techniques. Setting $Q=\lceil n^{1/3}\rceil$ yields a semi-streaming decision algorithm, answering the decision version of another open problem posed by Assadi et al. On the negative side, we prove that distinguishing $χ(G)\le q$ from $χ(G)\ge(q-1)^2$ requires $Ω(n^2/q^5)$ bits of space, improving upon the previously established $q^2/4$ threshold using the same space complexity.

0.19