Search

Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X\cap Y=\varnothing$ and there is no edge in $G$ with an end in $X$ and an end in $Y$. We prove that every graph $G$ of sufficiently large treewidth contains two anticomplete sets of vertices each inducing a subgraph of large treewidth unless $G$ contains, as an induced subgraph, a highly structured graph of large treewidth that is an obvious counterexample to this statement. These are: complete graphs, complete bipartite graphs and "interrupted $s$-constellations." The latter is a slightly adjusted version of a well-known construction by Bonamy et al., Comment: arXiv admin note: text overlap with arXiv:2410.16495

Static and dynamic properties of magnetically soft amorphous ferromagnets have been studied analytically and numerically within random-field and random-anisotropy models. External field and coherent anisotropy that are weak compared to their random counterparts are sufficient to bring the magnet close to saturation. The scaling of spin-spin correlations in this regime is computed, and its dependence on parameters is confirmed by Monte Carlo simulation. We show that near the ferromagnetic resonance, the spin excitations are damped and spatially localized due to randomness even close to saturation. On increasing the strength of randomness, the localization length goes down in accordance with theoretical expectations, while the damping of spin excitations goes up., Comment: 10 PR pages, 6 figure captions

We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large constellation; that is, a complete bipartite induced minor model such that on one side of the bipartition, each branch set is a singleton, and on the other side, each branch set induces a path. We further refine this theorem by characterizing the unavoidable induced subgraphs of large constellations as two types of highly structured constellations. These results will be key ingredients in several forthcoming papers of this series.

We introduce Pixtral-12B, a 12--billion-parameter multimodal language model. Pixtral-12B is trained to understand both natural images and documents, achieving leading performance on various multimodal benchmarks, surpassing a number of larger models. Unlike many open-source models, Pixtral is also a cutting-edge text model for its size, and does not compromise on natural language performance to excel in multimodal tasks. Pixtral uses a new vision encoder trained from scratch, which allows it to ingest images at their natural resolution and aspect ratio. This gives users flexibility on the number of tokens used to process an image. Pixtral is also able to process any number of images in its long context window of 128K tokens. Pixtral 12B substanially outperforms other open models of similar sizes (Llama-3.2 11B \& Qwen-2-VL 7B). It also outperforms much larger open models like Llama-3.2 90B while being 7x smaller. We further contribute an open-source benchmark, MM-MT-Bench, for evaluating vision-language models in practical scenarios, and provide detailed analysis and code for standardized evaluation protocols for multimodal LLMs. Pixtral-12B is released under Apache 2.0 license.

The fork is the tree obtained from the claw $K_{1,3}$ by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs., Comment: This is an old paper. It was published in 2020 in Discrete Math where it was awarded Editors' choice

Recently observed scaling in the random-anisotropy model of amorphous or sintered ferromagnets is derived by an alternative method and extended for studying the dynamical properties in terms of the Landau-Lifshitz equations for spin blocks. Switching to the rescaled exchange and anisotropy constants allows one to investigate the dynamics by using a reduced number of variables, which greatly speeds up computations. The proposed dynamical scaling is applied to the problem of microwave absorption by a random anisotropy magnet. The equivalence of the rescaled model to the original atomic model is confirmed numerically. The method is proposed as a powerful tool in studying static and dynamic properties of systems with quenched randomness., Comment: 7 pages, 3 figure captions (5 figures)

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c>0 such that for every integer n>1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most c log^10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is even-hole-free.

We prove that for every $t\in \mathbb{N}$ there exists $\tau=\tau(t)\in \mathbb{N}$ such that every (theta, prism, $K_{1,t}$)-free graph has tree independence number at most $\tau$ (where we allow "prisms" to have one path of length zero).

Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any $n$-vertex graph with independence number $\alpha$ without $bK_a$ as an induced subgraph has at most $n^{O(1)} \cdot \alpha^{O(\alpha)}$ independent sets. This substantially improves the trivial upper bound of $n^{\alpha},$ whenever $\alpha \le n^{o(1)}$ and gives a characterization of graphs forbidding of which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with $\alpha^{\Omega(\alpha)}$ independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to $n^{O(1)} \cdot 2^{O(\alpha)}$ which is tight up to a constant factor in the exponent.

