Jie Han

$F$ -factors in Quasi-random Hypergraphs

Given $k\ge 2$ and two $k$ -graphs ( $k$ -uniform hypergraphs) $F$ and $H$ , an $F$ -factor in $H$ is a set of vertex-disjoint copies of $F$ that together covers the vertex set of $H$ . Lenz and Mubayi [J. Combin. Theory Ser. B, 2016] studied the $F$ -factor problem in quasi-random $k$ -graphs with minimum degree $Ω(n^{k-1})$ . They posed the problem of characterizing the $k$ -graphs $F$ such that every sufficiently large quasi-random $k$ -graph with constant edge density and minimum degree $Ω(n^{k-1})$ contains an $F$ -factor, and in particular, they showed that all linear $k$ -graphs satisfy this property. In this paper we prove a general theorem on $F$ -factors which reduces the $F$ -factor problem of Lenz and Mubayi to a natural sub-problem, that is, the $F$ -cover problem. By using this result, we answer the question of Lenz and Mubayi for those $F$ which are $k$ -partite $k$ -graphs, and for all 3-graphs $F$ , separately. Our characterization result on 3-graphs is motivated by the recent work of Reiher, Rödl and Schacht [J. Lond. Math. Soc., 2018] that classifies the 3-graphs with vanishing Turán density in quasi-random $k$ -graphs.

$H$ -factors in graphs with small independence number

Let $H$ be an $h$ -vertex graph. The vertex arboricity $ar(H)$ of $H$ is the least integer $r$ such that $V(H)$ can be partitioned into $r$ parts and each part induces a forest in $H$ . We show that for sufficiently large $n\in h\mathbb{N}$ , every $n$ -vertex graph $G$ with $δ(G)\geq \max\left\{\left(1-\frac{2}{f(H)}+o(1)\right)n, \left(\frac{1}{2}+o(1)\right)n\right\}$ and $α(G)=o(n)$ contains an $H$ -factor, where $f(H)=2ar(H)$ or $2ar(H)-1$ . The result can be viewed an analogue of the Alon--Yuster theorem \cite{MR1376050} in Ramsey--Turán theory, which generalises the results of Balogh--Molla--Sharifzadeh~\cite{MR3570984} and Knierm--Su~\cite{MR4193066} on clique factors. In particular the degree conditions are asymptotically sharp for infinitely many graphs $H$ which are not cliques.

Adversarial Fine-tune with Dynamically Regulated Adversary

Adversarial training is an effective method to boost model robustness to malicious, adversarial attacks. However, such improvement in model robustness often leads to a significant sacrifice of standard performance on clean images. In many real-world applications such as health diagnosis and autonomous surgical robotics, the standard performance is more valued over model robustness against such extremely malicious attacks. This leads to the question: To what extent we can boost model robustness without sacrificing standard performance? This work tackles this problem and proposes a simple yet effective transfer learning-based adversarial training strategy that disentangles the negative effects of adversarial samples on model's standard performance. In addition, we introduce a training-friendly adversarial attack algorithm, which facilitates the boost of adversarial robustness without introducing significant training complexity. Extensive experimentation indicates that the proposed method outperforms previous adversarial training algorithms towards the target: to improve model robustness while preserving model's standard performance on clean data.

Cover 3-uniform hypergraphs by vertex-disjoint tight paths

Let $H$ be an $n$ -vertex 3-uniform hypergraph such that every pair of vertices is in at least $n/3+o(n)$ edges. We show that $H$ contains two vertex-disjoint tight paths whose union covers the vertex set of $H$ . The quantity two here is best possible and the degree condition is asymptotically best possible. This result also has an interpretation as the \emph{deficiency problems}, recently introduced by Nenadov, Sudakov and Wagner: every such $H$ can be made Hamiltonian by adding at most two vertices and all triples intersecting them.

Dropout Prediction Uncertainty Estimation Using Neuron Activation Strength

Dropout has been commonly used to quantify prediction uncertainty, i.e, the variations of model predictions on a given input example. However, using dropout in practice can be expensive as it requires running dropout inferences many times. In this paper, we study how to estimate dropout prediction uncertainty in a resource-efficient manner. We demonstrate that we can use neuron activation strengths to estimate dropout prediction uncertainty under different dropout settings and on a variety of tasks using three large datasets, MovieLens, Criteo, and EMNIST. Our approach provides an inference-once method to estimate dropout prediction uncertainty as a cheap auxiliary task. We also demonstrate that using activation features from a subset of the neural network layers can be sufficient to achieve uncertainty estimation performance almost comparable to that of using activation features from all layers, thus reducing resources even further for uncertainty estimation.

