CS Paper Radar

Isolation of $k$-cliques in uniform hypergraphs

Mattea Baluci, Peter Borg

cs.DM math.CO ·submitted 2026-11-12 20:24 UTC · v1
theory

Abstract

A copy of a hypergraph $F$ is called an $F$-copy. For any integers $k$ and $r$ with $2 \leq r \leq k$, let $K_k^r$ denote the complete $r$-uniform hypergraph whose vertex set is $[k] = \{1, 2, \dots, k\}$ (that is, the edges of $K_k^r$ are the $r$-element subsets of $[k]$). Given an $r$-uniform $m$-edge hypergraph $H$, the $K_k^r$-isolation number of $H$, denoted by $ι(H, K_k^r)$, is the size of a smallest subset $D$ of the vertex set of $H$ such that the closed neighbourhood $N[D]$ of $D$ intersects the vertex sets of the $K_k^r$-copies contained by $H$ (equivalently, $H-N[D]$ contains no $K_k^r$-copy). We prove that if $H$ is connected and not a $K_k^r$-copy, then $$ι(H, K^r_k) \le \left \lfloor \frac{(r-1)m + 1}{(r-1)(\binom{k}{r}+1) + 1} \right \rfloor.$$ The bound is best possible. This is a solution to a problem of Li, Zhang and Ye. We also provide an alternative proof for $r < k$. Both proofs introduce new ideas for establishing bounds on isolation parameters.

Comment
13 pages

Closest papers

Nearest neighbours by meaning across the whole index.

On edge-ordered Ramsey numbers of hypergraphs

cs.DM math.CO ·2026-10-29 ·Martin Balko, Jelena Glišić
theory similarity 0.68
Abstract · 10 pages

For an integer $h\geq2$, an edge-ordered $h$-uniform hypergraph $H^<$ is an $h$-uniform hypergraph with a linear ordering of its hyperedges. For an integer $q \geq 1$, the edge-ordered Ramsey number $R_{\mathrm{edge}}(H^<;q)$ of $H^<$ is the smallest positive integer $N$ such that there exists an edge-ordered $h$-uniform hypergraph $G^<$ on $N$ vertices such that, for every $q$-coloring of the hyperedges of $G^<$, there is a monochromatic copy of $H^<$ in $G^<$ preserving the hyperedge order. In this note, we show that, for every edge-ordered $h$-uniform hypergraph $F^<$ on $n$ vertices with $m\geq1$ hyperedges, $R_{\mathrm{edge}}(F^<;q) \leq R_h(F;q)^{Cm^2}$ where $F$ is the underlying unordered hypergraph, $R_h(F;q)$ is its standard $q$-color Ramsey number, and $C=C(h,q)>0$ is a constant. For fixed $h\geq3$ and $q\geq2$, this shows that prescribing the hyperedge order does not require an increase in the tower height of the classical upper bound. It also settles a problem posed by Fox and Li (2020), and for $h=2$ gives the bound $2^{O(n^4\log n)}$, improving their bounds for every fixed $q \geq 3$.

0.33

Lower Bounds for Minimal-Transversal Enumeration of Bounded-Dimension Hypergraphs and the maximum Minimal Hitting Set Problem

cs.CC ·2026-10-20 ·Arnaud Mary
similarity 0.66
Abstract

We present lower bounds for the maximum minimal hitting set problem and for the problem of enumeration of minimal transversals in bounded-dimension hypergraphs. Our starting point is the recent reduction of Kobayashi, Kurita, and Wasa (2026), developed to establish ETH-based hardness of hypergraph dualization. Adapting their construction, we show that, under ETH, deciding whether a hypergraph $\mathcal{G}$ with $n$ vertices and $m$ hyperedges has a minimal transversal of size at least $k$ cannot be done in time $n^{f(k)}m^{o(k)}$, for an arbitrary computable $f$. We transfer this bound to the following decision problem: given a dimension-at-most-$r$ hypergraph and a family of $s$ of its minimal transversals, decide whether another exists. Under ETH, this problem admits no uniform algorithm with running time $n^{f(r)}(s+1)^{o(r)}$. Under SETH, for every fixed $t \geq 2$, it admits no algorithm with running time $\poly(|\mathcal{G}|)(s+1)^c$ for dimension at most $2t$ and any $c<t$. As corollaries, the same exponent obstructions hold for the total time of any output-polynomial enumeration algorithm, with $s$ replaced by the total number of minimal transversals. In particular, polynomial delay is excluded under SETH already for dimension at most four.

0.15

Finding Hypercliques Faster Than Brute Force

cs.DS cs.CC ·2026-11-03 ·Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
similarity 0.62
Abstract

We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.

0.23

Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs

cs.DM math.CO ·2026-10-10 ·Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang
theory similarity 0.60
Abstract

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

0.21

Connected Dominating Set on Semi-Ladder-Free Graphs

cs.DS ·2026-09-30 ·Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh, Sanjay Seetharaman, Anannya Upasana
publishedtheory similarity 0.59
Abstract · This is an archived version of the paper accepted at ISAAC 2026