We report comprehensive Monte-Carlo studies of the melting of skyrmion lattices in systems of small, medium, and large sizes with the number of skyrmions ranging from $10^{3}$ to over $10^{5}$. Large systems exhibit hysteresis similar to that observed in real experiments on the melting of skyrmion lattices. For sufficiently small systems which achieve thermal equilibrium, a fully reversible sharp solid-liquid transition on temperature with no intermediate hexatic phase is observed. A similar behavior is found on changing the magnetic field that provides the control of pressure in the skyrmion lattice. We find that on heating the melting transition occurs via a formation of grains with different orientations of hexagonal axes. On cooling, the fluctuating grains coalesce into larger clusters until a uniform orientation of hexagonal axes is slowly established. The observed scenario is caused by collective effects involving defects and is more complex than a simple picture of a transition driven by the unbinding and annihilation of dislocation and disclination pairs., Comment: 15 pages PR style, 26 figures (16 figure captions)

We construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique number, the construction can be adjusted to make the dependance grow arbitrarily. Some of these classes provide counter-examples to several conjectures. In particular, the construction includes hereditary classes of graphs whose treewidth is bounded by a function of the clique number while the tree-independence number is unbounded, thus disproving a conjecture of Dallard, Milani\v{c} and \v{S}torgel [Treewidth versus clique number. II. Tree-independence number. Journal of Combinatorial Theory, Series B, 164:404-442, 2024.]. The construction can be further adjusted to provide, for any fixed integer $c$, graphs of arbitrarily large treewidth that contain no $K_c$-free graphs of high treewidth, thus disproving a conjecture of Hajebi [Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth, arXiv:2401.01299, 2024]., Comment: 22 pages, 4 figures

We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains $K_{3, 4}$ as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a \emph{theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$, each of length at least two, such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number, or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels)., Comment: 25 pages, 12 figures

A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We prove that 3PC-free graphs have poly-logarithmic tree-independence number. More explicitly, we show that there exists a constant $c$ such that every $n$-vertex 3PC-free graph graph has a tree decomposition in which every bag has stability number at most $c (\log n)^2$. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is 3PC-free.

We report Monte-Carlo studies of the orientational order and melting of a 2D skyrmion lattice containing more than one million spins. Two models have been investigated, a microscopic model of lattice spins with Dzyaloshinskii-Moryia interaction that possesses skyrmions, and the model in which skyrmions are treated as point particles with repulsive interaction derived from a spin model. They produce similar results. The skyrmion lattice exhibits a sharp one-step transition between solid and liquid phases on temperature and the magnetic field. This solid-liquid transition is characterized by the kink in the magnetization. The field-temperature phase diagram is computed. We show that the application of the field gradient to a 2D system of skyrmions produces a solid-liquid interface that must be possible to observe in experiments., Comment: 11 pages, 14 figures

We prove that for every integer $t\geq 1$ there exists an integer $c_t\geq 1$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\log{n}$. This resolves a conjecture of Sintiari and Trotignon, who also proved that the logarithmic bound is asymptotically best possible. It follows that several \textsf{NP}-hard problems such as \textsc{Stable Set}, \textsc{Vertex Cover}, \textsc{Dominating Set} and \textsc{Coloring} admit polynomial-time algorithms on this class of graphs. As a consequence, for every positive integer $r$, $r$-{\sc Coloring} can be solved in polynomial time on even-hole-free graphs without any assumptions on clique size. As part of the proof, we show that there is an integer $d$ such that every even-hole-free graph has a balanced separator which is contained in the (closed) neighborhood of at most $d$ vertices. This is of independent interest; for instance, it implies the existence of efficient approximation algorithms for certain \textsf{NP}-hard problems while restricted to the class of all even-hole-free graphs., Comment: arXiv admin note: text overlap with arXiv:2307.13684

The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, we utilize tools from group theory and ring theory to study this problem when the network is a Cayley graph. In particular, we answer the following question: Which Cayley graphs are prime?

