• We prove that if $T_1,\dots, T_n$ is a sequence of bounded degree trees so that $T_i$ has $i$ vertices, then $K_n$ has a decomposition into $T_1,\dots, T_n$. This shows that the tree packing conjecture of Gy\'arf\'as and Lehel from 1976 holds for all bounded degree trees (in fact, we can allow the first $o(n)$ trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemer\'{e}di's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions.
  • Given graphs $H_1,\ldots, H_k$, a graph $G$ is $(H_1,\ldots, H_k)$-free if there is a $k$-edge-colouring $\phi:E(G)\rightarrow [k]$ with no monochromatic copy of $H_i$ with edges of colour $i$ for each $i\in[k]$. Fix a function $f(n)$, the Ramsey-Tur\'an function $\textrm{RT}(n,H_1,\ldots,H_k,f(n))$ is the maximum number of edges in an $n$-vertex $(H_1,\ldots,H_k)$-free graph with independence number at most $f(n)$. We determine $\textrm{RT}(n,K_3,K_s,\delta n)$ for $s\in\{3,4,5\}$ and sufficiently small $\delta$, confirming a conjecture of Erd\H{o}s and S\'os from 1979. It is known that $\textrm{RT}(n,K_8,f(n))$ has a phase transition at $f(n)=\Theta(\sqrt{n\log n})$. However, the values of $\textrm{RT}(n,K_8, o(\sqrt{n\log n}))$ was not known. We determined this value by proving $\textrm{RT}(n,K_8,o(\sqrt{n\log n}))=\frac{n^2}{4}+o(n^2)$, answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings.
  • A classical result of Koml\'os, S\'ark\"ozy and Szemer\'edi states that every $n$-vertex graph with minimum degree at least $(1/2+ o(1))n$ contains every $n$-vertex tree with maximum degree $O(n/\log{n})$ as a subgraph, and the bounds on the degree conditions are sharp. On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every $n$-vertex graph $G_\alpha$ with minimum degree at least $\alpha n$ for any fixed $\alpha >0$ and every $n$-vertex tree $T$ with bounded maximum degree, one can still find a copy of $T$ in $G_\alpha$ with high probability after adding $O(n)$ randomly-chosen edges to $G_\alpha$. We extend their results to trees with unbounded maximum degree. More precisely, for a given $n^{o(1)}\leq \Delta\leq cn/\log n$ and $\alpha>0$, we determine the precise number (up to a constant factor) of random edges that we need to add to an arbitrary $n$-vertex graph $G_\alpha$ with minimum degree $\alpha n$ in order to guarantee a copy of any fixed $n$-vertex tree $T$ with maximum degree at most~$\Delta$ with high probability.
  • K\"uhn, Osthus, and Townsend asked whether there exists a constant $C$ such that every strongly $Ct$-connected tournament contains all possible $1$-factors with at most $t$ components. We answer this question in the affirmative. This is best possible up to constant. In addition, we can ensure that each cycle in the $1$-factor contains a prescribed vertex. Indeed, we derive this result from a more general result on partitioning digraphs which are close to semicomplete. More precisely, we prove that there exists a constant $C$ such that for any $k\geq 1$, if a strongly $Ck^4t$-connected digraph $D$ is close to semicomplete, then we can partition $D$ into $t$ strongly $k$-connected subgraphs with prescribed sizes, provided that the prescribed sizes are $\Omega(n)$. This result improves the earlier result of K\"uhn, Osthus, and Townsend. Here, the condition of connectivity being linear in $t$ is best possible, and the condition of prescribed size being $\Omega(n)$ is also best possible.
  • A {\em strong $k$-edge-coloring} of a graph $G$ is a mapping from $E(G)$ to $\{1,2,\ldots,k\}$ such that every two adjacent edges or two edges adjacent to the same edge receive distinct colors. The {\em strong chromatic index} $\chi_s'(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ admits a strong $k$-edge-coloring. We give bounds on $\chi_s'(G)$ in terms of the maximum degree $\Delta(G)$ of a graph $G$. when $G$ is sparse, namely, when $G$ is $2$-degenerate or when the maximum average degree ${\rm Mad}(G)$ is small. We prove that the strong chromatic index of each $2$-degenerate graph $G$ is at most $5\Delta(G) +1$. Furthermore, we show that for a graph $G$, if ${\rm Mad}(G)< 8/3$ and $\Delta(G)\geq 9$, then $\chi_s'(G)\leq 3\Delta(G) -3$ (the bound $3\Delta(G) -3$ is sharp) and if ${\rm Mad}(G)<3$ and $\Delta(G)\geq 7$, then $\chi_s'(G)\leq 3\Delta(G)$ (the restriction ${\rm Mad}(G)<3$ is sharp).
  • Let $k\ge 3$ be an odd integer and let $n$ be a sufficiently large integer. We prove that the maximum number of edges in an $n$-vertex $k$-uniform hypergraph containing no $2$-regular subgraphs is $\binom{n-1}{k-1} + \lfloor\frac{n-1}{k} \rfloor$, and the equality holds if and only if $H$ is a full $k$-star with center $v$ together with a maximal matching omitting $v$. This verifies a conjecture of Mubayi and Verstra\"{e}te.
  • In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + 750k^2\log(k+1)$ arcs.
  • The \textit{$r$-dynamic choosability} of a graph $G$, written ${\rm ch}_r(G)$, is the least $k$ such that whenever each vertex is assigned a list of at least $k$ colors a proper coloring can be chosen from the lists so that every vertex $v$ has at least $\min\{d_G(v),r\}$ neighbors of distinct colors. Let ${\rm ch}(G)$ denote the choice number of $G$. In this paper, we prove ${\rm ch}_r(G)\leq (1+o(1)){\rm ch}(G)$ when $\frac{\Delta(G)}{\delta(G)}$ is bounded. We also show that there exists a constant $C$ such that for the random graph $G=G(n,p)$ with $\frac{2}{n}<p\leq \frac{1}{2}$, it holds that ${\rm ch}_2(G)\leq {\rm ch}(G) + C$, asymptotically almost surely. Also if $G$ is triangle-free regualr graph, then ${\rm ch}_2(G)\leq {\rm ch}(G)+86$ holds.
  • We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to longstanding decomposition problems. For instance, our results imply the following. Let $G$ be a quasi-random $n$-vertex graph and suppose $H_1,\dots,H_s$ are bounded degree $n$-vertex graphs with $\sum_{i=1}^{s} e(H_i) \leq (1-o(1)) e(G)$. Then $H_1,\dots,H_s$ can be packed edge-disjointly into $G$. The case when $G$ is the complete graph $K_n$ implies an approximate version of the tree packing conjecture of Gy\'arf\'as and Lehel for bounded degree trees, and of the Oberwolfach problem. We provide a more general version of the above approximate decomposition result which can be applied to super-regular graphs and thus can be combined with Szemer\'edi's regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Koml\'os, S\'ark\H{o}zy and Szemer\'edi to the setting of approximate decompositions.
  • In conventional chemisorption model, the d-band center theory (augmented sometimes with the upper edge of d-band for imporved accuarcy) plays a central role in predicting adsorption energies and catalytic activity as a function of d-band center of the solid surfaces, but it requires density functional calculations that can be quite costly for large scale screening purposes of materials. In this work, we propose to use the d-band width of the muffin-tin orbital theory (to account for local coordination environment) plus electronegativity (to account for adsorbate renormalization) as a simple set of alternative descriptors for chemisorption, which do not demand the ab initio calculations. This pair of descriptors are then combined with machine learning methods, namely, artificial neural network (ANN) and kernel ridge regression (KRR), to allow large scale materials screenings. We show, for a toy set of 263 alloy systems, that the CO adsorption energy can be predicted with a remarkably small mean absolute deviation error of 0.05 eV, a significantly improved result as compared to 0.13 eV obtained with descriptors including costly d-band center calculations in literature. We achieved this high accuracy by utilizing an active learning algorithm, without which the accuracy was 0.18 eV otherwise. As a practical application of this machine, we identified Cu3Y@Cu as a highly active and cost-effective electrochemical CO2 reduction catalyst to produce CO with the overpotential 0.37 V lower than Au catalyst.
  • We provide a combinatorial characterization of all testable properties of $k$-graphs (i.e. $k$-uniform hypergraphs). Here, a $k$-graph property $\mathbf{P}$ is testable if there is a randomized algorithm which makes a bounded number of edge queries and distinguishes with probability $2/3$ between $k$-graphs that satisfy $\mathbf{P}$ and those that are far from satisfying $\mathbf{P}$. For the $2$-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. Our results for the $k$-graph setting are in contrast to those of Austin and Tao, who showed that for the somewhat stronger concept of local repairability, the testability results for graphs do not extend to the $3$-graph setting.
  • Koml\'os conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify.
  • We prove that for every integer $r\geq 2$, an $n$-vertex $k$-uniform hypergraph $H$ containing no $r$-regular subgraphs has at most $(1+o(1)){{n-1}\choose{k-1}}$ edges if $k\geq r+1$ and $n$ is sufficiently large. Moreover, if $r\in\{3,4\}$, $r\mid k$ and $k,n$ are both sufficiently large, then the maximum number of edges in an $n$-vertex $k$-uniform hypergraph containing no $r$-regular subgraphs is exactly ${{n-1} \choose {k-1}}$, with equality only if all edges contain a specific vertex $v$. We also ask some related questions.
  • Given a graph $G$, the matching number of $G$, written $\alpha'(G)$, is the maximum size of a matching in $G$, and the fractional matching number of $G$, written $\alpha'_f(G)$, is the maximum size of a fractional matching of $G$. In this paper, we prove that if $G$ is an $n$-vertex connected graph that is neither $K_1$ nor $K_3$, then $\alpha'_f(G)-\alpha'(G) \le \frac{n-2}6$ and $\frac{\alpha'_f(G)}{\alpha'(G)} \le \frac{3n}{2n+2}$. Both inequalities are sharp, and we characterize the infinite family of graphs where equalities hold.
  • Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+1}$ minor, then its vertex set $V(G)$ can be partitioned into $t$ stable sets. This is still open, but we prove under the same hypotheses that $V(G)$ can be partitioned into $t$ sets $X_1,\ldots, X_t$, such that for $1\le i\le t$, the subgraph induced on $X_i$ has maximum degree at most a function of $t$. This is sharp, in that the conclusion becomes false if we ask for a partition into $t-1$ sets with the same property.
  • We determine, for all $k\geq 6$, the typical structure of graphs that do not contain an induced $2k$-cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$-cycle or without an induced $10$-cycle.
  • We show that if $T$ is a strongly $10^9k^6\log(2k)$-connected tournament, there exists a partition $A, B$ of $V(T)$ such that each of $T[A]$, $T[B]$ and $T[A,B]$ is strongly $k$-connected. This provides tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs.
  • A family $\mathcal{F}$ is $t$-$\it{intersecting}$ if any two members have at least $t$ common elements. Erd\H os, Ko, and Rado proved that the maximum size of a $t$-intersecting family of subsets of size $k$ is equal to $ {{n-t} \choose {k-t}}$ if $n\geq n_0(k,t)$. Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing $t$-intersecting families for all $t \geq 1$. In 2004, Talbot generalized Bollob\'{a}s's Two Families Theorem to $t$-intersecting families. In this paper, we proved a slight generalization of Talbot's result by using the probabilistic method.
  • An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. A $2$-matching is also called an induced matching. In this paper, we estimate the maximum number of $r$-matchings in a tree of fixed order. We also prove that the $n$-vertex path has the maximum number of induced matchings among all $n$-vertex trees.
  • A harmonious coloring of $G$ is a proper vertex coloring of $G$ such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of $G$, $h(G)$, is the minimum number of colors needed for a harmonious coloring of $G$. We show that if $T$ is a forest of order $n$ with maximum degree $\Delta(T)\geq \frac{n+2}{3}$, then $$h(T)= \Delta(T)+2, & if $T$ has non-adjacent vertices of degree $\Delta(T)$; \Delta(T)+1, & otherwise. $$ Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest.
  • A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,..., k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The {\it $t$-tone chromatic number} of $G$, denoted $\tau_t(G)$, is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. Bickle and Phillips showed that always $\tau_2(G) \le [\Delta(G)]^2 + \Delta(G)$, but conjectured that in fact $\tau_2(G) \le 2\Delta(G) + 2$; we confirm this conjecture when $\Delta(G) \le 3$ and also show that always $\tau_2(G) \le \ceil{(2 + \sqrt{2})\Delta(G)}$. For general $t$ we prove that $\tau_t(G) \le (t^2+t)\Delta(G)$. Finally, for each $t\ge 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{\Delta(T)} \le \tau_t(T) \le c_2\sqrt{\Delta(T)}$.