Search

We consider $n\times n$ real-valued matrices $A = (a_{ij})$ satisfying $a_{ii} \geq a_{i,i+1} \geq \dots \geq a_{in} \geq a_{i1} \geq \dots \geq a_{i,i-1}$ for $i = 1,\dots,n$. With such a matrix $A$ we associate a directed graph $G(A)$. We prove that the solutions to the system $A^T x = \lambda e$, with $\lambda \in \mathbb{R}$ and $e$ the vector of all ones, are linear combinations of 'fundamental' solutions to $A^T x=e$ and vectors in $\ker A^T$, each of which is associated with a closed strongly connected component (SCC) of $G(A)$. This allows us to characterize the sign of $\det A$ in terms of the number of closed SCCs and the solutions to $A^T x = e$. In addition, we provide conditions for $A$ to be a $P$-matrix., Comment: 17 pages, 2 figures; minor changes in introduction, added Figure 1, corrected typos

We present the first steps towards the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to ±1. Here we deal with the disconnected, the bipartite and the complete signed graphs. In addition, we present many examples which cannot be obtained from an unsigned graph or its negative by switching.

Let H be a field with Q⊆H⊆C, and let p(λ) be a polynomial in H[λ], and let A∈Hn×n be nonderogatory. In this paper we consider the problem of finding a solution X∈Hn×n to p(X)=A. A necessary condition for this to be possible is already known from a paper by M.P. Drazin: Exact rational solutions of the matrix equation A=p(X) by linearization. Under an additional condition we provide an explicit construction of such solutions. The similarities and differences with the derogatory case will be discussed as well. One of the tools needed in the paper is a new canonical form, which may be of independent interest. It combines elements of the rational canonical form with elements of the Jordan canonical form.

Discrete Mathematics, 346 (9), ISSN:0012-365X, ISSN:1872-681X

This paper addresses two questions: (a) can we identify a sensible class of 2-parameter persistence modules on which the rank invariant is complete? (b) can we determine efficiently whether a given 2-parameter persistence module belongs to this class? We provide positive answers to both questions, and our class of interest is that of rectangle-decomposable modules. Our contributions include: on the one hand, a proof that the rank invariant is complete on rectangle-decomposable modules, together with an inclusion-exclusion formula for counting the multiplicities of the summands; on the other hand, algorithms to check whether a module induced in homology by a bifiltration is rectangle-decomposable, and to decompose it in the affirmative, with a better complexity than state-of-the-art decomposition methods for general 2-parameter persistence modules. Our algorithms are backed up by a new structure theorem, whereby a 2-parameter persistence module is rectangle-decomposable if, and only if, its restrictions to squares are. This local characterization is key to the efficiency of our algorithms, and it generalizes previous conditions derived for the smaller class of block-decomposable modules. It also admits an algebraic formulation that turns out to be a weaker version of the one for block-decomposability. By contrast, we show that general interval-decomposability does not admit such a local characterization, even when locality is understood in a broad sense. Our analysis focuses on the case of modules indexed over finite grids, the more general cases are left as future work., Comment: This is the final version to be published in DCG. Changed the algorithm in Section 3 for computing the rank invariant, which was incorrect. The new algorithm reduces to computing 1-parameter vineyards along a family of paths in the grid. It was first proposed in the PhD thesis of D. Morozov

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon etal. (2010). It models the diffusion process of information in social networks where several competitive companies want to spread their information, for example. The nature of this game strongly depends on the graph topology, and the relationship is studied from several aspects. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on split graphs, block graphs, and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that a pure Nash equilibrium does not always exist on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