We study \textsc{Connected Dominating Set} on graphs whose closed-neighborhood set systems are $d$-semi-ladder-free. This structural condition strictly generalizes the biclique-free setting and provides a natural regime for connectivity-constrained domination. We obtain both a fixed-parameter algorithm and an approximate kernelization framework for the problem on this class. Our algorithmic result is based on a new compact representation theorem for inclusion-wise minimal set covers in $d$-semi-ladder-free set systems. Although the number of minimal set covers of size at most $k$ may be as large as $n^{Ω(k)}$, we show that all such set covers can nevertheless be encoded by a family of at most $k^{kd+1}$ tuples, and that this family can be enumerated in time $\Oh(k^{kd+2}\cdot nm)$. Combining this representation with a \textsc{Group Steiner Tree} subroutine, we obtain an algorithm for \textsc{Connected Set Cover}, which in turn yields an algorithm for \textsc{Connected Dominating Set} running in time $k^{kd+2}\cdot 2^k \cdot n^{\Oh(1)}$ and polynomial space. For the preprocessing result, we introduce grouped domination cores and dominator cores, and prove polynomial upper bounds on their sizes in $d$-semi-ladder-free graphs. Using these structures, we obtain, for every fixed $d$ and $\varepsilon>0$, a polynomial-time $(1+\varepsilon)$-lossy compression for \textsc{Connected Dominating Set} to an equivalent reduced instance of size $k^{\Oh(d^2/\varepsilon)}$. The reduced instance is a \textsc{Connected Dominating Set} instance on a $(d+2)$-semi-ladder-free graph.

0.22

Mutual-visibility k-colouring is NP-complete for every fixed diameter

cs.DM cs.CCmath.CO ·2026-10-31 ·Siddhesh Chaubal
similarity 0.58
Abstract · 9 pages, 1 figure. v2: extended to any fixed number k of colours; new title

A mutual-visibility set in a graph G is a set S of vertices such that any two vertices of S are connected by a shortest path with no internal vertex in S, and the mutual-visibility chromatic number $χ_μ(G)$ is the minimum number of mutual-visibility sets needed to partition V(G). Babu, Di Stefano and Lakshmanan showed that it is NP-complete to decide whether $χ_μ(G)\le 2$ for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed $d\ge2$; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed $k\ge2$ and $d\ge2$, it is NP-complete to decide whether $χ_μ(G)\le k$ for graphs of diameter d. The proof rests on a reformulation of $χ_μ(G)\le 2$ for diameter-two graphs as the 2-colourability of an associated hypergraph, and on a reduction from 2-colourability of 3-uniform hypergraphs without short cycles.

0.24

Distance-$2$ isolation of connected graphs

cs.DM math.CO ·2026-11-14 ·Peter Borg, Pawaton Kaemawichanurat
hot direction similarity 0.58
Abstract · 15 pages

If $\mathcal{F}$ is a set of graphs and $F$ is a copy of a graph in $\mathcal{F}$, then we call $F$ an $\mathcal{F}$-graph. Let $G$ be a connected $n$-vertex graph. For a subset $D$ of the vertex set $V(G)$, let $N^2[D]$ denote the second closed neighbourhood of $D$. Let $ι_2(G, \mathcal{F})$ denote the size of a smallest subset $D$ of $V(G)$ such that $N^2[D]$ intersects the $\mathcal{F}$-graphs contained by $G$ (equivalently, $G - N^2[G]$ contains no $\mathcal{F}$-graph). For $k \geq 0$, let $\mathcal{E}_k$ denote the set of connected graphs that have at least $k$ edges (and at least one vertex if $k = 0$). By a well-known result of Meir and Moon, $ι_2(G, \mathcal{E}_0) \leq n/3$ if $n \geq 3$. We show that $ι_2(G, \mathcal{E}_1) \leq n/4$ if $n \neq 2$, $n \neq 3$ and $G$ is not a $7$-cycle. Hua and Liu recently showed that if $G$ is not a $4$-vertex path or a $4$-cycle or a $9$-cycle, then there exists a subset $D$ of $V(G)$ such that $|D| \leq n/5$ and each component of $G-N^2[D]$ has a universal vertex. We strengthen this result by showing that $ι_2(G, \mathcal{E}_2) \leq n/5$ if $n \neq 3$, $n \neq 4$ and $G$ is not an $8$-cycle or one of five $9$-vertex graphs. It follows that $ι_2(G, \mathcal{E}_3) \leq n/5$ if $G$ is not a $3$-cycle or a $4$-vertex graph or a $9$-cycle. This also implies the result of Hua and Liu, and that if $\mathcal{C}$ is the set of cycles, then $ι_2(G, \mathcal{C}) \leq n/5$ unless $G$ is a $3$-cycle or a $4$-vertex graph containing a cycle. All these bounds are sharp.

0.40

Clique counts under degree and matching constraints

cs.DM math.CO ·2026-10-31 ·Rajat Adak
theory similarity 0.57
Abstract

We study the maximum number of $t$-cliques in graphs with maximum degree at most $D$ and matching number at most $M$, with no restriction on the number of vertices. For $t\ge 3$, we determine this maximum whenever $D\ge 2M-1$ and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for $D\ge 2M$, while $K_{2M}$ is uniquely extremal when $D=2M-1$. We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even $D$. For fixed even $D$ and $3\le t\le D+1$, every extremal graph consists, apart from isolated vertices, of copies of $K_{D+1}$ together with a remainder whose order is bounded independently of $M$. When $D/2$ divides $M$, this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.

0.28