Search

Fracture toughness is the material property characterizing resistance to failure. Predicting its value from the solid structure at the atomistic scale remains elusive, even in the simplest situations of brittle fracture. We report here numerical simulations of crack propagation in two-dimensional fuse networks of different periodic geometries, which are electrical analogs of bidimensional brittle crystals under antiplanar loading. Fracture energy is determined from Griffith's analysis of energy balance during crack propagation, and fracture toughness is determined from fits of the displacement fields with Williams' asymptotic solutions. Significant size dependencies are evidenced in small lattices, with fracture energy and fracture toughness both converging algebraically with system size toward well-defined material-constant values in the limit of infinite system size. The convergence speed depends on the loading conditions and is faster when the symmetry of the considered lattice increases. The material constants at infinity obey Irwin's relation and properly define the material resistance to failure. Their values are approached up to $\sim$ 15 % using the recent analytical method proposed in Nguyen and Bonamy (Phys Rev Lett 123:205503, 2019). Nevertheless, the deviation remains finite and does not vanish when the system size goes to infinity. We finally show that this deviation is a consequence of the lattice discreetness and decreases when the super-singular terms of Williams' solutions (absent in a continuum medium but present here due to lattice discreetness) are taken into account., Comment: International Journal of Fracture, In press

In submerged sandy slopes, soil is frequently eroded as a combination of two main mechanisms: breaching, which refers to the retrogressive failure of a steep slope forming a turbidity current, and, instantaneous sliding wedges, known as shear failure, that also contribute to shape the morphology of the soil deposit. Although there are several modes of failures, in this paper we investigate breaching and shear failures of granular columns using the two-fluid approach. The numerical model is first applied to simulate small scale granular column collapses with different initial volume fractions to study the role of the initial conditions on the main flow dynamics. For loosely packed granular columns, the porous medium initially contracts and the resulting positive pore pressure leads to a rapid collapse. Whereas in initially dense-packing columns, the porous medium initially dilates and negative pore pressure is generated stabilizing the granular column, which results in a slow collapse. The proposed numerical approach shows good agreement with the experimental data in terms of morphology and excess of pore pressure. Numerical results are extended to a large-scale application known as the breaching process. This phenomenon may occur naturally at coasts or on dykes and levees in rivers but it can also be triggered by humans during dredging operations. The results indicate that the two-phase flow model correctly predicts the dilative behavior and, the subsequent turbidity currents, associated to the breaching process.

We show that the edges of any planar graph of maximum degree at most $9$ can be partitioned into $4$ linear forests and a matching. Combined with known results, this implies that the edges of any planar graph $G$ of odd maximum degree $\Delta\ge 9$ can be partitioned into $\tfrac{\Delta-1}{2}$ linear forests and one matching. This strengthens well-known results stating that graphs in this class have chromatic index $\Delta$ [Vizing, 1965] and linear arboricity at most $\lceil(\Delta+1)/2\rceil$ [Wu, 1999].

Recently, Letzter proved that any graph of order $n$ contains a collection $\mathcal{P}$ of $O(n\log^\star n)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path in $\mathcal{P}$ which contains $e$ but not $f$. We improve this upper bound to $19 n$, thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluh\'ar and by Falgas-Ravry, Kittipassorn, Kor\'andi, Letzter, and Narayanan. Our proof is elementary and self-contained., Comment: 7 pages, 3 figures

We examine how disordering joint position influences the linear elastic behavior of lattice materials via numerical simulations in two-dimensional beam networks. Three distinct initial crystalline geometries are selected as representative of mechanically isotropic materials low connectivity, mechanically isotropic materials with high connectivity, and mechanically anisotropic materials with intermediate connectivity. Introducing disorder generates spatial fluctuations in the elasticity tensor at the local (joint) scale. Proper coarse-graining reveals a well-defined continuum-level scale elasticity tensor. Increasing disorder aids in making initially anisotropic materials more isotropic. The disorder impact on the material stiffness depends on the lattice connectivity: Increasing the disorder softens lattices with high connectivity and stiffens those with low connectivity, without modifying the scaling between elastic modulus and density (linear scaling for high connectivity and cubic scaling for low connectivity). Introducing disorder in lattices with intermediate fixed connectivity reveals both scaling: the linear scaling occurs for low density, the cubic one at high density, and the crossover density increases with disorder. Contrary to classical formulations, this work demonstrates that connectivity is not the sole parameter governing elastic modulus scaling. It offers a promising route to access novel mechanical properties in lattice materials via disordering the architectures.