A consistent path system in a graph $G$ is an intersection-closed collection of paths, with exactly one path between any two vertices in $G$. We call $G$ metrizable if every consistent path system in it is the system of geodesic paths defined by assigning some positive lengths to its edges. We show that metrizable graphs are, in essence, subdivisions of a small family of basic graphs with additional compliant edges. In particular, we show that every metrizable graph with 11 vertices or more is outerplanar plus one vertex.

Magnetic order and microwave absorption in amorphous ferromagnets and materials sintered from nanoscale ferromagnetic grains are investigated analytically and numerically within the random-anisotropy model. We show that a scaling argument specific to static randomness allows one to make conclusions about the behavior of a large system with a weak disorder by studying a smaller system with a strong disorder. The breakdown of the scaling on increasing the strength of the magnetic anisotropy and/or the size of the grain separates two distinct regimes in magnetic ordering and frequency dependence of the absorbed microwave power. Analytical results are confirmed by numerical experiments on spin lattices containing up to ten million spins. Our findings should help design materials with desired magnetic and microwave properties. The method can be extended to other systems with quenched randomness., Comment: 10 pages, 9 figures

A clock is a graph consisting of an induced cycle $C$ and a vertex not in $C$ with at least two non-adjacent neighbours in $C$. We show that every clock-free graph of large treewidth contains a "basic obstruction" of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall.

Given an integer $k>4$ and a graph $H$, we prove that, assuming P$\neq$NP, the List-$k$-Coloring Problem restricted to $H$-free graphs can be solved in polynomial time if and only if either every component of $H$ is a path on at most three vertices, or removing the isolated vertices of $H$ leaves an induced subgraph of the five-vertex path. In fact, the "if" implication holds for all $k\geq 1$.

Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every $t\geq 1$, the $t$-basic obstructions: the graphs $K_{t+1}$ and $K_{t,t}$, along with the subdivisions of the $t$-by-$t$ wall and their line graphs. But this list is far from complete. The simplest example of a ''non-basic'' obstruction is due to Pohoata and Davies (independently). For every $n \geq 1$, they construct certain graphs of treewidth $n$ and with no $3$-basic obstruction as an induced subgraph, which we call $n$-arrays. Let us say a graph class $\mathcal{G}$ is clean if the only obstructions to bounded treewidth in $\mathcal{G}$ are in fact the basic ones. It follows that a full description of the induced subgraph obstructions to bounded treewidth is equivalent to a characterization of all families $\mathcal{H}$ of graphs for which the class of all $\mathcal{H}$-free graphs is clean (a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to any graph in $\mathcal{H}$). This remains elusive, but there is an immediate necessary condition: if $\mathcal{H}$-free graphs are clean, then there are only finitely many integers $n\geq 1$ such that there is an $n$-array which is $\mathcal{H}$-free. The above necessary condition is not sufficient in general. However, the situation turns out to be different if $\mathcal{H}$ is finite: we prove that for every finite set $\mathcal{H}$ of graphs, the class of all $\mathcal{H}$-free graphs is clean if and only if there is no $\mathcal{H}$-free $n$-array except possibly for finitely many values of $n$.

A class $\mathcal F$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi(H)\le f(\omega(H))$ for all induced subgraphs $H$ of a graph in $\mathcal F$. If $f$ can be chosen to be a polynomial, we say that $\mathcal F$ is polynomially $\chi$-bounded. Esperet proposed a conjecture that every $\chi$-bounded class of graphs is polynomially $\chi$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. Nevertheless, inspired by Esperet's conjecture, we introduce Pollyanna classes of graphs. A class $\mathcal C$ of graphs is Pollyanna if $\mathcal C\cap \mathcal F$ is polynomially $\chi$-bounded for every $\chi$-bounded class $\mathcal F$ of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna., Comment: 35 pages, 12 figures