Matching of given sizes in hypergraphs

For all integers $k,d$ such that $k \geq 3$ and $k/2\leq d \leq k-1$ , let $n$ be a sufficiently large integer {\rm(}which may not be divisible by $k$ {\rm)} and let $s\le \lfloor n/k\rfloor-1$ . We show that if $H$ is a $k$ -uniform hypergraph on $n$ vertices with $δ_{d}(H)>\binom{n-d}{k-d}-\binom{n-d-s+1}{k-d}$ , then $H$ contains a matching of size $s$ . This improves a recent result of Lu, Yu, and Yuan and also answers a question of Kühn, Osthus, and Townsend. In many cases, our result can be strengthened to $s\leq \lfloor n/k\rfloor$ , which then covers the entire possible range of $s$ . On the other hand, there are examples showing that the result does not hold for certain $n, k, d$ and $s= \lfloor n/k\rfloor$ .

Semantic Compression with Side Information: A Rate-Distortion Perspective

We consider the semantic rate-distortion problem motivated by task-oriented video compression. The semantic information corresponding to the task, which is not observable to the encoder, shows impacts on the observations through a joint probability distribution. The similarities among intra-frame segments and inter-frames in video compression are formulated as side information available at both the encoder and the decoder. The decoder is interested in recovering the observation and making an inference of the semantic information under certain distortion constraints. We establish the information-theoretic limits for the tradeoff between compression rates and distortions by fully characterizing the rate-distortion function. We further evaluate the rate-distortion function under specific Markov conditions for three scenarios: i) both the task and the observation are binary sources; ii) the task is a binary classification of an integer observation as even and odd; iii) Gaussian correlated task and observation. We also illustrate through numerical results that recovering only the semantic information can reduce the coding rate comparing to recovering the source observation.

preprint2021arXiv

Boost-S: Gradient Boosted Trees for Spatial Data and Its Application to FDG-PET Imaging Data

Boosting Trees are one of the most successful statistical learning approaches that involve sequentially growing an ensemble of simple regression trees (i.e., "weak learners"). However, gradient boosted trees are not yet available for spatially correlated data. This paper proposes a new gradient Boosted Trees algorithm for Spatial Data (Boost-S) with covariate information. Boost-S integrates the spatial correlation structure into the classical framework of gradient boosted trees. Each tree is grown by solving a regularized optimization problem, where the objective function involves two penalty terms on tree complexity and takes into account the underlying spatial correlation. A computationally-efficient algorithm is proposed to obtain the ensemble trees. The proposed Boost-S is applied to the spatially-correlated FDG-PET (fluorodeoxyglucose-positron emission tomography) imaging data collected during cancer chemoradiotherapy. Our numerical investigations successfully demonstrate the advantages of the proposed Boost-S over existing approaches for this particular application.

preprint2021arXiv

Minimum degree thresholds for Hamilton $(k/2)$ -cycles in $k$ -uniform hypergraphs

For any even integer $k\ge 6$ , integer $d$ such that $k/2\le d\le k-1$ , and sufficiently large $n\in (k/2)\mathbb N$ , we find a tight minimum $d$ -degree condition that guarantees the existence of a Hamilton $(k/2)$ -cycle in every $k$ -uniform hypergraph on $n$ vertices. When $n\in k\mathbb N$ , the degree condition coincides with the one for the existence of perfect matchings provided by Rödl, Ruciński and Szemerédi (for $d=k-1$ ) and Treglown and Zhao (for $d\ge k/2$ ), and thus our result strengthens theirs in this case.

preprint2021arXiv

Structural Entropy of the Stochastic Block Models

With the rapid expansion of graphs and networks and the growing magnitude of data from all areas of science, effective treatment and compression schemes of context-dependent data is extremely desirable. A particularly interesting direction is to compress the data while keeping the "structural information" only and ignoring the concrete labelings. Under this direction, Choi and Szpankowski introduced the structures (unlabeled graphs) which allowed them to compute the structural entropy of the Erdős--Rényi random graph model. Moreover, they also provided an asymptotically optimal compression algorithm that (asymptotically) achieves this entropy limit and runs in expectation in linear time. In this paper, we consider the Stochastic Block Models with an arbitrary number of parts. Indeed, we define a partitioned structural entropy for Stochastic Block Models, which generalizes the structural entropy for unlabeled graphs and encodes the partition information as well. We then compute the partitioned structural entropy of the Stochastic Block Models, and provide a compression scheme that asymptotically achieves this entropy limit.

preprint2020arXiv

Hamiltonicity in Cherry-quasirandom 3-graphs

