Computability of graphs

We consider topological pairs $(A,B)$, $B\subseteq A$, which have computable type, which means that they have the following property: if X is a computable topological space and $f:A\to X$ a topological imbedding such that $f(A)$ and $f(B)$ are semicomputable sets in X, then $f(A)$ is a computable set in X. It is known, e.g., that $(M,\partial M)$ has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph G a discrete subspace E so that $(G,E)$ has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.     

A characterization of (4,2)-choosable graphs

A graph $G$ is $\left(a,b\right)$-choosable if given any list assignment $L$ with $\text{◂=▸}\mid L\left(v\right)\mid =a$ for each $\text{◂+▸}v\in V\left(G\right)$ there exists a function $\phi$ such that $\text{◂⊆▸}\phi \left(v\right)\subseteq L\left(v\right)$ and $\text{◂=▸}\mid \phi \left(v\right)\mid =b$ for all $\text{◂+▸}v\in V\left(G\right)$, and whenever vertices $x$ and $y$ are adjacent $\text{◂+▸}\phi \left(x\right)\cap \phi \left(y\right)=\varnothing$. Meng, Puleo, and Zhu conjectured a characterization of (4,2)-choosable graphs. We prove their conjecture.     

Higher dimensional Calabi–Yau manifolds of Kummer type

Based on Cynk–Hulek method from [7] we construct complex Calabi–Yau varieties of arbitrary dimensions using elliptic curves with an automorphism of order 6. Also we give formulas for Hodge numbers of varieties obtained from that construction. We shall generalize the result of [11] to obtain arbitrarily dimensional Calabi–Yau manifolds which are Zariski in any characteristic $p\not\equiv \text{◂⋅▸}1(\mathrm{mod}12)$.     

Graph homomorphism reconfiguration and frozen H-colorings

We say that a graph $F$ strongly arrows a pair of graphs $\left(G,H\right)$ and write $\text{◂→▸}F\stackrel{\text{ind}}{\to }\left(G,H\right)$ if any coloring of its edges with red and blue leads to either a red $G$ or a blue $H$ appearing as induced subgraphs of $F$. The induced Ramsey number, $\text{◂...▸}\text{IR}\left(G,H\right)$, is defined as $\text{◂lim▸}\min \text{◂{}▸}\{|V\left(F\right)|:\text{◂→▸}F\stackrel{\text{ind}}{\to }\left(G,H\right)\}$. We consider the connection between the induced Ramsey number for a pair of two connected graphs $\text{◂...▸}\text{IR}\left(G,H\right)$ and the induced Ramsey number for multiple copies of these graphs $\text{IR}\text{◂()▸}\left(sG,tH\right)$, where $xG$ denotes the pairwise vertex-disjoint union of $x$ copies of $G$. It is easy to see that if $\text{◂→▸}F\stackrel{\text{ind}}{\to }\left(G,H\right)$, then $\text{◂⋅▸}\left(s+t-1\right)F\stackrel{\text{ind}}{\to }\text{◂()▸}\left(sG,tH\right)$. This implies that $$\text{◂...▸}\text{IR}\text{◂≤▸}\text{◂()▸}\left(sG,tH\right)\le \left(s+t-1\right)\text{IR}\left(G,H\right).$$ For several specific graphs, such as a path on three vertices vs a complete multipartite graph, a matching vs a complete graph, or a matching vs another matching, it is known that the above inequality is tight. On the other hand, the inequality is also strict for some graphs. However, even in the simplest case when $H$ is an edge and $t=2$, it is not known for what $G$ and for what $s$ the above inequality is tight. We show that it is tight if $G$ is connected and $s$ is at least as large as the order of $G$. In addition, we make further progress in determining induced Ramsey numbers for multiple copies of graphs, such as paths and triangles.