A graph is $\mathcal{O}_k$-free if it does not contain $k$ pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) $\mathcal{O}_k$-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of $\mathcal{O}_2$-free graphs without $K_{2,3}$ as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in $\mathcal{O}_k$-free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse $\mathcal{O}_k$-free graphs, and that deciding the $\mathcal{O}_k$-freeness of sparse graphs is polynomial time solvable., Comment: 30 pages, 6 figures. v5: revised version

We consider Kempe changes on the $k$-colorings of a graph on $n$ vertices. If the graph is $(k-1)$-degenerate, then all its $k$-colorings are equivalent up to Kempe changes. However, the sequence between two $k$-colorings that arises from the proof may be exponential in the number of vertices. An intriguing open question is whether it can be turned polynomial. We prove this to be possible under the stronger assumption that the graph has treewidth at most $k-1$. Namely, any two $k$-colorings are equivalent up to $O(kn^2)$ Kempe changes. We investigate other restrictions (list coloring, bounded maximum average degree, degree bounds). As a main result, we derive that given an $n$-vertex graph with maximum degree $\Delta$, the $\Delta$-colorings are all equivalent up to $O(n^2)$ Kempe changes, unless $\Delta = 3$ and some connected component is a 3-prism.

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for \textsc{Max Clique} on disk and unit ball graphs. \textsc{Max Clique} on unit ball graphs is equivalent to finding, given a collection of points in $\mathbb R^3$, a maximum subset of points with diameter at most some fixed value. In stark contrast, \textsc{Maximum Clique} on ball graphs and unit $4$-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation which cannot be attained even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails., Comment: arXiv admin note: substantial text overlap with arXiv:1712.05010, arXiv:1803.01822

The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best-known result was for graphs with minimum degree $23$., Comment: 10 pages

In 1968, Gallai conjectured that the edges of any connected graph with $n$ vertices can be partitioned into $\lceil \frac{n}{2} \rceil$ paths. We show that this conjecture is true for every planar graph. More precisely, we show that every connected planar graph except $K_3$ and $K_5^-$ ($K_5$ minus one edge) can be decomposed into $\lfloor \frac{n}{2} \rfloor$ paths.

Modelling sediment transport is still a challenging problem and is of major importance for the study of particulate geophysical flows. In this work, the modelling of sediment transport in the collisional regime is investigated with a focus on the continuum modelling of the granular flow. For this purpose, a frictional-collisional approach, combining a Coulomb model with the kinetic theory of granular gases, is developed. The methodology is based on a comparison with coupled fluid-discrete simulations, that classical kinetic theory model fails to reproduce. In order to improve the continuum model, the fluctuating energy balance is computed in the discrete simulations and systematically compared with the kinetic theory closure laws. Inter-particle friction is shown to affect the radial distribution function and to increase the energy dissipation, in agreement with previous observations in the literature. Due to saltating particles, whose motion can not be captured by the kinetic theory, departure from the viscosity and diffusivity laws are observed in the dilute part of the granular flow. Finally, the quadratic nature of the drag force is shown to increase the granular fluctuating energy dissipation. Based on these observations, modifications of the kinetic theory closure laws are proposed. The modified model reproduces perfectly the discrete simulations in the entire depth structure of the granular flow. These modifications are shown to impact the rheological properties of the flow and they make it possible to recover the {\mu}(I) rheology in the dense regime.

We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a $(5-\varepsilon)$-approximation, for any $\varepsilon>0$. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed., Comment: Accepted to DISC 2021

Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? We answer this question in the affirmative for triangle-free graphs., Comment: 12 pages, 6 figures

Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4., Comment: 14 pages, 11 figures, Accepted to European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB) 2021