We show that for any fixed $α>0$ , cherry-quasirandom 3-graphs of positive density and sufficiently large order $n$ with minimum vertex degree $α\binom n2$ have a tight Hamilton cycle. This solves a conjecture of Aigner-Horev and Levy.

preprint2020arXiv

Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu

A perfect $K_r$ -tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_r$ that together cover all the vertices in $G$ . In this paper we consider perfect $K_r$ -tilings in the setting of randomly perturbed graphs; a model introduced by Bohman, Frieze and Martin where one starts with a dense graph and then adds $m$ random edges to it. Specifically, given any fixed $0< α<1-1/r$ we determine how many random edges one must add to an $n$ -vertex graph $G$ of minimum degree $δ(G) \geq αn$ to ensure that, asymptotically almost surely, the resulting graph contains a perfect $K_r$ -tiling. As one increases $α$ we demonstrate that the number of random edges required `jumps' at regular intervals, and within these intervals our result is best-possible. This work therefore closes the gap between the seminal work of Johansson, Kahn and Vu (which resolves the purely random case, i.e., $α=0$ ) and that of Hajnal and Szemerédi (which demonstrates that for $α\geq 1-1/r$ the initial graph already houses the desired perfect $K_r$ -tiling).

Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs

For any $γ>0$ , Keevash, Knox and Mycroft constructed a polynomial-time algorithm to determine the existence of perfect matchings in any $n$ -vertex $k$ -uniform hypergraph whose minimum codegree is at least $n/k+γn$ . We prove a structure theorem that enables us to determine the existence of a perfect matching for any $k$ -uniform hypergraph with minimum codegree at least $n/k$ . This solves a problem of Karpiński, Ruciński and Szymańska completely. Our proof uses a lattice-based absorbing method.

Near Perfect Matchings in $k$ -uniform Hypergraphs II

Suppose $k\nmid n$ and $H$ is an $n$ -vertex $k$ -uniform hypergraph. A near perfect matching in $H$ is a matching of size $\lfloor n/k\rfloor$ . We give a divisibility barrier construction that prevents the existence of near perfect matchings in $H$ . This generalizes the divisibility barrier for perfect matchings. We give a conjecture on the minimum $d$ -degree threshold forcing a (near) perfect matching in $H$ which generalizes a well-known conjecture on perfect matchings. We also verify our conjecture in various cases. Our proof makes use of the lattice-based absorbing method that the author used recently to solve two other problems on matching and tilings for hypergraphs.

Perfect Matchings in Hypergraphs and the Erdős matching conjecture

We prove a new upper bound for the minimum $d$ -degree threshold for perfect matchings in $k$ -uniform hypergraphs when $d<k/2$ . As a consequence, this determines exact values of the threshold when $0.42k \le d < k/2$ or when $(k,d)=(12,5)$ or $(17,7)$ . Our approach is to give an upper bound on the Erdős Matching Conjecture and convert the result to the minimum $d$ -degree setting by an approach of Kühn, Osthus and Townsend. To obtain exact thresholds, we also apply a result of Treglown and Zhao.

The complexity of perfect matchings and packings in dense hypergraphs

Given two $k$ -graphs $H$ and $F$ , a perfect $F$ -packing in $H$ is a collection of vertex-disjoint copies of $F$ in $H$ which together cover all the vertices in $H$ . In the case when $F$ is a single edge, a perfect $F$ -packing is simply a perfect matching. For a given fixed $F$ , it is often the case that the decision problem whether an $n$ -vertex $k$ -graph $H$ contains a perfect $F$ -packing is NP-complete. Indeed, if $k \geq 3$ , the corresponding problem for perfect matchings is NP-complete whilst if $k=2$ the problem is NP-complete in the case when $F$ has a component consisting of at least $3$ vertices. In this paper we give a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect $F$ -packings is polynomial time solvable. We then give three applications of this tool: (i) Given $1\leq \ell \leq k-1$ , we give a minimum $\ell$ -degree condition for which it is polynomial time solvable to determine whether a $k$ -graph satisfying this condition has a perfect matching; (ii) Given any graph $F$ we give a minimum degree condition for which it is polynomial time solvable to determine whether a graph satisfying this condition has a perfect $F$ -packing; (iii) We also prove a similar result for perfect $K$ -packings in $k$ -graphs where $K$ is a $k$ -partite $k$ -graph. For a range of values of $\ell,k$ (i) resolves a conjecture of Keevash, Knox and Mycroft whilst (ii) answers a question of Yuster in the negative. In many cases our results are best possible in the sense that lowering the minimum degree condition means that the corresponding decision problem becomes NP-complete.

The i-V curve curve characteristics of burner-stabilized premixed flames: detailed and reduced models

The i-V curve describes the current drawn from a flame as a function of the voltage difference applied across the reaction zone. Since combustion diagnostics and flame control strategies based on electric fields depend on the amount of current drawn from flames, there is significant interest in modeling and understanding i-V curves. We implement and apply a detailed model for the simulation of the production and transport of ions and electrons in one dimensional premixed flames. An analytical reduced model is developed based on the detailed one, and analytical expressions are used to gain insight into the characteristics of the i-V curve for various flame configurations. In order for the reduced model to capture the spatial distribution of the electric field accurately, the concept of a dead zone region, where voltage is constant, is introduced, and a suitable closure for the spatial extent of the dead zone is proposed and validated. The results from the reduced modeling framework are found to be in good agreement with those from the detailed simulations. The saturation voltage is found to depend significantly on the flame location relative to the electrodes, and on the sign of the voltage difference applied. Furthermore, at sub-saturation conditions, the current is shown to increase linearly or quadratically with the applied voltage, depending on the flame location. These limiting behaviors exhibited by the reduced model elucidate the features of i-V curves observed experimentally. The reduced model relies on the existence of a thin layer where charges are produced, corresponding to the reaction zone of a flame. Consequently, the analytical model we propose is not limited to the study of premixed flames, and may be applied easily to others configurations, e.g. nonpremixed counterflow flames.

The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton--Milner family

The celebrated Erdős-Ko-Rado theorem determines the maximum size of a $k$ -uniform intersecting family. The Hilton-Milner theorem determines the maximum size of a $k$ -uniform intersecting family that is not a subfamily of the so-called Erdős-Ko-Rado family. In turn, it is natural to ask what the maximum size of an intersecting $k$ -uniform family that is neither a subfamily of the Erdős-Ko-Rado family nor of the Hilton-Milner family is. For $k\ge 4$ , this was solved (implicitly) in the same paper by Hilton-Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases $k\ge 3$ and characterize all extremal families achieving the extremal value.

Exact minimum codegree threshold for $K^- _4$ -factors

Given hypergraphs $F$ and $H$ , an $F$ -factor in $H$ is a set of vertex-disjoint copies of $F$ which cover all the vertices in $H$ . Let $K^- _4$ denote the $3$ -uniform hypergraph with $4$ vertices and $3$ edges. We show that for sufficiently large $n\in 4 \mathbb N$ , every $3$ -uniform hypergraph $H$ on $n$ vertices with minimum codegree at least $n/2-1$ contains a $K^- _4$ -factor. Our bound on the minimum codegree here is best-possible. It resolves a conjecture of Lo and Markström for large hypergraphs, who earlier proved an asymptotically exact version of this result. Our proof makes use of the absorbing method as well as a result of Keevash and Mycroft concerning almost perfect matchings in hypergraphs.

Forbidding Hamilton cycles in uniform hypergraphs

For $1\le d\le \ell< k$ , we give a new lower bound for the minimum $d$ -degree threshold that guarantees a Hamilton $\ell$ -cycle in $k$ -uniform hypergraphs. When $k\ge 4$ and $d< \ell=k-1$ , this bound is larger than the conjectured minimum $d$ -degree threshold for perfect matchings and thus disproves a well-known conjecture of Rödl and Ruciński. Our (simple) construction generalizes a construction of Katona and Kierstead and the space barrier for Hamilton cycles.

Minimum codegree threshold for $C_6^3$ -factors in $3$ -uniform Hypergraphs

Let $C_6^3$ be the 3-uniform hypergraph on $\{1,\dots, 6\}$ with edges $123, 345,561$ , which can be seen as the triangle in 3-uniform hypergraphs. For sufficiently large $n$ divisible by 6, we show that every $n$ -vertex 3-uniform hypergraph $H$ with minimum codegree at least $n/3$ contains a $C_6^3$ -factor, i.e., a spanning subhypergraph consisting of vertex-disjoint copies of $C_6^3$ . The minimum codegree condition is best possible. This improves the asymptotical result obtained by Mycroft and answers a question of Rödl and Ruciński exactly.

Minimum codegree threshold for Hamilton l-cycles in k-uniform hypergraphs

For $1\le \ell<k/2$ , we show that for sufficiently large $n$ , every $k$ -uniform hypergraph on $n$ vertices with minimum codegree at least $\frac n{2 (k-\ell)}$ contains a Hamilton $\ell$ -cycle. This codegree condition is best possible and improves on work of Hàn and Schacht who proved an asymptotic result.