The evolution of online social networks is highly dependent on the recommended links. Most of the existing works focus on predicting intra-community links efficiently. However, it is equally important to predict inter-community links with high accuracy for diversifying a network. In this work, we propose a link prediction method, called HM-EIICT, that considers both the similarity of nodes and their community information to predict both kinds of links, intra-community links as well as inter-community links, with higher accuracy. The proposed framework is built on the concept that the connection likelihood between two given nodes differs for inter-community and intra-community node-pairs. The performance of the proposed methods is evaluated using link prediction accuracy and network modularity reduction. The results are studied on real-world networks and show the effectiveness of the proposed method as compared to the baselines. The experiments suggest that the inter-community links can be predicted with a higher accuracy using community information extracted from the network topology, and the proposed framework outperforms several measures especially proposed for community-based link prediction. The paper is concluded with open research directions.

Mixed-frequency Vector AutoRegressions (MF-VAR) model the dynamics between variables recorded at different frequencies. However, as the number of series and high-frequency observations per low-frequency period grow, MF-VARs suffer from the "curse of dimensionality". We curb this curse through a regularizer that permits hierarchical sparsity patterns by prioritizing the inclusion of coefficients according to the recency of the information they contain. Additionally, we investigate the presence of nowcasting relations by sparsely estimating the MF-VAR error covariance matrix. We study predictive Granger causality relations in a MF-VAR for the U.S. economy and construct a coincident indicator of GDP growth. Supplementary Materials for this article are available online., Forthcoming in Journal of Computational and Graphical Statistics

We introduce the concept of codeterminantal graphs, which generalize the concepts of cospectral and coinvariant graphs. To do this, we investigate the relationship of the spectrum and the Smith normal form (SNF) with the determinantal ideals. We establish a necessary and sufficient condition for graphs to be codeterminantal on R[x], and we present some computational results on codeterminantal graphs up to 9 vertices. Finally, we show that complete graphs and star graphs are determined by the SNF of its distance Laplacian matrix.

In this paper we are concerned with the least energy solutions to the Lane-Emden problem driven by an anisotropic operator, so-called the Finsler \begin{document}$ N $\end{document}-Laplacian, on a bounded domain in \begin{document}$ {\mathbb{R}}^N $\end{document}. We prove several asymptotic formulae as the nonlinear exponent gets large.

We investigate questions related to the set $\mathcal{SEP}_d$ consisting of the linear maps $\rho$ acting on $\mathbb{C}^d\otimes \mathbb{C}^d$ that can be written as a convex combination of rank one matrices of the form $xx^*\otimes yy^*$. Such maps are known in quantum information theory as the separable bipartite states, while nonseparable states are called entangled. In particular we introduce bounds for the separable rank $\mathrm{rank_{sep}}(\rho)$, defined as the smallest number of rank one states $xx^*\otimes yy^*$ entering the decomposition of a separable state $\rho$. Our approach relies on the moment method and yields a hierarchy of semidefinite-based lower bounds, that converges to a parameter $\tau_{\mathrm{sep}}(\rho)$, a natural convexification of the combinatorial parameter $\mathrm{rank_{sep}}(\rho)$. A distinguishing feature is exploiting the positivity constraint $\rho-xx^*\otimes yy^* \succeq 0$ to impose positivity of a polynomial matrix localizing map, the dual notion of the notion of sum-of-squares polynomial matrices. Our approach extends naturally to the multipartite setting and to the real separable rank, and it permits strengthening some known bounds for the completely positive rank. In addition, we indicate how the moment approach also applies to define hierarchies of semidefinite relaxations for the set $\mathcal{SEP}_d$ and permits to give new proofs, using only tools from moment theory, for convergence results on the DPS hierarchy from (A.C. Doherty, P.A. Parrilo and F.M. Spedalieri. Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18):187904, 2002).

We show that the edges of any graph $G$ containing two edge-disjoint spanning trees can be blue/red coloured so that the blue and red graphs are connected and the blue and red degrees at each vertex differ by at most four. This improves a result of H\"orsch. We discuss variations of the question for digraphs, infinite graphs and a computational question, and resolve two further questions of H\"orsch in the negative., Comment: 23 pages, 22 figures