We prove that for any $\varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(\frac32-\varepsilon)t$-colouring that is "frozen" with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981., Comment: 5 pages

We examine theoretically and numerically fast propagation of a tensile crack along unidimensional strips with periodically evolving toughness. In such dynamic fracture regimes, crack front waves form and transport front disturbances along the crack edge at speed less than the Rayleigh wave speed and depending on the crack speed. In this configuration, standing front waves dictate the spatio-temporal evolution of the local crack front speed, which takes a specific scaling form. Analytical examination of both the short-time and long-time limits of the problem reveals the parameter dependency with strip wavelength, toughness contrast and overall fracture speed. Implications and generalization to unidimensional strips of arbitrary shape are lastly discussed.

Following a given ordering of the edges of a graph $G$, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index $\chi'(G)$, and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let $\chi_c'(G)$ be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether $\chi_c'(G)>\chi'(G)$. We prove that $\chi'(G)=\chi_c'(G)$ if $G$ is bipartite, and that $\chi_c'(G)\leq 4$ if $G$ is subcubic., Comment: Comments welcome, 12 pages

The process of colloidal drying gives way to particle self-assembly in numerous elds including photonics or biotechnology. Yet, the mechanisms and conditions driving the nal particle arrangement in dry colloidal layers remain elusive. Here, we examine how the drying rate selects the nanostructure of thick dried layers in four dierent suspensions of silica nanospheres. Depending on particle size and dispersity, either an amorphous arrangement, a crystalline arrangement, or a rate-dependent amorphous-to-crystalline transition occurs at the drying surface. Amorphous arrangements are observed in the two most polydisperse suspensions while crystallinity occurs when dispersity is lower. Counter-intuitively in the latter case, a higher drying rate favors ordering of the particles. To complement these measurements and to take stock of the bulk properties of the layer, tests on the layer porosity were undertaken. For all suspensions studied herein, faster drying yields denser dry layers. Crystalline surface arrangement implies large bulk volume fraction ($\sim$ 0.65) whereas amorphous arrangements can be observed in layers with either low (down to $\sim$ 0.53) or high ($\sim$ 0.65) volume fraction. Lastly, we demonstrate via targeted additional experiments and SAXS measurements, that the packing structure of the layers is mainly driven by the formation of aggregates and their subsequent packing, and not by the competition between Brownian diusion and convection. This highlights that a second dimensionless ratio in addition to the Peclet number should be taken into account, namely the aggregation over evaporation timescale.

A hereditary class of graphs $\mathcal{G}$ is \emph{$\chi$-bounded} if there exists a function $f$ such that every graph $G \in \mathcal{G}$ satisfies $\chi(G) \leq f(\omega(G))$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and the clique number of $G$, respectively. As one of the first results about $\chi$-bounded classes, Gy\'{a}rf\'{a}s proved in 1985 that if $G$ is $P_t$-free, i.e., does not contain a $t$-vertex path as an induced subgraph, then $\chi(G) \leq (t-1)^{\omega(G)-1}$. In 2017, Chudnovsky, Scott, and Seymour proved that $C_{\geq t}$-free graphs, i.e., graphs that exclude induced cycles with at least $t$ vertices, are $\chi$-bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that $P_{t-1}$-free graphs are in particular $C_{\geq t}$-free. It remains a major open problem in the area whether for $C_{\geq t}$-free, or at least $P_t$-free graphs $G$, the value of $\chi(G)$ can be bounded from above by a polynomial function of $\omega(G)$. We consider a relaxation of this problem, where we compare the chromatic number with the size of a largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every $t$ there exists a constant $c$ such that for and every $C_{\geq t}$-free graph which does not contain $K_{\ell,\ell}$ as a subgraph, it holds that $\chi(G) \leq \ell^{c}$.

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours., Comment: This paper is essentially a combination of arXiv:2007.03582 and the non-algorithmic part of arXiv:2007.08771, where some results in arXiv:2007.03582 are strengthened. v2: fix the authors names. v3: update based on referees' comments, improve the bound for layered treewidth in Theorem 1.12 from 12 to 1, and simplify the proof without the use of fat bananas

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing $2^{\Omega(n^2)}$ $n$-vertex graphs as $n\to \infty$. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of $n/4+o(n)$ bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of $n/4+o(n)$ bits per vertex and comparability labelling scheme for posets with labels of $n/4+o(n)$ bits per element. All these results are best possible, up to the lower order term., Comment: 17 pages - to appear in the proceedings of STOC 2021

