Search

In this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Triangle Hitting (TH). We focus on the class of pseudo-disk graphs, which forms a common generalization of several graph classes where such results exist, like disk graphs and square graphs. In these graphs, we show that TH can be solved in time $2^{O(k^{3/4}\log k)}n^{O(1)}$, and given a geometric representation FVS can be solved in time $2^{O(k^{6/7}\log k)}n^{O(1)}$., Comment: Presented at the conference WG 2024

A local homeomorphism between open subsets of a locally compact Hausdorff space induces dynamical systems with a wide range of applications, including in C*-algebras. In this paper, we introduce the concepts of nonwandering and wandering sets for such systems and show that, under mild conditions, the metric entropy is concentrated in the nonwandering set. More generally, we demonstrate that the entropy of the system is the maximum of the entropies of the systems restricted to the nonwandering set and the closure of the wandering set. We illustrate these results with several examples, including applications to subshifts over countable alphabets., Comment: 21 pages, 2 figures

A vishing attack is a form of social engineering where attackers use phone calls to deceive individuals into disclosing sensitive information, such as personal data, financial information, or security credentials. Attackers exploit the perceived urgency and authenticity of voice communication to manipulate victims, often posing as legitimate entities like banks or tech support. Vishing is a particularly serious threat as it bypasses security controls designed to protect information. In this work, we study the potential for vishing attacks to escalate with the advent of AI. In theory, AI-powered software bots may have the ability to automate these attacks by initiating conversations with potential victims via phone calls and deceiving them into disclosing sensitive information. To validate this thesis, we introduce ViKing, an AI-powered vishing system developed using publicly available AI technology. It relies on a Large Language Model (LLM) as its core cognitive processor to steer conversations with victims, complemented by a pipeline of speech-to-text and text-to-speech modules that facilitate audio-text conversion in phone calls. Through a controlled social experiment involving 240 participants, we discovered that ViKing has successfully persuaded many participants to reveal sensitive information, even those who had been explicitly warned about the risk of vishing campaigns. Interactions with ViKing's bots were generally considered realistic. From these findings, we conclude that tools like ViKing may already be accessible to potential malicious actors, while also serving as an invaluable resource for cyber awareness programs.

In this paper, we establish a connection between evolution algebras of dimension two and Hopf algebras, via the algebraic group of automorphisms of an evolution algebra. Initially, we describe the Hopf algebra associated with the automorphism group of a 2-dimensional evolution algebra. Subsequently, for a 2-dimensional evolution algebra $A$ over a field $K$, we detail the relation between the algebra associated with the (tight) universal associative and commutative representation of $A$, referred to as the (tight) $p$-algebra, and the corresponding Hopf algebra, $\mathcal{H}$, representing the affine group scheme $\text{Aut}(A)$. Our analysis involves the computation of the (tight) $p-$algebra associated with any 2-dimensional evolution algebra, whenever it exists. We find that $\text{Aut}(A)=1$ if and only if there is no faithful associative and commutative representation for $A$. Moreover, there is a faithful associative and commutative representation for $A$ if and only if $\mathcal{H}\not\cong K$ and $\text{char} (K)\neq 2$, or $\mathcal{H}\not\cong K(\epsilon)$ (the dual numbers algebra) and $\mathcal{H}\not\cong K$ in case of $\text{char} (K)= 2$. Furthermore, if $A$ is perfect and has a faithful tight $p$-algebra, then this $p$-algebra is isomorphic to $\mathcal{H}$ (as algebras). Finally, we derive implications for arbitrary finite-dimensional evolution algebras.

Peer assessment has been widely studied as a replacement for traditional evaluation, not only by reducing the professors' workload but mainly by benefiting students' engagement and learning. Although several works successfully validate its accuracy and fairness, more research must be done on how students' pre-existing social relationships affect the grades they give their peers in an e-learning course. We developed a Moodle plugin to provide the platform with peer assessment capabilities in forums and used it on an MSc course. The plugin curated the reviewer set for a post based on the author's relationships and included rubrics to counter the possible interpersonal effects of peer assessment. Results confirm that peer assessment is reliable and accurate for works with at least three peer assessments, although students' grades are slightly higher. The impact of social relationships is noticeable when students who do not like another peer grade their work consistently lower than students who have a positive connection. However, this has little influence on the final aggregate peer grade. Our findings show that peer assessment can replace traditional evaluation in an e-learning environment where students are familiar with each other., Comment: 24 pages, 5 figures, 4 tables. Learning Environ Res (2024)