In this paper, we consider two-term fractional differential equations (FDEs) with boundary conditions. We use operator techniques including Fourier multipliers, perturbation theory of operators, the trace theorem, and Green\"s functions to establish maximal regularity of three types of FDEs with nonlocal or Dirichlet boundary conditions in Lp-space. As an application, the existence-uniqueness and coercive estimate of the Cauchy problem for fractional parabolic differential equation are given.

Given a set $P$ of $n$ points in $\mathbb{R}^2$ and an input line $\gamma$ in $\mathbb{R}^2$, we present an algorithm that runs in optimal $\Theta(n\log n)$ time and $\Theta(n)$ space to solve a restricted version of the $1$-Steiner tree problem. Our algorithm returns a minimum-weight tree interconnecting $P$ using at most one Steiner point $s \in \gamma$, where edges are weighted by the Euclidean distance between their endpoints. We then extend the result to $j$ input lines. Following this, we show how the algorithm of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) that solves the $k$-Steiner tree problem in $\mathbb{R}^2$ in $O(n^{2k})$ time can be adapted to our setting. For $k>1$, restricting the (at most) $k$ Steiner points to lie on an input line, the runtime becomes $O(n^{k})$. Next we show how the results of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) allow us to maintain the same time and space bounds while extending to some non-Euclidean norms and different tree cost functions. Lastly, we extend the result to $j$ input curves., Comment: 31 pages (26 of content), 4 figures (last one as 3 subfigures). Minor corrections since publication: notably our analysis of the Brazil et al. k-steiner tree algorithm in section 4.1 (results unchanged), and a correction to some corollary statements to correct the space usage. Also added short discussion of how the algorithm still works when the MST of the input point set is not unique

Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several well-known eigenvalue bounds. In this work we aim to further our algebraic and computational understanding of weight-equitable partitions. We do so by showing several spectral properties and algebraic characterizations, and by providing a method to find coarse weight-equitable partitions.

Existing changepoint approaches consider changepoints to occur linearly in time; one changepoint happens after another and they are not linked. However, data processes may have regularly occurring changepoints, for example, a yearly increase in sales of ice-cream on the first hot weekend. Using linear changepoint approaches here will miss more global features such as a decrease in sales of ice-cream due to other product availability. Being able to tease these global changepoint features from the more local (periodic) ones is beneficial for inference. We propose a periodic changepoint model to model this behavior using a mixture of a periodic and linear time perspective. Built around a Reversible Jump Markov chain Monte Carlo sampler, the Bayesian framework is used to study the local (periodic) changepoint behavior. To identify the optimal global changepoint positions we integrate the local changepoint model into the pruned exact linear time (PELT) search algorithm. We demonstrate that the method detects both local and global changepoints with high accuracy on simulated and motivating applications that share periodic behavior. Due to the micro–macro nature of the analysis, visualization of the results can be challenging. We additionally provide a unique perspective for changepoint visualizations in these data sequences. Supplementary Materials for this article are available online.

We formulate two fairness principles and characterize the league competition systems that satisfy them. The first principle requires that all players should have the same chance of being the final winner if all players are equally strong, while the second states that the league competition should not favor weaker players. We apply these requirements to a class of systems which includes round-robin tournaments as a particular case. Financial support from the Spanish Ministry of Science and Technology (Project ECO2015-65031-R MINECO/FEDER, UE) is acknowledged. Open Access funding enabled and organized by Projekt DEAL.

The Kuramoto Model (KM) is a nonlinear model widely used to model synchrony in a network of oscillators – from the synchrony of the flashing fireflies to the hand clapping in an auditorium. Recently, a modification of the KM (complex-valued KM) was introduced with an analytical solution expressed in terms of a matrix exponential, and consequentially, its eigensystem. Remarkably, the analytical KM and the original KM bear significant similarities, even with phase lag introduced, despite being determined by distinct systems. We found that this approach gives a geometric perspective of synchronization phenomena in terms of complex eigenmodes, which in turn offers a unified geometry for synchrony, chimera states, and waves in nonlinear oscillator networks. These insights are presented in Chapter 2 of this thesis. This surprising connection between the eigenspectrum of the adjacency matrix of a ring graph and its Kuramoto dynamics invites the question: what is the eigenspectrum of joins of circulant matrices? We answered this question in Chapter 3 of this thesis.

