Skip to content
Preprint

On the number of factorable induced subgraphs

Jul 2026 · 0 citations · 30 references
Mathematics

Abstract

Let $F$ be an $r$-vertex graph. In this paper, we study the $F$-factor problem in random induced subgraphs of dense graphs. We show that for any $r$-vertex graph $F$ and $\gamma>0$, if $H$ is an $n$-vertex graph with minimum degree at least $(1-1/\chi_{cr}(F)+\gamma)n$, then for every fixed $p \in (0,1)$, the random induced subgraph $H[p]$ contains an $F$-factor with probability at least $1/(rq)-o_n(1)$, where $q\in \mathbb{N}$ is the order of certain coset group defined from $H$. The probability is asymptotically best possible for infinitely many $F$ and $H$ and yields that a $1/(rq)-o_n(1)$ proportion of the subsets of $H$ induce $F$-factors, interestingly, regardless of whether $H$ itself admits an $F$-factor. Similar results are obtained for perfect matchings in hypergraphs under minimum degree conditions. Our proof combines concentration inequalities, lattice point counting in $\mathbb{Z}^d$ and structural theorems for $F$-factors in dense (hyper)graphs.

View source

Similar papers

Preprint Oct 2026

Counting cographs in locally dense graphs

An $n$-vertex graph $G$ is $(\rho, d)$-dense if for all $U \subseteq V(G)$ of size at least $\rho n$, the induced subgraph $G[U]$ contains at least $\frac{d}{2}|U|^2$ edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, R\"{o}dl, and Schacht conjectured that, for any fixed graph $F$, th...

Hyunwoo Lee · 0 citations
Preprint Oct 2026

Induced-Count Discrepancy in Uniform Hypergraphs

Let $u_k^{(r)}(H,p)$ be the maximum, over all $k$-vertex $r$-uniform hypergraphs $F$, of the absolute difference between the number of induced copies of $F$ in $H$ and its expectation in the binomial random $r$-graph with the same number of vertices as $H$ and edge probability $p$. Let $u_k^{(r)}(n,p)$ be the minimum o...

Cheng-Long Yu · 0 citations
Preprint Aug 2026

A dichotomy for the number of vertex-critical ($P_5$, $H$)-free graphs when $H$ is bipartite

A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge...

Iain Beaton, Ben Cameron · 2 citations
Preprint Oct 2026

Sharp linear Tur\'an remainders for cycle and edge extremality

For a graph $G$, let $e(G)$ denote the number of edges of $G$, and let $c(G)$ be the number of distinct cycles in $G$. Morrison, Roberts and Scott asked whether, for every fixed graph $H$ and all large $n$, some $n$-vertex $H$-free graph maximizes both $e(G)$ and $c(G)$. In this paper, we show that the answer is no for...

Ji-Fu Lin, Xiao-Lin Wang, Guang-Miao Yu · 0 citations
Preprint Aug 2026

The Erd\H{o}s four-edge intersection problem

For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}s...

Andrzej Żak · 0 citations
#artificial intelligence Preprint Aug 2026

Exponential random graph models with soft clique constraints

Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,n\}$. We consider an exponential random graph model which gives higher probability to $G \in \mathbf{G}_n$ than to $H \in \mathbf{G}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in $\mathbf{G}_n$ ha...

Yasmin Tousinejad, Vera Koponen · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.