In the $K_r$-Cover problem, given a graph $G$ and an integer $k$ one has to decide if there exists a set of at most $k$ vertices whose removal destroys all $r$-cliques of $G$. In this paper we give an algorithm for $K_r$-Cover that runs in subexponential FPT time on graph classes satisfying two simple conditions related to cliques and treewidth. As an application we show that our algorithm solves $K_r$-Cover in time * $2^{O_r\left (k^{(r+1)/(r+2)}\log k \right)} \cdot n^{O_r(1)}$ in pseudo-disk graphs and map-graphs; * $2^{O_{t,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $K_{t,t}$-subgraph-free string graphs; and * $2^{O_{H,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $H$-minor-free graphs.

Brooks' Theorem is a fundamental result on graph colouring, stating that the chromatic number of a graph is almost always upper bounded by its maximal degree. Lov\'asz showed that such a colouring may then be computed in linear time when it exists. Many analogues are known for variants of (di)graph colouring, notably for list-colouring and partitions into subgraphs with prescribed degeneracy. One of the most general results of this kind is due to Borodin, Kostochka, and Toft, when asking for classes of colours to satisfy "variable degeneracy" constraints. An extension of this result to digraphs has recently been proposed by Bang-Jensen, Schweser, and Stiebitz, by considering colourings as partitions into "variable weakly degenerate" subdigraphs. Unlike earlier variants, there exists no linear-time algorithm to produce colourings for these generalisations. We introduce the notion of (variable) bidegeneracy for digraphs, capturing multiple (di)graph degeneracy variants. We define the corresponding concept of $F$-dicolouring, where $F = (f_1,...,f_s)$ is a vector of functions, and an $F$-dicolouring requires vertices coloured $i$ to induce a "strictly-$f_i$-bidegenerate" subdigraph. We prove an analogue of Brooks' theorem for $F$-dicolouring, generalising the result of Bang-Jensen et al., and earlier analogues in turn. Our new approach provides a linear-time algorithm that, given a digraph $D$, either produces an $F$-dicolouring of $D$, or correctly certifies that none exist. This yields the first linear-time algorithms to compute (di)colourings corresponding to the aforementioned generalisations of Brooks' theorem. In turn, it gives an unified framework to compute such colourings for various intermediate generalisations of Brooks' theorem such as list-(di)colouring and partitioning into (variable) degenerate sub(di)graphs., Comment: 26 pages, 5 figures

We prove the Effros-Hahn conjecture for groupoid algebras with coefficients in a sheaf, obtaining as a consequence a description of the ideals in skew inverse semigroup rings. We also use the description of the ideals to characterize when the groupoid algebras with coefficients in a sheaf are von Neumann regular, primitive, semiprimitive, or simple. We apply our results to the topological dynamics of actions of inverse semigroups, describing the existence of dense orbits and minimality in terms of primitivity and simplicity, respectively, of the associated algebra. Moreover, we apply our results to the usual complex groupoid algebra of continuous functions with compact support, used to build the C*-algebra associated with a groupoid, and describe criteria for its simplicity.

The leitmotiv of this paper is linking algebraic properties of an evolution algebra with combinatorial properties of the (possibly several) graphs that one can associate to the algebra. We link nondegeneracy, zero annihilator, absorption property, von Neumann regularity, and primeness with suitable properties in the associated graph. In the presence of semiprimeness, the property of primeness is equivalent to any associated graph being downward directed. We also provide a description of the prime ideals in an evolution algebra and prove that certain algebraic properties, such as semiprimeness and perfection, can not be characterized in combinatorial terms. We describe the centroid of evolution algebras as constant functions along the connected components of its associated graph. The dimension of the centroid of a zero annihilator algebra $A$ agrees with the cardinal of the connected components of any possible graph associated to $A$. This is the combinatorial expression of an algebraic uniqueness property in the decomposition of $A$ as indecomposable algebras with $1$-dimensional centroid.

We introduce the concept of "irrational paths" for a given subshift and use it to characterize all minimal left ideals in the associated unital subshift algebra. Consequently, we characterize the socle as the sum of the ideals generated by irrational paths. Proceeding, we construct a graph such that the Leavitt path algebra of this graph is graded isomorphic to the socle. This realization allows us to show that the graded structure of the socle serves as an invariant for the conjugacy of Ott-Tomforde-Willis subshifts and for the isometric conjugacy of subshifts constructed with the product topology. Additionally, we establish that the socle of the unital subshift algebra is contained in the socle of the corresponding unital subshift C*-algebra.

The driven Dicke model, wherein an ensemble of atoms is driven by an external field and undergoes collective spontaneous emission due to coupling to a leaky cavity mode, is a paradigmatic example of a system exhibiting a driven-dissipative phase transition as a function of driving strength. Recently, a similar phenomenon was experimentally observed, not in a cavity setting, but rather in a free-space atomic ensemble. The reason why similar behavior should emerge in free space is not obvious, as the system interacts with a continuum of optical modes, which encodes light propagation effects. Here, we present and solve a simple model to explain the behavior of the free-space system, based on the one-dimensional Maxwell-Bloch equations. On one hand, we show that a free-space ensemble at a low optical depth can exhibit similar behavior as the cavity system, as spatial propagation effects are negligible. On the other hand, in the thermodynamic limit of large atom number, we show that certain observables such as the transmittance or the atomic excited population exhibit non-analytic behavior as a function of the driving intensity, reminiscent of a phase transition. However, a closer analysis reveals that the atomic properties are highly inhomogeneous in space, and based on this we argue that the free-space system does not undergo a phase transition but rather a ``phase separation", roughly speaking, between saturated and unsaturated regions., Comment: 16 pages and 9 figures in the main text + 2 pages and 2 figures in the Appendix

In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} - \frac{k}{2} + 1$ by Addario-Berry et al. We give the first subquadratic bound for Burr's conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$., Comment: 17 pages, 2 figures

We associate a C*-algebra $\widetilde{\mathcal{O}}_{\textsf{X}}$ with a subshift over an arbitrary, possibly infinite, alphabet. We show that $\widetilde{\mathcal{O}}_{\textsf{X}}$ is a full invariant for topological conjugacy of the subshifts of Ott, Tomforde, and Willis. When the alphabet is countable, we show that $\widetilde{\mathcal{O}}_{\textsf{X}}$ is an invariant for isometric conjugacy of subshifts with the product metric. For a suitable partial action associated with a subshift over a countable alphabet, we show that $\widetilde{\mathcal{O}}_{\textsf{X}}$ is also an invariant for continuous orbit equivalence. Additionally, we give a concrete way to compute the K-theory of $\widetilde{\mathcal{O}}_{\textsf{X}}$ and illustrate it with two examples.

Plasma physics simulations create complex datasets for which researchers need state-of-the-art visualization tools to gain insights. These datasets are 3D in nature but are commonly depicted and analyzed using 2D idioms displayed on 2D screens. These offer limited understandability in a domain where spatial awareness is key. Virtual reality (VR) can be used as an alternative to conventional means for analyzing such datasets. VR has been known to improve depth and spatial relationship perception, which are fundamental for obtaining insights into 3D plasma morphology. Likewise, VR can potentially increase user engagement by offering more immersive and enjoyable experiences. Methods This study presents PlasmaVR, a proof-of-concept VR tool for visualizing datasets resulting from plasma physics simulations. It enables immersive multidimensional data visualization of particles, scalar, and vector fields and uses a more natural interface. The study includes user evaluation with domain experts where PlasmaVR was employed to assess the possible benefits of immersive environments in plasma physics visualization. The experimental group comprised five plasma physics researchers who were asked to perform tasks designed to represent their typical analysis workflow. To assess the suitability of the prototype for the different types of tasks, a set of objective metrics, such as completion time and number of errors, were measured. The prototype's usability was also evaluated using a standard System Usability Survey questionnaire.

In this paper we investigate the existence of subexponential parameterized algorithms of three fundamental cycle-hitting problems in geometric graph classes. The considered problems, \textsc{Triangle Hitting} (TH), \textsc{Feedback Vertex Set} (FVS), and \textsc{Odd Cycle Transversal} (OCT) ask for the existence in a graph $G$ of a set $X$ of at most $k$ vertices such that $G-X$ is, respectively, triangle-free, acyclic, or bipartite. Such subexponential parameterized algorithms are known to exist in planar and even $H$-minor free graphs from bidimensionality theory [Demaine et al., JACM 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of "fat" objects ([Grigoriev et al., FOCS 2022] and [Lokshtanov et al., SODA 2022]). In this paper we focus on "thin" objects by considering intersection graphs of segments in the plane with $d$ possible slopes ($d$-DIR graphs) and contact graphs of segments in the plane. Assuming the ETH, we rule out the existence of algorithms: - solving TH in time $2^{o(n)}$ in 2-DIR graphs; and - solving TH, FVS, and OCT in time $2^{o(\sqrt{n})}$ in $K_{2,2}$-free contact 2-DIR graphs. These results indicate that additional restrictions are necessary in order to obtain subexponential parameterized algorithms for %these problems. In this direction we provide: - a $2^{O(k^{3/4}\cdot \log k)}n^{O(1)}$-time algorithm for FVS in contact segment graphs; - a $2^{O(\sqrt d\cdot t^2 \log t\cdot k^{2/3}\log k)} n^{O(1)}$-time algorithm for TH in $K_{t,t}$-free $d$-DIR graphs; and - a $2^{O(k^{7/9}\log^{3/2}k)} n^{O(1)}$-time algorithm for TH in contact segment graphs.

Given a subshift over an arbitrary alphabet, we construct a representation of the associated unital algebra. We describe a criteria for the faithfulness of this representation in terms of the existence of cycles with no exits. Subsequently, we focus on describing the irreducible components of this representation and characterize equivalence between such components. Building upon these findings, we identify the minimal left ideals of a subshift algebra associated with (what we call) line paths.

Let $R$ be a commutative unital ring, $\textsf{X}$ a subshift, and $\widetilde{\mathcal{A}}_R(\textsf{X})$ the corresponding unital subshift algebra. We establish the reduction theorem for $\widetilde{\mathcal{A}}_R(\textsf{X})$. As a consequence, we obtain a Cuntz-Krieger uniqueness theorem for $\widetilde{\mathcal{A}}_R(\textsf{X})$ and we show that $\widetilde{\mathcal{A}}_R(\textsf{X})$ is semiprimitive (resp. semiprime) whenever $R$ is a field (resp. a domain)., Comment: 20 pages. Revised version. To appear in Revista de la Real Academia de Ciencias Exactas, F\'isicas y Naturales. Serie A. Matem\'aticas

In this paper, we develop the basic theory of the shadowing property for local homeomorphisms of metric locally compact spaces, with a focus on applications to edge shift spaces connected with C*-algebra theory. For the local homeomorphism (the Deaconu-Renault system) associated with a direct graph, we completely characterize the shadowing property in terms of conditions on sets of paths. Using these results, we single out classes of graphs for which the associated system presents the shadowing property, fully characterize the shadowing property for systems associated with certain graphs, and show that the system associated with the rose of infinite petals presents the shadowing property and that the Renewal shift system does not present the shadowing property.

We extend Nekrashevych's $KK$-duality for $C^*$-algebras of regular, recurrent, contracting self-similar group actions to regular, contracting self-similar groupoid actions on a graph, removing the recurrence condition entirely and generalising from a finite alphabet to a finite graph. More precisely, given a regular and contracting self-similar groupoid $(G,E)$ acting faithfully on a finite directed graph $E$, we associate two $C^*$-algebras, $\mathcal{O}(G,E)$ and $\widehat{\mathcal{O}}(G,E)$, to it and prove that they are strongly Morita equivalent to the stable and unstable Ruelle C*-algebras of a Smale space arising from a Wieler solenoid of the self-similar limit space. That these algebras are Spanier-Whitehead dual in $KK$-theory follows from the general result for Ruelle algebras of irreducible Smale spaces proved by Kaminker, Putnam, and the last author., Comment: File updated to make several corrections. Example 8.15 added

In this paper, we introduce topological entropy for dynamical systems generated by a single local homeomorphism (Deaconu-Renault systems). More precisely, we generalize Adler, Konheim, and McAndrew's definition of entropy via covers and Bowen's definition of entropy via separated sets. We propose a definition of factor map between Deaconu-Renault systems and show that entropy (via separated sets) always decreases under uniformly continuous factor maps. Since the variational principle does not hold in the full generality of our setting, we show that the proposed entropy via covers is a lower bound to the proposed entropy via separated sets. Finally, we compute entropy for infinite graphs (and ultragraphs) and compare it with the entropy of infinite graphs defined by Gurevich.

This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free. We give several structural properties of these graphs, and we raise several questions., Comment: Minor change

Given a partial action $\alpha$ of a groupoid $G$ on a ring $R$, we study the associated partial skew groupoid ring $R \rtimes_{\alpha} G$, which carries a natural $G$-grading. We show that there is a one-to-one correspondence between the $G$-invariant ideals of $R$ and the graded ideals of the $G$-graded ring $R \rtimes_{\alpha}G.$ We provide sufficient conditions for primeness, and necessary and sufficient conditions for simplicity of $R \rtimes_{\alpha}G.$ We show that every ideal of $R \rtimes_{\alpha}G$ is graded if, and only if, $\alpha$ has the residual intersection property. Furthermore, if $\alpha$ is induced by a topological partial action $\theta$, then we prove that minimality of $\theta$ is equivalent to $G$-simplicity of $R$, topological transitivity of $\theta$ is equivalent to $G$-primeness of $R$, and topological freeness of $\theta$ on every closed invariant subset of the underlying topological space is equivalent to $\alpha$ having the residual intersection property. As an application, we characterize condition (K) for an ultragraph in terms of topological properties of the associated partial action and in terms of algebraic properties of the associated ultragraph algebra., Comment: 39 pages. Added references

We introduce two algebras associated with a subshift over an arbitrary alphabet. One is unital and the other not necessarily. We focus on the unital case and describe a conjugacy between Ott-Tomforde-Willis subshifts in terms of a homeomorphism between the Stone duals of suitable Boolean algebras, and in terms of a diagonal-preserving isomorphism of the associated unital algebras. For this, we realise the unital algebra associated with a subshift as a groupoid algebra and as a partial skew group ring., Comment: 40 pages

Let $E$ be a directed graph, $\mathbb K$ be a field, and $\mathbb F$ be the free group on the edges of $E$. In this work, we use the isomorphism between Leavitt path algebras and partial skew group rings to endow $L_{\mathbb K}(E)$ with an $\mathbb F$-gradation and study some algebraic properties of this gradation. More precisely, we show that graded cleanness, graded unit-regularity, and strong gradeness of $L_{\mathbb K}(E)$ are all equivalent., Comment: 11 pages

We describe Markov interval maps via branching systems and develop the theory of relative branching systems, characterizing when the associated representations of relative graph C*-algebras are faithful. When the Markov interval maps $f$ have escape sets, we use our results to characterize injectivity of the associated relative graph algebra representations, improving on previous work by the first, third, and fourth authors.

Let $G$ be a connected graph with maximum degree $\Delta \geq 3$ distinct from $K_{\Delta + 1}$. Generalizing Brooks' Theorem, Borodin, Kostochka and Toft proved that if $p_1, \dots, p_s$ are non-negative integers such that $p_1 + \dots + p_s \geq \Delta - s$, then $G$ admits a vertex partition into parts $A_1, \dots, A_s$ such that, for $1 \leq i \leq s$, $G[A_i]$ is $p_i$-degenerate. Here we show that such a partition can be performed in linear time. This generalizes previous results that treated subcases of a conjecture of Abu-Khzam, Feghali and Heggernes~\cite{abu2020partitioning}, which our result settles in full., Comment: 12 pages, 4 figures, 5 algorithms

Despite all the efforts, there is no agreement on how temperature affects soil carbon decay and consequently soil CO2 emission, due to overlapping of environmental constraints. To gain further insight into the driving forces of soil microbial processes, we herein examine the abiotic physical environment and its potential influence on microbial activity. In this work we discuss a mechanism which is related to temperature sensitivity of soil carbon stability following a first-order kinetic theory. Soil carbon decomposition is linked to diffusion and consequently to water viscosity, splitting the effects of temperature from viscosity, here we suggest that viscosity could be a controlling factor on bacterial mobility and nutrient diffusion. As a result, viscosity effect on the potential soil carbon losses is demonstrated and could be an important influence in the feedbacks of climate change on soil carbon cycling kinetics., Comment: 15 pages and 3 figures

Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph $G$ is the minimum integer $d$ such that $G$ can be represented as a touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We show that proper minor-closed classes have bounded comparable box dimensions and explore further properties of this notion., Comment: 23 pages, 1 figure, accepted for presentation at SoCG 2022

There are two established gradings on Leavitt path algebras associated with ultragraphs, namely the grading by the integers group and the grading by the free group on the edges. In this paper, we characterize properties of these gradings in terms of the underlying combinatorial properties of the ultragraphs. More precisely, we characterize when the gradings are strong or epsilon-strong. The results regarding the free group on the edges are new also in the context of Leavitt path algebras of graphs. Finally, we also describe the relation between the strongness of the integer grading on an ultragraph Leavitt path algebra and the saturation of the gauge action associated with the corresponding ultragraph C*-algebra.