International audience; We introduce a total order on n-simplices in the n-Euclidean space for which the support of the lexicographic-minimal chain with the convex hull boundary as boundary constraint is precisely the n-dimensional Delaunay triangulation, or in a more general setting, the regular triangulation of a set of weighted points. This new characterization of regular and Delaunay triangulations is motivated by its possible generalization to submanifold triangulations as well as the recent development of polynomial-time triangulation algorithms taking advantage of this order.

In this paper, a class of nonlocal fractional Dirichlet problems is studied. By using a variational principle due to Ricceri (whose original version was given in J. Comput. Appl. Math. 113 (2000), 401-410), the existence of infinitely many weak solutions for these problems is established by requiring that the nonlinear term $f$ has a suitable oscillating behaviour either at the origin or at infinity.

In [19], Taslaman, Tisseur, and Zaballa show that any regular matrix polynomial P (λ)over an algebraically closed field is spectrally equivalent to a triangular matrix polynomial of the same degree. When P (λ)is real and regular, they also show that there is a real quasi-triangular matrix polynomial of the same degree that is spectrally equivalent to P (λ), in which the diagonal blocks are of size at most 2 × 2. This paper generalizes these results to regular matrix polynomials P (λ)over arbitrary fields F, showing that any such P (λ) can be quasi-triangularized to a spectrally equivalent matrix polynomial over F of the same degree, in which the largest diagonal block size is bounded by the highest degree appearing among all of the F-irreducible factors in the Smith form for P (λ). This publication is part of the "Proyecto de I+D+i PID2019-106362GB-I00 financiado por MCIN/AEI/10.13039/501100011033". It has been also funded by Ministerio de Economía, Industria y Competitividad (MINECO) of Spain through grants MTM-2015-65798-P and BES-2013-065688. Funding for APC: Universidad Carlos III de Madrid (Read & Publish Agreement CRUE-CSIC 2023).

We quantise Whitney’s construction to prove the existence of a triangulation for any$$C^2$$C2manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric.

