Search

A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected $2$-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem.

It is well-known that every tournament contains a Hamilton path, and every strongly connected tournament contains a Hamilton cycle. This paper establishes transversal generalizations of these classical results. For a collection $\mathbf{T}=\{T_1,\dots,T_m\}$ of not-necessarily distinct tournaments on a common vertex set $V$, an $m$-edge directed graph $\mathcal{D}$ with vertices in $V$ is called a $\mathbf{T}$-transversal if there exists a bijection $\phi\colon E(\mathcal{D})\to [m]$ such that $e\in E(T_{\phi(e)})$ for all $e\in E(\mathcal{D})$. We prove that for sufficiently large $m$ with $m=|V|-1$, there exists a $\mathbf{T}$-transversal Hamilton path. Moreover, if $m=|V|$ and at least $m-1$ of the tournaments $T_1,\ldots,T_m$ are assumed to be strongly connected, then there is a $\mathbf{T}$-transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub $\mathbf{H}$-partition.

Given a collection $\mathcal{G}=(G_1,\dots, G_h)$ of graphs on the same vertex set $V$ of size $n$, an $h$-edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow [h]$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The conditions on the minimum degree $\delta(\mathcal{G})=\min_{i\in[h]}\{ \delta(G_i)\}$ for finding a spanning $\mathcal{G}$-transversal isomorphic to a graph $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$-factor, a spanning tree with maximum degree $o(n/\log n)$ and a power of a Hamilton cycle, etc. In this paper, we determined the asymptotically tight threshold on $\delta(\mathcal{G})$ for finding a $\mathcal{G}$-transversal isomorphic to $H$ when $H$ is a general $n$-vertex graph with bounded maximum degree and $o(n)$-bandwidth. This provides a transversal generalization of the celebrated Bandwidth theorem by B\"ottcher, Schacht and Taraz.

We investigate quiver representations over $\mathbb{F}_1$. Coefficient quivers are combinatorial gadgets equivalent to $\mathbb{F}_1$-representations of quivers. We focus on the case when the quiver $Q$ is a pseudotree. For such quivers, we first use the notion of coefficient quivers to provide a complete classification of asymptotic behaviors of indecomposable representations over $\mathbb{F}_1$. Then, we prove some fundamental structural results about the Lie algebras associated to pseudotrees. Finally, we construct examples of $\mathbb{F}_1$-representations $M$ of a quiver $Q$ by using coverings, under which the Euler characteristics of the quiver Grassmannians $\textrm{Gr}^Q_{\underline{d}}(M)$ can be computed in a purely combinatorial way., Comment: 26 pages

In 1975, Erd\H{o}s asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders., Comment: 10 pages, 2 figures

The oriented Ramsey number $\vec{r}(H)$ for an acyclic digraph $H$ is the minimum integer $n$ such that any $n$-vertex tournament contains a copy of $H$ as a subgraph. We prove that the $1$-subdivision of the $k$-vertex transitive tournament $H_k$ satisfies $\vec{r}(H_k)= O(k^2\log\log k)$. This is tight up to multiplicative $\log\log k$-term. We also show that if $T$ is an $n$-vertex tournament with $\Delta^+(T)-\delta^+(T)= O(n/k) - k^2$, then $T$ contains a $1$-subdivision of $\vec{K}_k$, a complete $k$-vertex digraph with all possible $k(k-1)$ arcs. This is tight up to multiplicative constant.

A celebrated theorem of Pippenger, and Frankl and R\"odl states that every almost-regular, uniform hypergraph $\mathcal{H}$ with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a ``conflict-free'' matching, where conflicts are encoded via a collection $\mathcal{C}$ of subsets $C\subseteq E(\mathcal{H})$. We say that a matching $\mathcal{M}\subseteq E(\mathcal{H})$ is conflict-free if $\mathcal{M}$ does not contain an element of $\mathcal{C}$ as a subset. Under natural assumptions on $\mathcal{C}$, we prove that $\mathcal{H}$ has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called ``high-girth'' Steiner systems. Our main tool is a random greedy algorithm which we call the ``conflict-free matching process''., Comment: 58 pages

Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and Rödl conjectured that for any given $μ>0$, there exists $n_0$ such that the following holds. Every $n$-vertex Steiner triple system contains all hypertrees with at most $(1-μ)n$ vertices whenever $n\geq n_0$. We prove this conjecture., 19 pages, 2 figures