We examine the effect of small, spatially localized, excitations applied periodically in different manners, on the crackling dynamics of a brittle crack driven slowly in a heterogeneous solid. When properly adjusted, these excitations are observed to radically modify avalanche statistics and considerably limit the magnitude of the largest events. Surprisingly, this does not require information on the front loading state at the time of excitation; applying it either at a random location or at the most loaded point gives the same results. Subsequently, we unravel how the excitation amplitude, spatial extent and frequency govern the effect. We find that the excitation efficiency is ruled by a single reduced parameter, namely the injected power per unit front length; the suppression of extreme avalanches is maximum at a well-defined optimal value of this control parameter. This analysis opens a new way to control largest events in crackling dynamics. Beyond fracture problems, it may be relevant for crackling systems described by models of the same universality class, such as the wetting of heterogeneous substrates or magnetic walls in amorphous magnets., Comment: 4 figures

We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the following three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Lu\v{z}ar, and \v{S}krekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most $2 - 1/324$., Comment: 14 pages, 2 figures

We introduce a model for random geodesic drawings of the complete bipartite graph $K_{n,n}$ on the unit sphere $\mathbb{S}^2$ in $\mathbb{R}^3$, where we select the vertices in each bipartite class of $K_{n,n}$ with respect to two non-degenerate probability measures on $\mathbb{S}^2$. It has been proved recently that many such measures give drawings whose crossing number approximates the Zarankiewicz number (the conjectured crossing number of $K_{n,n}$). In this paper we consider the intersection graphs associated with such random drawings. We prove that for any probability measures, the resulting random intersection graphs form a convergent graph sequence in the sense of graph limits. The edge density of the limiting graphon turns out to be independent of the two measures as long as they are antipodally symmetric. However, it is shown that the triangle densities behave differently. We examine a specific random model, blow-ups of antipodal drawings $D$ of $K_{4,4}$, and show that the triangle density in the corresponding crossing graphon depends on the angles between the great circles containing the edges in $D$ and can attain any value in the interval $\bigl(\frac{83}{12288}, \frac{128}{12288}\bigr)$., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

"Zombies and Survivor" is a variant of the well-studied game of "Cops and Robber" where the zombies (cops) can only move closer to the survivor (robber). We consider the deterministic version of the game where a zombie can choose their path if multiple options are available. The zombie number, like the cop number, of a graph is the minimum number of zombies, or cops, required to capture the survivor. In this short note, we solve a question by Fitzpatrick et al., proving that the zombie number of the Cartesian product of two graphs is at most the sum of their zombie numbers. We also give a simple graph family with cop number $2$ and an arbitrarily large zombie number., Comment: 4 pages

The famous List Colouring Conjecture from the 1970s states that for every graph $G$ the chromatic index of $G$ is equal to its list chromatic index. In 1996 in a seminal paper, Kahn proved that the List Colouring Conjecture holds asymptotically. Our main result is a local generalization of Kahn's theorem. More precisely, we show that, for a graph $G$ with sufficiently large maximum degree $\Delta$ and minimum degree $\delta \geq \ln^{25} \Delta$, the following holds: for every assignment of lists of colours to the edges of $G$, such that $|L(e)| \geq (1+o(1)) \cdot \max\left\{\rm{deg}(u),\rm{deg}(v)\right\}$ for each edge $e=uv$, there is an $L$-edge-colouring of $G$. Furthermore, Kahn showed that the List Colouring Conjecture holds asymptotically for linear, $k$-uniform hypergraphs, and recently Molloy generalized Kahn's original result to correspondence colouring as well as its hypergraph generalization. We prove local versions of all of these generalizations by showing a weighted version that simultaneously implies all of our results., Comment: 25 pages, Accepted to JCTB

