A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs which occur are odd cycles and complete graphs. In this article we present a series of theoretical results which contribute to a computer search verifying this conjecture for all groups of size up to 1024. The conjecture is also verified theoretically for several infinite families of groups including dihedral and some families of nilpotent groups. Two key results which enable the computer search to reach as far as it does are: if the center of a group has even order, then the conjecture holds (this eliminates all 2-groups from our computer search); if a Cayley graph is geodetic then there are bounds relating the size of the group, generating set and center (which cuts down the number of generating sets which must be searched significantly).
相關內容
Group一直是研究計算機支持的合作工作、人機交互、計算機支持的協作學習和社會技術研究的主要場所。該會議將社會科學、計算機科學、工程、設計、價值觀以及其他與小組工作相關的多個不同主題的工作結合起來，并進行了廣泛的概念化。官網鏈接： ·
Processing（編程語言）
·
MoDELS
·
似然
·
馬爾可夫過程
·
Multistate Markov models are a canonical parametric approach for data modeling of observed or latent stochastic processes supported on a finite state space. Continuous-time Markov processes describe data that are observed irregularly over time, as is often the case in longitudinal medical data, for example. Assuming that a continuous-time Markov process is time-homogeneous, a closed-form likelihood function can be derived from the Kolmogorov forward equations -- a system of differential equations with a well-known matrix-exponential solution. Unfortunately, however, the forward equations do not admit an analytical solution for continuous-time, time-inhomogeneous Markov processes, and so researchers and practitioners often make the simplifying assumption that the process is piecewise time-homogeneous. In this paper, we provide intuitions and illustrations of the potential biases for parameter estimation that may ensue in the more realistic scenario that the piecewise-homogeneous assumption is violated, and we advocate for a solution for likelihood computation in a truly time-inhomogeneous fashion. Particular focus is afforded to the context of multistate Markov models that allow for state label misclassifications, which applies more broadly to hidden Markov models (HMMs), and Bayesian computations bypass the necessity for computationally demanding numerical gradient approximations for obtaining maximum likelihood estimates (MLEs). Supplemental materials are available online.
The "classical" (weak) greedy algorithm is widely used within model order reduction in order to compute a reduced basis in the offline training phase: An a posteriori error estimator is maximized and the snapshot corresponding to the maximizer is added to the basis. Since these snapshots are determined by a sufficiently detailed discretization, the offline phase is often computationally extremely costly. We suggest to replace the serial determination of one snapshot after the other by a parallel approach. In order to do so, we introduce a batch size $b$ and add $b$ snapshots to the current basis in every greedy iteration. These snapshots are computed in parallel. We prove convergence rates for this new batch greedy algorithm and compare them to those of the classical (weak) greedy algorithm in the Hilbert and Banach space case. Then, we present numerical results where we apply a (parallel) implementation of the proposed algorithm to the linear elliptic thermal block problem. We analyze the convergence rate as well as the offline and online wall-clock times for different batch sizes. We show that the proposed variant can significantly speed-up the offline phase while the size of the reduced problem is only moderately increased. The benefit of the parallel batch greedy increases for more complicated problems.
We consider the discretization of the $1d$-integral Dirichlet fractional Laplacian by $hp$-finite elements. We present quadrature schemes to set up the stiffness matrix and load vector that preserve the exponential convergence of $hp$-FEM on geometric meshes. The schemes are based on Gauss-Jacobi and Gauss-Legendre rules. We show that taking a number of quadrature points slightly exceeding the polynomial degree is enough to preserve root exponential convergence. The total number of algebraic operations to set up the system is $\mathcal{O}(N^{5/2})$, where $N$ is the problem size. Numerical example illustrate the analysis. We also extend our analysis to the fractional Laplacian in higher dimensions for $hp$-finite element spaces based on shape regular meshes.
Houdr\'e and Tetali defined a class of isoperimetric constants $\varphi_p$ of graphs for $0 \leq p \leq 1$, and conjectured a Cheeger-type inequality for $\varphi_\frac12$ of the form $$\lambda_2 \lesssim \varphi_\frac12 \lesssim \sqrt{\lambda_2}$$ where $\lambda_2$ is the second smallest eigenvalue of the normalized Laplacian matrix. If true, the conjecture would be a strengthening of the hard direction of the classical Cheeger's inequality. Morris and Peres proved Houdr\'e and Tetali's conjecture up to an additional log factor, using techniques from evolving sets. We present the following related results on this conjecture. - We provide a family of counterexamples to the conjecture of Houdr\'e and Tetali, showing that the logarithmic factor is needed. - We match Morris and Peres's bound using standard spectral arguments. - We prove that Houdr\'e and Tetali's conjecture is true for any constant $p$ strictly bigger than $\frac12$, which is also a strengthening of the hard direction of Cheeger's inequality. Furthermore, our results can be extended to directed graphs using Chung's definition of eigenvalues for directed graphs.
Several different types of identification problems have been already studied in the literature, where the objective is to distinguish any two vertices of a graph by their unique neighborhoods in a suitably chosen dominating or total-dominating set of the graph, often referred to as a \emph{code}. To study such problems under a unifying point of view, reformulations of the already studied problems in terms of covering problems in suitably constructed hypergraphs have been provided. Analyzing these hypergraph representations, we introduce a new separation property, called \emph{full-separation}, which has not yet been considered in the literature so far. We study it in combination with both domination and total-domination, and call the resulting codes \emph{full-separating-dominating codes} (or \emph{FD-codes} for short) and \emph{full-separating-total-dominating codes} (or \emph{FTD-codes} for short), respectively. We address the conditions for the existence of FD- and FTD-codes, bounds for their size and their relation to codes of the other types. We show that the problems of determining an FD- or an FTD-code of minimum cardinality in a graph is NP-hard. We also show that the cardinalities of minimum FD- and FTD-codes differ by at most one, but that it is NP-complete to decide if they are equal for a given graph in general. We find the exact values of minimum cardinalities of the FD- and FTD-codes on some familiar graph classes like paths, cycles, half-graphs and spiders. This helps us compare the two codes with other codes on these graph families thereby exhibiting extremal cases for several lower bounds.
Consider an operator that takes the Fourier transform of a discrete measure supported in $\mathcal{X}\subset[-\frac 12,\frac 12)^d$ and restricts it to a compact $\Omega\subset\mathbb{R}^d$. We provide lower bounds for its smallest singular value when $\Omega$ is either a ball or cube of radius $m$, and under different types of geometric assumptions on $\mathcal{X}$. We first show that if distances between points in $\mathcal{X}$ are lower bounded by a $\delta$ that is allowed to be arbitrarily small, then the smallest singular value is at least $Cm^{d/2} (m\delta)^{\lambda-1}$, where $\lambda$ is the maximum number of elements in $\mathcal{X}$ contained within any ball or cube of an explicitly given radius. This estimate communicates a localization effect of the Fourier transform. While it is sharp, the smallest singular value behaves better than expected for many $\mathcal{X}$, including when we dilate a generic set by parameter $\delta$. We next show that if there is a $\eta$ such that, for each $x\in\mathcal{X}$, the set $\mathcal{X}\setminus\{x\}$ locally consists of at most $r$ hyperplanes whose distances to $x$ are at least $\eta$, then the smallest singular value is at least $C m^{d/2} (m\eta)^r$. For dilations of a generic set by $\delta$, the lower bound becomes $C m^{d/2} (m\delta)^{\lceil (\lambda-1)/d\rceil }$. The appearance of a $1/d$ factor in the exponent indicates that compared to worst case scenarios, the condition number of nonharmonic Fourier transforms is better than expected for typical sets and improve with higher dimensionality.
It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix $M$ whose subdeterminants are all bounded by a constant $\Delta$ in absolute value, can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from $M$, one obtains a submatrix $A$ that is the transpose of a network matrix. Our approach focuses on the case where $A$ arises from $M$ after removing $k$ rows only, where $k$ is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. First, we derive a strong proximity result for the case where $A$ is a general totally unimodular matrix: Given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of $[A\; I]$. Second, for the case where $A$ is transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph $G$. We observe that if $G$ is $2$-connected, then it has no rooted $K_{2,t}$-minor for $t = \Omega(k \Delta)$. We leverage this to obtain a tree-decomposition of $G$ into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming.
\v{C}ech Persistence diagrams (PDs) are topological descriptors routinely used to capture the geometry of complex datasets. They are commonly compared using the Wasserstein distances $OT_{p}$; however, the extent to which PDs are stable with respect to these metrics remains poorly understood. We partially close this gap by focusing on the case where datasets are sampled on an $m$-dimensional submanifold of $\mathbb{R}^{d}$. Under this manifold hypothesis, we show that convergence with respect to the $OT_{p}$ metric happens exactly when $p\gt m$. We also provide improvements upon the bottleneck stability theorem in this case and prove new laws of large numbers for the total $\alpha$-persistence of PDs. Finally, we show how these theoretical findings shed new light on the behavior of the feature maps on the space of PDs that are used in ML-oriented applications of Topological Data Analysis.
A module of a graph G is a set of vertices that have the same set of neighbours outside. Modules of a graphs form a so-called partitive family and thereby can be represented by a unique tree MD(G), called the modular decomposition tree. Motivated by the central role of modules in numerous algorithmic graph theory questions, the problem of efficiently computing MD(G) has been investigated since the early 70's. To date the best algorithms run in linear time but are all rather complicated. By combining previous algorithmic paradigms developed for the problem, we are able to present a simpler linear-time that relies on very simple data-structures, namely slice decomposition and sequences of rooted ordered trees.
The convex dimension of a $k$-uniform hypergraph is the smallest dimension $d$ for which there is an injective mapping of its vertices into $\mathbb{R}^d$ such that the set of $k$-barycenters of all hyperedges is in convex position. We completely determine the convex dimension of complete $k$-uniform hypergraphs, which settles an open question by Halman, Onn and Rothblum, who solved the problem for complete graphs. We also provide lower and upper bounds for the extremal problem of estimating the maximal number of hyperedges of $k$-uniform hypergraphs on $n$ vertices with convex dimension $d$. To prove these results, we restate them in terms of affine projections that preserve the vertices of the hypersimplex. More generally, we provide a full characterization of the projections that preserve its $i$-dimensional skeleton. In particular, we obtain a hypersimplicial generalization of the linear van Kampen-Flores theorem: for each $n$, $k$ and $i$ we determine onto which dimensions can the $(n,k)$-hypersimplex be linearly projected while preserving its $i$-skeleton. Our results have direct interpretations in terms of $k$-sets and $(i,j)$-partitions, and are closely related to the problem of finding large convexly independent subsets in Minkowski sums of $k$ point sets.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191