Sivaraman conjectured that if $G$ is a graph with no induced even cycle then there exist sets $X_1, X_2 \subseteq V(G)$ satisfying $V(G) = X_1 \cup X_2$ such that the induced graphs $G[X_1]$ and $G[X_2]$ are both chordal. We prove this conjecture in the special case where $G$ contains no sector wheel, namely, a pair $(H, w)$ where $H$ is an induced cycle of $G$ and $w$ is a vertex in $V(G) \setminus V(H)$ such that $N(w) \cap H$ is either $V(H)$ or a path with at least three vertices.

We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Dibek, Chudnovsky, Rz\k{a}\.zewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time $n^{\mathcal{O}(\Delta^2)}$, where $n$ is the number of vertices of the instance and $\Delta$ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph., Comment: arXiv admin note: text overlap with arXiv:2107.05434

Given an integer $c\geq 1$, we say a graph $G$ is $c$-pinched if $G$ does not contain an induced subgraph consisting of $c$ cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of $c$-pinched graphs? For instance, $1$-pinched graphs are exactly graphs of treewidth $1$. However, bounded treewidth for $c>1$ is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line-graphs of subdivided walls are all examples of $2$-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of $c$, discovered by Pohoata and later independently by Davies, consisting of $3$-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every integer $c\geq 1$, a $c$-pinched graph $G$ has large treewidth if and only if $G$ contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line-graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded., Comment: arXiv admin note: text overlap with arXiv:2305.15615

Treewidth is a fundamental graph parameter that quantifies the complexity of graphs by measuring their "thickness" compared to a tree. In 1986, Robertson and Seymour proved that the only way a graph may have large treewidth is by containing a large hexagonal grid as a minor, or equivalently, as a (subdivided) subgraph. Which induced subgraphs prevent a graph from having small treewidth? Along with complete graphs, there are three other "basic" obstructions that should appear in the answer. But the full list remains beyond the reach of current methods, and "even holes" seem to be the crux of this matter. The reason lies in the observation that even holes are the only (non-trivial) induced subgraphs that all basic obstructions except for complete graphs have in common, and yet graphs with no even hole and no $4$-vertex complete subgraph fail to have bounded treewidth. The only known example of (even-hole, $K_4$)-free graphs of unbounded treewidth, called "layered wheels", is due to Sintiari and Trotignon. While rather complicated in global structure, layered wheels are unexpectedly sparse from a local perspective: for every $h\geq 1$, there are layered wheels of arbitrarily large treewidth in which every induced subgraph on at most $h$ vertices is chordal. The converse is also true, that every $K_4$-free chordal graph $H$ appears as an induced subgraph in every layered wheel of sufficiently large treewidth. It turns out, despite their technically involved construction, that layered wheels are in fact quite canonical: our main result shows that the local structure of layered wheels is realized in every (even-hole, $K_4$)-free graph of large treewidth. More precisely, we prove that for a graph $H$, every (even-hole, $K_4$)-free graph of large enough treewidth contains an induced subgraph isomorphic to $H$, if and only if $H$ is a $K_4$-free chordal graph.

Contraction and expansion of skyrmions in ferromagnetic films are investigated. In centrosymmetric systems, the dynamics of a collapsing skyrmion is driven by dissipation. The collapse time has a minimum on the damping constant. In systems with broken inversion symmetry, the evolution of skyrmions toward equilibrium size is driven by the Dzyaloshinskii-Moriya interaction. Expressions describing the time dependence of the skyrmion size are derived and their implications for skyrmion-based information processing are discussed., Comment: Six pages, two figures, to appear in the journal of Low Temperature Physics published by the B. Verkin Institute for Low Temperature Physics and Engineering of the National Academy of Sciences of Ukraine

Microwave power absorption by a two-layer system deposited on a metallic surface has been studied in the experimental setup emulating the response to a radar signal. Layers containing hexaferrite and iron powder in a dried paint of thickness under 1mm have been used. The data is analyzed within a theoretical model derived for a bilayer system from the transmission line theory. A good agreement between experimental and theoretical results is found. The advantage of using a bilayer system over a single-layer system has been demonstrated. How the maximum microwave absorption (minimum reflection loss) can be achieved through the optimization of the filling factors and thicknesses of the two layers is shown.