In this paper the capabilities of the turbulence-resolving Eulerian-Eulerian two-phase flow model to predict the suspension of mono-dispersed finite-sized solid particles in a boundary layer flow are investigated. For heavier-than-fluid particles, having settling velocity of the order of the bed friction velocity, the two-fluid model significantly under-estimates the turbulent dispersion of particles. It is hypothesized that finite-size effects are important and a correction model for the drag law is proposed. This model is based on the assumption that the turbulent flow scales larger than the particle diameter will contribute to the resolved relative velocity between the two phases, whereas eddies smaller than the particle diameter will have two effects: (i) they will reduce the particle response time by adding a sub-particle scale eddy viscosity to the drag coefficient, and (ii) they will contribute to increase the production of granular temperature. Integrating finite-size effects allows us to quantitatively predict the concentration profile for heavier-than-fluid particles without any tuning parameter. The proposed modification of the two-fluid model extends its range of applicability to tackle particles having a size belonging to the inertial range of turbulence and allows us to envision more complex applications in terms of flow forcing conditions, i.e. sheet flow, wave-driven transport, turbidity currents and/or flow geometries, i.e. ripples, dunes, scour.

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e. colorings in which each monochromatic component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with monochromatic components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal., Comment: 35 pages, 4 figures - v3: correction of the statements of Theorem 5.2, Corollary 5.3 and Theorem 5.9. Most of the results in this paper have been merged to arXiv:2012.02435

Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating minimal dominating sets in an incomparability graph. We provide an output-polynomial time algorithm for incomparability graphs whose underlying posets have bounded dimension. Through a different proof technique, we also provide an output-polynomial algorithm for their complements, i.e., for comparability graphs of bounded dimension posets. Our algorithm for incomparability graphs is based on flashlight search and relies on the geometrical representation of incomparability graphs with bounded dimension, as given by Golumbic et al. in 1983. It runs with polynomial delay and only needs polynomial space. Our algorithm for comparability graphs is based on the flipping method introduced by Golovach et al. in 2015. It performs in incremental-polynomial time and requires exponential space. In addition, we show how to improve the flipping method so that it requires only polynomial space. Since the flipping method is a key tool for the best known algorithms enumerating minimal dominating sets in a number of graph classes, this yields direct improvements on the state of the art., Comment: 22 pages, 5 figures

We consider a classic rendezvous game where two players try to meet each other on a set of $n$ locations. In each round, every player visits one of the locations and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of $\frac{n+1}{2}$ is achieved by the wait-for-mommy pair of strategies, where one of the players stays at one location for $n$ rounds, while the other player searches through all the $n$ locations in a random order. However, if we insist that the players are symmetric --- they are expected to follow the same strategy --- then the best known strategy, proposed by Anderson and Weber, achieves an asymptotic expected waiting time of $0.829 n$. We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every $n\geqslant 2$, if the players need to employ the same strategy, then the expected waiting time is at least $\frac{n+1}{2}+\varepsilon n$, where $\varepsilon=2^{-36}$., Comment: 13 pages

