Papers for

database indexing teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Upper bound on minimum vertices blocking complete cliques in hypergraphs

Isolation of $k$-cliques in uniform hypergraphs

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.

Thu 12 NovDiscrete Mathematics
The gist
This paper finds a way to determine the smallest number of points needed to 'block' or isolate all complete cliques of size k within a special type of network called a uniform hypergraph. The authors prove an exact formula for this minimum number, which depends on how many edges the hypergraph has and the size of the cliques they're trying to block. This solves a previously posed question and introduces new ideas to measure how well certain subsets of vertices can control or disrupt clique formation in these networks.
Open → 2611.17489v1

Induced packing branchwidth links graph structures and decompositions

Induced packing treewidth III. Branch decompositions

Abstract: The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. In this paper, we introduce induced packing branchwidth, a branch-decomposition analogue of induced packing treewidth. For a graph $H$, the induced $H$-packing branchwidth of a graph $G$, denoted by $\branchpi_H(G)$, is the minimum, over all branch decompositions of $G$, of the largest number of pairwise anticomplete induced copies of $H$ that cross one displayed cut. For $H=P_2$, it equals sim-width. We prove several structural properties of graphs of bounded $\branchpi_H$, for various choices of $H$, including $χ$-boundedness, polynomial degree-boundedness, and metric properties.

Mon 9 NovDiscrete Mathematics
The gist
This work studies a new way to measure structural complexity in networks called induced packing branchwidth. The authors connect this measure to existing concepts that describe how graphs can be broken into simpler pieces while avoiding certain patterns. They also show how graphs with small values of this measure have useful properties, like constraints on colorings and distances. This helps unify different approaches to understanding complicated networks.
Open → 2611.12358v1