A generalized $t$-pyramid is a graph obtained from a certain kind of tree (a subdivided star or a subdivided cubic caterpillar) and the line graph of a subdivided cubic caterpillar by identifying simplicial vertices. We prove that for every integer $t$ there exists a constant $c(t)$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ and no induced subgraph isomorphic to a generalized $t$-pyramid has treewidth at most $c(t)\log{n}$. This settles a special case of a conjecture of Sintiari and Trotignon; this bound is also best possible for the class. It follows that several \textsf{NP}-hard problems such as \textsc{Stable Set}, \textsc{Vertex Cover}, \textsc{Dominating Set} and \textsc{Coloring} admit polynomial-time algorithms on this class of graphs. Results from this paper are also used in later papers of the series, in particular to solve the full version of the Sintiari-Trotignon conjecture.

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of $P_6$-free graphs. This generalizes the work of Grzesik, Klimo\v{s}ov\'{a}, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in $P_6$-free graphs~[SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rz\k{a}\.zewski, and Seymour on problems in $P_5$-free graphs~[SODA~2021]. The key step is a new generalization of the framework of potential maximal cliques. We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their carvers: vertex sets that contain the same vertices from the sought solution and have similar separation properties.

The tree-independence number tree-$\alpha$, first defined and studied by Dallard, Milani\v{c} and \v{S}torgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass $\mathcal C$ of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that $\mathcal C$ has bounded tree-$\alpha$. Via existing results, this yields a polynomial time algorithm for the maximum independent set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milani\v{c} and \v{S}torgel that in a hereditary graph class, tree-$\alpha$ is bounded if and only if the treewidth is bounded by a function of the clique number., Comment: 17 pages. arXiv admin note: text overlap with arXiv:2203.06775

The celebrated Erd\H{o}s-P\'{o}sa Theorem, in one formulation, asserts that for every $c\geq 1$, graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of $c$ cycles have bounded treewidth. What can we say about the treewidth of graphs containing no induced subgraph isomorphic to the disjoint union of $c$ cycles? Let us call these graphs $c$-perforated. While $1$-perforated graphs have treewidth one, complete graphs and complete bipartite graphs are examples of $2$-perforated graphs with arbitrarily large treewidth. But there are sparse examples, too: Bonamy, Bonnet, D\'{e}pr\'{e}s, Esperet, Geniet, Hilaire, Thomass\'{e} and Wesolek constructed $2$-perforated graphs with arbitrarily large treewidth and no induced subgraph isomorphic to $K_3$ or $K_{3,3}$; we call these graphs occultations. Indeed, it turns out that a mild (and inevitable) adjustment of occultations provides examples of $2$-perforated graphs with arbitrarily large treewidth and arbitrarily large girth, which we refer to as full occultations. Our main result shows that the converse also holds: for every $c\geq 1$, a $c$-perforated graph has large treewidth if and only if it contains, as an induced subgraph, either a large complete graph, or a large complete bipartite graph, or a large full occultation. This distinguishes $c$-perforated graphs, among graph classes purely defined by forbidden induced subgraphs, as the first to admit a grid-type theorem incorporating obstructions other than subdivided walls and their line graphs. More generally, for all $c,o\geq 1$, we establish a full characterization of induced subgraph obstructions to bounded treewidth in graphs containing no induced subgraph isomorphic to the disjoint union of $c$ cycles, each of length at least $o+2$.

Let $G$ be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph $G$ with no balanced skew-partition is either complete or has an even pair.

The family of cycle completable graphs has several cryptomorphic descriptions, the equivalence of which has heretofore been proven by a laborious implication-cycle that detours through a motivating matrix completion problem. We give a concise proof, partially by introducing a new characterization. Then we generalize this family to ``$k$-quasichordal'' graphs, with three natural characterizations., Comment: 8 pages

We study analytically and numerically on lattices containing $10^5$ spins, the integral absorption of microwaves by a random-anisotropy magnet, $\int d\omega P(\omega)$. It scales as $D^2_R/J$ on the random-anisotropy strength $D_R$ and the strength of the ferromagnetic exchange $J$ in low-anisotropy amorphous magnetic materials. At high anisotropy and in low-anisotropy materials sintered of sufficiently large ferromagnetic grains, the integral power scales linearly on $D_R$. The maximum bandwidth, combined with the maximum absorption power, is achieved when the amorphous structure factor, or grain size, is of an order of the domain wall thickness in a conventional ferromagnet that is of the order of $(J/D_R)^{1/2}$ lattice spacings., Comment: 9 pages, 5 figure captions