Graphs (i.e., networks) have become an integral tool for the representation and analysis of relational data. Advances in data gathering have led to multirelational data sets which exhibit greater depth and scope. In certain cases, this data can be modelled using a hypergraph. However, in practice analysts typically reduce the dimensionality of the data (whether consciously or otherwise) to accommodate a traditional graph model. In recent years spectral hypergraph theory has emerged to study the eigenpairs of the adjacency hypermatrix of a uniform hypergraph. We show how analyzing multi-relational data, via a hypermatrix associated to the aforementioned hypergraph, can lead to conclusions different from those when the data is projected down to its cooccurrence matrix. To this end we consider how the principal eigenvector of a hypergraph and its shadow can vary in terms of their spectral rankings, Pearson/Spearman correlation coefficient, and Chebyshev distance. In particular, we provide an example of a uniform hypergraph where the most central vertex (`a la eigencentrality) changes depending on the order of the associated matrix. To the best of our knowledge this is the first known hypergraph to exhibit this property. We further show that the aforementioned eigenvectors have a high Pearson correlation but are uncorrelated under the Spearman correlation coefficient.

We describe primitive association schemes $\mathfrak{X}$ of degree $n$ such that $\mathrm{Aut}(\mathfrak{X})$ is imprimitive and $|\mathrm{Aut}(\mathfrak{X})| \geq \exp(n^{1/8})$, contradicting a conjecture of Babai. This and other examples we give are the first known examples of nonschurian primitive coherent configurations (PCC) with more than a quasipolynomial number of automorphisms. Our constructions are "Hamming sandwiches", association schemes sandwiched between the $d$th tensor power of the trivial scheme and the $d$-dimensional Hamming scheme. We study Hamming sandwiches in general, and exhaustively for $d \leq 8$. We revise Babai's conjecture by suggesting that any PCC with more than a quasipolynomial number of automorphisms must be an association scheme sandwiched between a tensor power of a Johnson scheme and the corresponding full Cameron scheme. If true, it follows that any nonschurian PCC has at most $\exp O(n^{1/8} \log n)$ automorphisms., 21 pages. Minor correction to Lemma 4.7(2). Final version incorporating referees' comments. To appear in Combinatorica

Recently geometric hypergraphs that can be defined by intersections of pseudohalfplanes with a finite point set were defined in a purely combinatorial way. This led to extensions of earlier results about points and halfplanes to pseudohalfplanes, including polychromatic colorings and discrete Helly-type theorems about pseudohalfplanes. Here we continue this line of research and introduce the notion of convex sets of such pseudohalfplane hypergraphs. In this context we prove several results corresponding to classical results about convexity, namely Helly's Theorem, Carath\'eodory's Theorem, Kirchberger's Theorem, Separation Theorem, Radon's Theorem and the Cup-Cap Theorem. These results imply the respective results about pseudoconvex sets in the plane defined using pseudohalfplanes. It turns out that most of our results can be also proved using oriented matroids and topological affine planes (TAPs) but our approach is different from both of them. Compared to oriented matroids, our theory is based on a linear ordering of the vertex set which makes our definitions and proofs quite different and perhaps more elementary. Compared to TAPs, which are continuous objects, our proofs are purely combinatorial and again quite different in flavor. Altogether, we believe that our new approach can further our understanding of these fundamental convexity results.

We establish an equivalence between two approaches to quantization of irreducible symmetric spaces of compact type within the framework of quasi-coactions, one based on the Enriquez-Etingof cyclotomic Knizhnik-Zamolodchikov (KZ) equations and the other on the Letzter-Kolb coideals. This equivalence can be upgraded to that of ribbon braided quasi-coactions, and then the associated reflection operators (K-matrices) become a tangible invariant of the quantization. As an application we obtain a Kohno-Drinfeld type theorem on type B braid group representations defined by the monodromy of KZ-equations and by the Balagovi\'c-Kolb universal K-matrices. The cases of Hermitian and non-Hermitian symmetric spaces are significantly different. In particular, in the latter case a quasi-coaction is essentially unique, while in the former we show that there is a one-parameter family of mutually nonequivalent quasi-coactions., Comment: v2: minor changes; v1: 62 pages

We study rotation $r$-graphs and show that for every $r$-graph $G$ of odd regularity there is a simple rotation $r$-graph $G'$ such that $G$ can be obtained form $G'$ by a finite number of $2$-cut reductions. As a consequence, some hard conjectures as the (generalized) Berge-Fulkerson Conjecture and Tutte's 3- and 5-flow conjecture can be reduced to rotation $r$-graphs., 9 pages

We focus on the maximum number of minimal transversals in 3-partite 3-uniform hypergraphs on n vertices. Those hypergraphs (and their minimal transversals) are commonly found in database applications. In this paper we prove that this number grows at least like 1.4977^n and at most like 1.5012^n.

We study distinct $(0,1)$ matrices $A$ and $B$, called \textit{Gram mates}, such that $AA^T=BB^T$ and $A^TA=B^TB$. We characterize Gram mates where one can be obtained from the other by changing signs of some positive singular values. We classify Gram mates such that the rank of their difference is at most $2$. Among such Gram mates, we further produce equivalent conditions in order that one is obtained from the other by changing signs of at most $2$ positive singular values. Moreover, we provide some tools for constructing Gram mates where the rank of their difference is more than $2$. Finally, we characterize non-isomorphic Gram mates whose difference is of rank $1$ with some extra conditions.

Machine learning algorithms play an important role in a variety of important decision-making processes, including targeted advertisement displays, home loan approvals, and criminal behavior predictions. Given the far-reaching impact of these algorithms, it is crucial that they operate fairly, free from bias or prejudice towards certain groups in the population. Ensuring impartiality in these algorithms is essential for promoting equality and avoiding discrimination. To this end we introduce a unified framework for randomized subset selection that incorporates group fairness constraints. Our problem involves a global utility function and a set of group utility functions for each group, here a group refers to a group of individuals (e.g., people) sharing the same attributes (e.g., gender). Our aim is to generate a distribution across feasible subsets, specifying the selection probability of each feasible set, to maximize the global utility function while meeting a predetermined quota for each group utility function in expectation. Note that there may not necessarily be any direct connections between the global utility function and each group utility function. We demonstrate that this framework unifies and generalizes many significant applications in machine learning and operations research. Our algorithmic results either improves the best known result or provide the first approximation algorithms for new applications., This paper has been accepted for publication in the Journal on Combinatorial Optimization

The generalized circumradius of a set of points $A \subseteq \mathbb{R}^d$ with respect to a convex body $K$ equals the minimum value of $\lambda \geq 0$ such that $A$ is contained in a translate of $\lambda K$. Each choice of $K$ gives a different function on the set of bounded subsets of $\mathbb{R}^d$; we characterize which functions can arise in this way. Our characterization draws on the theory of diversities, a recently introduced generalization of metrics from functions on pairs to functions on finite subsets. We additionally investigate functions which arise by restricting the generalised circumradius to a finite subset of $\mathbb{R}^d$. We obtain elegant characterizations in the case that $K$ is a simplex or parallelotope., Comment: To be published in Discrete and Computational Geometry

This paper surveys recent work by the author on the theoretical and algorithmic aspects of restless bandit indexation as well as on its application to a variety of problems involving the dynamic allocation of priority to multiple stochastic projects. The main aim is to present ideas and methods in an accessible form that can be of use to researchers addressing problems of such a kind. Besides building on the rich literature on bandit problems, our approach draws on ideas from linear programming, economics, and multi-objective optimization. In particular, it was motivated to address issues raised in the seminal work of Whittle (Restless bandits: activity allocation in a changing world. In: Gani J. (ed.) A Celebration of Applied Probability, J. Appl. Probab., vol. 25A, Applied Probability Trust, Sheffield, pp. 287-298, 1988) where he introduced the index for restless bandits that is the starting point of this work. Such an index, along with previously proposed indices and more recent extensions, is shown to be unified through the intuitive concept of ``marginal productivity index'' (MPI), which measures the marginal productivity of work on a project at each of its states. In a multi-project setting, MPI policies are economically sound, as they dynamically allocate higher priority to those projects where work appears to be currently more productive. Besides being tractable and widely applicable, a growing body of computational evidence indicates that such index policies typically achieve a near-optimal performance and substantially outperform benchmark policies derived from conventional approaches., 7 figures

In this paper, we study a variant of graph domination known as $(t, r)$ broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretour in 2015. In this variant, each broadcast provides $t-d$ reception to each vertex a distance $d < t$ from the broadcast. If $d \ge t$ then no reception is provided. A vertex is considered dominated if it receives $r$ total reception from all broadcasts. Our main results provide some upper and lower bounds on the density of a $(t, r)$ dominating pattern of an infinite grid, as well as methods of computing them. Also, when $r \ge 2$ we describe a family of counterexamples to a generalization of Vizing's Conjecture to $(t,r)$ broadcast domination., 13 pages, 4 figures

In this paper we discuss a result similar to the polynomial version of the Alon-F\"uredi theorem. We prove that if you want to cover the vertices of the $n$-dimensional unit cube, except those of weight at most $r$ then you need an algebraic surface of degree at least $n-r$., Comment: 5 pages, published

We show that the counting sequence for permutations avoiding both of the (classical) patterns 1243 and 2134 has the algebraic generating function supplied by Vaclav Kotesovec for sequence A164651 in The On-Line Encyclopedia of Integer Sequences., Comment: 8 pages, 2 figures, final version, to appear, Discrete Mathematics & Theoretical Computer Science (DMTCS)

Orthogonal matrices which are linear combinations of permutation matrices have attracted enormous attention in quantum information and computation. In this paper, we provide a complete parametric characterization of all complex, real and rational orthogonal permutative matrices of order $4.$ We show that any such matrix can always be expressed as a linear combination of up to four permutation matrices. Finally we determine several matrix spaces generated by linearly independent permutation matrices such that any orthogonal matrix in these spaces is always permutative or direct sum of orthogonal permutative matrices up to permutation of its rows and columns., 18 pages. arXiv admin note: substantial text overlap with arXiv:2103.00515

We study a family of generalizations of Edge Dominating Set on directed graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc $(u,v)$ is said to dominate itself, as well as all arcs which are at distance at most $q$ from $v$, or at distance at most $p$ to $u$. First, we give significantly improved FPT algorithms for the two most important cases of the problem, $(0,1)$-dEDS and $(1,1)$-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that $(p,q)$-dEDS is FPT parameterized by $p+q+tw$, but W-hard parameterized by $tw$ (even if the size of the optimal is added as a second parameter), where $tw$ is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of $p,q$, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case $(p=q=1)$ which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.

In many scientific research fields, understanding and visualizing a black-box function in terms of the effects of all the input variables is of great importance. Existing visualization tools do not allow one to visualize the effects of all the input variables simultaneously. Although one can select one or two of the input variables to visualize via a 2D or 3D plot while holding other variables fixed, this presents an oversimplified and incomplete picture of the model. To overcome this shortcoming, we present a new visualization approach using an interpretable architecture neural network (IANN) to visualize the effects of all the input variables directly and simultaneously. We propose two interpretable structures, each of which can be conveniently represented by a specific IANN, and we discuss a number of possible extensions. We also provide a Python package to implement our proposed method. The supplemental materials are available online.

International audience; Symmetric Positive Definite (SPD) matrices are ubiquitous in data analysis under the form of covariance matrices or correlation matrices. Several O(n)-invariant Riemannian metrics were defined on the SPD cone, in particular the kernel metrics introduced by Hiai and Petz. The class of kernel metrics interpolates between many classical O(n)-invariant metrics and it satisfies key results of stability and completeness. However, it does not contain all the classical O(n)-invariant metrics. Therefore in this work, we investigate super-classes of kernel metrics and we study which key results remain true. We also introduce an additional key result called cometric-stability, a crucial property to implement geodesics with a Hamiltonian formulation. Our method to build intermediate embedded classes between O(n)-invariant metrics and kernel metrics is to give a characterization of the whole class of O(n)-invariant metrics on SPD matrices and to specify requirements on metrics one by one until we reach kernel metrics. As a secondary contribution, we synthesize the literature on the main O(n)-invariant metrics, we provide the complete formula of the sectional curvature of the affine-invariant metric and the formula of the geodesic parallel transport between commuting matrices for the Bures-Wasserstein metric.

Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying $\Pi$. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size $n$ of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of $O(\log \log n)$ bits per node in any $n$-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use $\Omega(\log \log n)$-bit per node registers in some $n$-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms., Comment: Final journal version for DMTCS (Conference version at OPODIS 2021)

A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t ω(G - X)≤ |X| for all X ∩ V (G) with ω (G - X) > 1. The toughness of G, denoted τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = ∞ for all n ≥ 1). It is known that a Hamilton-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K1 ? P4 itself. We leave this as an open case.

Pursuit-evasion games study the number of cops needed to capture the robber in a game played on a graph, in which the cops and the robber move alternatively to neighbouring vertices, and the robber is captured if a cop steps on the vertex the robber is in. A common tool in analyzing this cop number of a graph is a cop moving along a shortest path in a graph, thus preventing the robber to step onto this path. We generalize this approach by introducing a shadow of the robber, the maximal set of vertices from which the cop parries the protected subgraph. In this context, the robber becomes an intruder and the cop becomes the guard. We show that the shadow can be computed in polynomial time, implying polynomial time algorithms for computing both a successful guard as well as a successful intruder, whichever exists. Furthermore, we show that shadow function generalizes the concept of graph retractions. In some cases, this implies a polynomially computable certification of the negative answer to the NP-complete problem of existence of a retraction to a given subgraph.

A linear hypergraph, also known as a partial Steiner system, is a collection of subsets of a set such that no two of the subsets have more than one element in common. Most studies of linear hypergraphs consider only the uniform case, in which all the subsets have the same size. In this paper we provide, for the first time, asymptotically precise estimates of the number of linear hypergraphs in the non-uniform case, as a function of the number of subsets of each size.

For an integer k ≥ 2, a k-tree T is defined as a tree with maximum degree at most k. If a k-tree T spans a graph G, then T is called a spanning k-tree of G. Since a spanning 2-tree is a Hamiltonian path, a spanning k-tree is an extended concept of a Hamiltonian path. The first result, implying the existence of k-trees in star-free graphs, was by Caro, Krasikov, and Roditty in 1985, and independently, Jackson and Wormald in 1990, who proved that for any integer k with k ≥ 3, every connected K1,k-free graph contains a spanning k-tree. In this paper, we focus on a sharp condition that guarantees the existence of a spanning k-tree in K1,k+1-free graphs. In particular, we show that every connected K1,k+1-free graph G has a spanning k-tree if the degree sum of any 3k − 3 independent vertices in G is at least |G| − 2, where |G| is the order of G.

A set D of vertices in a graph G is a dominating set of G if every vertex outside D is adjacent in G to some vertex in D. A set D of vertices in G is a semitotal dominating set of G if D is a dominating set of G and every vertex in D is within distance 2 from another vertex of D. Given a graph G and a positive integer k, the semitotal domination problem is to decide whether G has a semitotal dominating set of cardinality at most k. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.

In this paper, we study the weak Roman domination number and the secure domination number of lexicographic product graphs. In particular, we show that these two parameters coincide for almost all lexicographic product graphs. Furthermore, we obtain tight bounds and closed formulas for these parameters.

The design of optimal Magnetic Resonance Imaging (MRI) coils is modeled as a minimum-norm problem (MNP), that is, as an optimization problem of the form $\min_{x\in\mathcal{R}}\|x\|$ min x ∈ R ∥ x ∥ , where $\mathcal{R}$ R is a closed and convex subset of a normed space X. This manuscript is aimed at revisiting MNPs from the perspective of Functional Analysis, Operator Theory, and Banach Space Geometry in order to provide an analytic solution to the following MRI problem: $\min_{\psi\in\mathcal{R}}\|\psi\|_{2}$ min ψ ∈ R ∥ ψ ∥ 2 , where $\mathcal{R}:=\{\psi\in \mathbb{R}^{n}:\frac{\|A\psi-b\|_{\infty}}{\|b\|_{\infty}} \leq D\}$ R : = { ψ ∈ R n : ∥ A ψ − b ∥ ∞ ∥ b ∥ ∞ ≤ D } , with $A\in\mathcal{M}_{m\times n}(\mathbb{R})$ A ∈ M m × n ( R ) , $D>0$ D > 0 , and $b\in\mathbb{R}^{m}\setminus\{0\}$ b ∈ R m ∖ { 0 } .

An embedding of a graph H in a graph G is an injection (i.e., a one-to-one function) σ from the vertices of H to the vertices of G such that σ(x)σ(y) is an edge of G for all edges xy of H. The image of H in G under σ is denoted by σ(H). A k-packing of a graph H in a graph G is a sequence (σ1, σ2,…, σk) of embeddings of H in G such that σ1(H), σ2(H),…, σk(H) are edge disjoint. We prove that for any tree T of order n, there is a 4-packing of T in a complete bipartite graph of order at most n + 12.