Let $f^{(r)}(n;s,k)$ be the maximum number of edges of an $r$-uniform hypergraph on $n$ vertices not containing a subgraph with $k$ edges and at most $s$ vertices. In 1973, Brown, Erdős and Sós conjectured that the limit $$\lim_{n\to \infty} n^{-2} f^{(3)}(n;k+2,k)$$ exists for all $k$ and confirmed it for $k=2$. Recently, Glock showed this for $k=3$. We settle the next open case, $k=4$, by showing that $f^{(3)}(n;6,4)=\left(\frac{7}{36}+o(1)\right)n^2$ as $n\to\infty$. More generally, for all $k\in \{3,4\}$, $r\ge 3$ and $t\in [2,r-1]$, we compute the value of the limit $\lim_{n\to \infty} n^{-t}f^{(r)}(n;k(r-t)+t,k)$, which settles a problem of Shangguan and Tamo., 11 pages, 2 figures

We prove that every properly edge-colored $n$-vertex graph with average degree at least $100(\log n)^2$ contains a rainbow cycle, improving upon $(\log n)^{2+o(1)}$ bound due to Tomon. We also prove that every properly colored $n$-vertex graph with at least $10^5 k^2 n^{1+1/k}$ edges contains a rainbow $2k$-cycle, which improves the previous bound $2^{ck^2}n^{1+1/k}$ obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erd\H{o}s--Simonovits supersaturation theorem for even cycles, which may be of independent interest.

For a given graph $H$, its subdivisions carry the same topological structure. The existence of $H$-subdivisions within a graph $G$ has deep connections with topological, structural and extremal properties of $G$. One prominent examples of such connections, due to Bollob\'{a}s and Thomason and independently Koml\'os and Szemer\'edi, asserts that the average degree of $G$ being $d$ ensures a $K_{\Omega(\sqrt{d})}$-subdivision in $G$. Although this square-root bound is best possible, various results showed that much larger clique subdivisions can be found in a graph from many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. This reveals the unifying cause underpinning all those improvements for various classes of graphs studied. Roughly speaking, when embedding subdivisions, natural space constraints arise; and such space constraints can be measured via crux. Our main result gives an asymptotically optimal bound on the size of a largest clique subdivision in a generic graph $G$, which is determined by both its average degree and its crux size. As corollaries, we obtain (1) a characterisation of extremal graphs for which the square-root bound above is tight: they are essentially disjoint union of graphs each of which has the crux size linear in $d$; (2) a unifying approach to find a clique subdivision of almost optimal size in graphs which does not contain a fixed bipartite graph as a subgraph; (3) and that the clique subdivision size in random graphs $G(n,p)$ witnesses a dichotomy: when $p = \omega(n^{-1/2})$, the barrier is the space, while when $p=o( n^{-1/2})$, the bottleneck is the density., Comment: 37 pages, 2 figures

This article summarizes technical advances contained in the fifth major release of the Q-Chem quantum chemistry program package, covering developments since 2015. A comprehensive library of exchange-correlation functionals, along with a suite of correlated many-body methods, continues to be a hallmark of the Q-Chem software. The many-body methods include novel variants of both coupled-cluster and configuration-interaction approaches along with methods based on the algebraic diagrammatic construction and variational reduced density-matrix methods. Methods highlighted in Q-Chem 5 include a suite of tools for modeling core-level spectroscopy, methods for describing metastable resonances, methods for computing vibronic spectra, the nuclear-electronic orbital method, and several different energy decomposition analysis techniques. High-performance capabilities including multithreaded parallelism and support for calculations on graphics processing units are described. Q-Chem boasts a community of well over 100 active academic developers, and the continuing evolution of the software is supported by an "open teamware" model and an increasingly modular design.