We prove that every connected $P_5$-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected $P_5$-free graph $G$ with independence number at least three contains a three-vertex induced path with vertices $a \hbox{-} b \hbox{-} c$ in order, such that every neighbour of $c$ is also adjacent to one of $a,b$., Comment: 14 pages

Given a graph $H$, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to $H$, if and only if $H$ is a forest.

The theory of localized spin-wave excitations in random-anisotropy magnets has been developed. Starting with a pure Heisenberg ferromagnet, we study the evolution of standing spin waves in a finite-size sample towards localized modes on increasing the strength of random anisotropy. Profiles of the localized modes and their phases are analyzed and visualized in a 2D sample. Localization length is obtained by several methods and its dependence on random anisotropy is computed. The connection between the localization of spin excitations and the broadband nature of the absorption of microwave power by random-anisotropy magnets is elucidated., Comment: 14 pages in Physical Review format, 13 figure captions

We say a class $\mathcal{C}$ of graphs is clean if for every positive integer $t$ there exists a positive integer $w(t)$ such that every graph in $\mathcal{C}$ with treewidth more than $w(t)$ contains an induced subgraph isomorphic to one of the following: the complete graph $K_t$, the complete bipartite graph $K_{t,t}$, a subdivision of the $(t\times t)$-wall or the line graph of a subdivision of the $(t \times t)$-wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Wei{\ss}auer) to prove that the class of all $H$-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph $H$) is clean if and only if $H$ is a forest whose components are subdivided stars. Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest $H$ as above, we show that forbidding certain connected graphs containing $H$ as an induced subgraph (rather than $H$ itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer $\eta$, a complete description of unavoidable connected induced subgraphs of a connected graph $G$ containing $\eta$ vertices from a suitably large given set of vertices in $G$. This is of independent interest, and will be used in subsequent papers in this series., Comment: Accepted manuscript; see DOI for journal version

Abstract We report Monte Carlo studies of lattices of up to $10^{5}$ skyrmions treated as particles with negative core energy and repulsive interaction obtained from a microscopic spin model. Temperature dependence of translational and orientational correlations has been investigated for different experimental protocols and initial conditions. Cooling the skyrmion liquid from fully disordered high-temperature state results in the formation of a skyrmion polycrystal. A perfect skyrmion lattice prepared at $T=0$, on raising temperature undergoes a first-order melting transition into a polyhexatic state that consists of large orientationally ordered domains of fluctuating shape. On the further increasing temperature, these domains decrease in size, leading to a fully disordered liquid of skyrmions., Comment: 19 Phys. Rev. pages, 22 figure captions

This paper continues a series of papers investigating the following question: which hereditary graph classes have bounded treewidth? We call a graph $t$-clean if it does not contain as an induced subgraph the complete graph $K_t$, the complete bipartite graph $K_{t, t}$, subdivisions of a $(t \times t)$-wall, and line graphs of subdivisions of a $(t \times t)$-wall. It is known that graphs with bounded treewidth must be $t$-clean for some $t$; however, it is not true that every $t$-clean graph has bounded treewidth. In this paper, we show that three types of cutsets, namely clique cutsets, 2-cutsets, and 1-joins, interact well with treewidth and with each other, so graphs that are decomposable by these cutsets into basic classes of bounded treewidth have bounded treewidth. We apply this result to two hereditary graph classes, the class of ($ISK_4$, wheel)-free graphs and the class of graphs with no cycle with a unique chord. These classes were previously studied and decomposition theorems were obtained for both classes. Our main results are that $t$-clean ($ISK_4$, wheel)-free graphs have bounded treewidth and that $t$-clean graphs with no cycle with a unique chord have bounded treewidth., Comment: Accepted manuscript; see DOI for journal version