
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 quasirandom 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 blowup 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$edgecolouring $\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 RamseyTur\'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)$ randomlychosen
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$edgecoloring} 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$edgecoloring. 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{n1}{k1} +
\lfloor\frac{n1}{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, BangJensen 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
trianglefree 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 quasirandom
$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 (1o(1)) e(G)$. Then $H_1,\dots,H_s$
can be packed edgedisjointly 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 superregular 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 blowup lemma of Koml\'os, S\'ark\H{o}zy and
Szemer\'edi to the setting of approximate decompositions.

In conventional chemisorption model, the dband center theory (augmented
sometimes with the upper edge of dband for imporved accuarcy) plays a central
role in predicting adsorption energies and catalytic activity as a function of
dband 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 dband width of the muffintin
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 dband 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 costeffective 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)){{n1}\choose{k1}}$ 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 ${{n1} \choose {k1}}$, 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{n2}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
$t1$ 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 $ {{nt}
\choose {kt}}$ 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 nonadjacent vertices of degree $\Delta(T)$;
\Delta(T)+1, & otherwise.
$$ Moreover, the proof yields a polynomialtime 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)}$.