Let the kissing number $K(d)$ be the maximum number of non-overlapping unit balls in $\mathbb R^d$ that can touch a given unit ball. Determining or estimating the number $K(d)$ has a long history, with the value of $K(3)$ being the subject of a famous discussion between Gregory and Newton in 1694. We prove that, as the dimension $d$ goes to infinity, $$ K(d)\ge (1+o(1)){\frac{\sqrt{3\pi}}{4\sqrt2}}\,\log\frac{3}{2}\cdot d^{3/2}\cdot \Big(\frac{2}{\sqrt{3}}\Big)^{d}, $$ thus improving the previously best known bound of Jenssen, Joos and Perkins by a factor of $\log(3/2)/\log(9/8)+o(1)=3.442...$. Our proof is based on the novel approach from Jenssen, Joos and Perkins that uses the hard core sphere model of an appropriate fugacity. Similar constant-factor improvements in lower bounds are also obtained for general spherical codes, as well as for the expected density of random sphere packings in the Euclidean space $\mathbb R^d$., Comment: 20 pages

We prove that for every integer $k$, there exists $\varepsilon > 0$ such that for every n-vertex graph $G$ with no pivot-minor isomorphic to $C_k$, there exist disjoint sets $A,B \subseteq V(G)$ such that $|A|,|B| \geq \varepsilon n$, and $A$ is either complete or anticomplete to $B$. This proves the analog of the Erd��s-Hajnal conjecture for the class of graphs with no pivot-minor isomorphic to $C_k$., 13 pages, 4 figures

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases., Comment: 19 pages

본 연구는 지난 1999년도부터 시작되어 현재까지 수행되고 있는 예비타당성조사에서 중요하게 고려되고 있는 요인이 무엇인지 살펴보는 것을 목적으로 한다. 분석결과, AHP평점에 영향을 미치는 요인은 B/C, 경제성 분석 가중치, 지역균형발전 가중치, 부정적인 특수평가항목, 사업계획 변경 여부, 집권당의 성향 등인 것으로 나타났다. 또한 분석과정에서 AHP활용의 적합성에 대해서도 재검토의 여지가 있을 것으로 판단하여 이에 대해 제언하였다. 본 연구는 예비타당성조사가 여러 항목을 아우르는 평가를 수행하고 있는지 여부를 확인할 수 있는 계기를 마련하고, 예비타당성조사의 종합판단을 위해 고안된 AHP방법론이 적합한 것인가에 대한 시사점을 제안하는데 의의를 가진다.

Given graphs $H_1,\ldots, H_k$, a graph $G$ is $(H_1,\ldots, H_k)$-free if there is a $k$-edge-colouring $��: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��n 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,��n)$ for $s\in\{3,4,5\}$ and sufficiently small $��$, confirming a conjecture of Erd��s and S��s from 1979. It is known that $\textrm{RT}(n,K_8,f(n))$ has a phase transition at $f(n)=��(\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., 20 pages, 2 figures, 2 pages appendix

The extremal number $\mathrm{ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with $\mathrm{ex}(n , F) = ��(n^r)$. Several decades ago, Erd��s and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1, \frac{7}{5}, 2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$. In this paper, we make progress on the conjecture of Erd��s and Simonovits. First, we show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

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.

Koml��s 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., 33 pages, to appear in Proceedings of the London Mathematical Society

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., Comment: Under review and including Electronic Supplementary Information (ESI)

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., Comment: Final version, to appear in Transactions of the American Mathematical Society

This study describes the tensile test results of AISI type 304 deformed at room and elevated temperatures. It has been known that the normal distribution fits well with the strength of typical structural materials. The Weibull distribution has many characteristics in the reliability design. In this paper, we showed that the Weibull distribution can be used to describe the scattering of strength data as well as normal distribution by testing goodness of fit. It is found that the parameters of Weibull distribution have decreasing tendency for temperature rise and the coefficient of variation has increasing tendency for temperature rise.