High performance calculation is increasingly used within society. Previously reserved for an elite, based on large computing and storage infrastructures, it is now a core module for many companies. Indeed, high performance calculation makes it possible to design and optimize many elements for a limited cost ,compared to the production of prototypes or tests in situ. It is also widely used in big data and artificial intelligence.It seems essential to ask about theenvironmental impact of these digital practices. A number of actions have already been initiated in this community: GREEN500; European CoC eco-responsibility label for Data centres... but these actions generally look at specific or even idealised situations and/or software.The software qualification process in the field of high performance calculation consists in looking at the scalability of the software. The originality of this study is to focus on energy scalability (calculation return time depending on the power consumed), by considering several architectures (three TOP500 machines and a laboratory cluster).The energy cost of an example calculation could be estimated, which shows that the most efficient machine in terms of calculation time is not necessarily the most energy efficient, and depending on the number of cores/processes chosen, it is not always the same architecture that is the most energy-efficient. It was therefore possible to show that the longer the user is prepared to wait, the less energy is used by the calculation., Comment: Vid{\'e}o https://replay.jres.org/videos/watch/811bb2fe-582e-4996-9643-89401d2c0d2c , in French, Congr\`es JRES : Les Journ\'ees R\'eseaux de l'Enseignement et de la Recherche, RENATER, Dec 2019, Dijon, France

Let $G$ be a graph and $D_s$ and $D_t$ be two dominating sets of $G$ of size $k$. Does there exist a sequence $\langle D_0 = D_s, D_1, \ldots, D_{\ell-1}, D_\ell = D_t \rangle$ of dominating sets of $G$ such that $D_{i+1}$ can be obtained from $D_i$ by replacing one vertex with one of its neighbors? In this paper, we investigate the complexity of this decision problem. We first prove that this problem is PSPACE-complete, even when restricted to split, bipartite or bounded treewidth graphs. On the other hand, we prove that it can be solved in polynomial time on dually chordal graphs (a superclass of both trees and interval graphs) or cographs.

We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain $k+1$ vertex-disjoint cycles, then it suffices to delete $2k$ vertices to obtain a forest.

We examine the atomistic scale dependence of material's resistance-to-failure by numerical simulations and analytical analysis in electrical analogs of brittle crystals. We show that fracture toughness depends on the lattice geometry in a way incompatible with Griffith's relationship between fracture and free surface energy. Its value finds its origin in the matching between the continuum displacement field at the engineering scale, and the discrete nature of solids at the atomic scale. The generic asymptotic form taken by this field near the crack tip provides a solution for this matching, and subsequently a way to predict toughness from the atomistic parameters with application to graphene.

We prove that if $\mathcal{C}$ is a hereditary class of graphs that is polynomially $\chi$-bounded, then the class of graphs that admit decompositions into pieces belonging to $\mathcal{C}$ along cuts of bounded rank is also polynomially $\chi$-bounded. In particular, this implies that for every positive integer $k$, the class of graphs of cliquewidth at most $k$ is polynomially $\chi$-bounded., Comment: 20 pages

We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises the notion of simpliciality best known in the context of chordal graphs. The conjecture was only established for k in {1,2} (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively). Our result also implies a result of Chv\'atal et al. 2002, which assumed cycle restrictions. We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis. In the line of previous works, we discuss conditions for multiple avoidable paths to exist., Comment: 7 pages, 1 figure

An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our scheme generalizes to graphs of bounded Euler genus with the same label length up to a second-order term. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time.

We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number., Comment: v2: revised following referees' comments

While of paramount importance in material science, the dynamics of cracks still lacks a complete physical explanation. The transition from their slow creep behavior to a fast propagation regime is a notable key, as it leads to full material failure if the size of a fast avalanche reaches that of the system. We here show that a simple thermodynamics approach can actually account for such complex crack dynamics, and in particular for the non-monotonic force-velocity curves commonly observed in mechanical tests on various materials. We consider a thermally activated failure process that is coupled with the production and the diffusion of heat at the fracture tip. In this framework, the rise in temperature only affects the sub-critical crack dynamics and not the mechanical properties of the material. We show that this description can quantitatively reproduce the rupture of two different polymeric materials (namely, the mode I opening of polymethylmethacrylate (PMMA) plates, and the peeling of pressure sensitive adhesive (PSA) tapes), from the very slow to the very fast fracturing regimes, over seven to nine decades of crack propagation velocities. In particular, the fastest regime is obtained with an increase of temperature of thousands of kelvins, on the molecular scale around the crack tip. Although surprising, such an extreme temperature is actually consistent with different experimental observations that accompany the fast propagation of cracks, namely, fractoluminescence (i.e., the emission of visible light during rupture) and a complex morphology of post-mortem fracture surfaces, which could be due to the sublimation of bubbles., Comment: 19 pages, 18 figures, including 4 appendices. Soft Matter, 2020