Search results for " 05"
showing 10 items of 51 documents
The smallest singular value of a shifted $d$-regular random square matrix
2017
We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let $$C_1<d< c n/\log ^2 n$$ and let $$\mathcal {M}_{n,d}$$ be the set of all $$n\times n$$ square matrices with 0 / 1 entries, such that each row and each column of every matrix in $$\mathcal {M}_{n,d}$$ has exactly d ones. Let M be a random matrix uniformly distributed on $$\mathcal {M}_{n,d}$$ . Then the smallest singular value $$s_{n} (M)$$ of M is greater than $$n^{-6}$$ with probability at least $$1-C_2\log ^2 d/\sqrt{d}$$ , where c, $$C_1$$ , and $$C_2$$ are absolute positive constants independent of any other parameter…
THE HOMOLOGY OF DIGRAPHS AS A GENERALIZATION OF HOCHSCHILD HOMOLOGY
2010
J. Przytycki has established a connection between the Hochschild homology of an algebra $A$ and the chromatic graph homology of a polygon graph with coefficients in $A$. In general the chromatic graph homology is not defined in the case where the coefficient ring is a non-commutative algebra. In this paper we define a new homology theory for directed graphs which takes coefficients in an arbitrary $A-A$ bimodule, for $A$ possibly non-commutative, which on polygons agrees with Hochschild homology through a range of dimensions.
Quasi-isometrically embedded subgroups of braid and diffeomorphism groups
2005
We show that a large class of right-angled Artin groups (in particular, those with planar complementary defining graph) can be embedded quasi-isometrically in pure braid groups and in the group of area preserving diffeomorphisms of the disk fixing the boundary (with respect to the $L^2$-norm metric); this extends results of Benaim and Gambaudo who gave quasi-isometric embeddings of $F\_n$ and $\Z^n$ for all $n>0$. As a consequence we are also able to embed a variety of Gromov hyperbolic groups quasi-isometrically in pure braid groups and in the diffeomorphism group of the disk. Examples include hyperbolic surface groups, some HNN-extensions of these along cyclic subgroups and the fundame…
A Note on Radio Antipodal Colouring of Paths
2005
International audience; The radio antipodal number of a graph G is the smallest integer c such that there exists an assignment f : V (G) -> {1, 2, . . . , c} satisfying |f(u) − f(v)| >= D − d(u, v) for every two distinct vertices u and v of G, where D is the diameter of G. In this note we determine the exact value of the antipodal number of the path, thus answering the conjecture given in [G. Chartrand, D. Erwin, and P. Zhang. Radio antipodal colorings of graphs, Math. Bohem. 127(1):57-69, 2002]. We also show the connections between this colouring and radio labelings.
Vertex Distinguishing Edge- and Total-Colorings of Cartesian and other Product Graphs
2012
International audience; This paper studies edge- and total-colorings of graphs in which (all or only adjacent) vertices are distinguished by their sets of colors. We provide bounds for the minimum number of colors needed for such colorings for the Cartesian product of graphs along with exact results for generalized hypercubes. We also present general bounds for the direct, strong and lexicographic products.
On List Coloring with Separation of the Complete Graph and Set System Intersections
2022
We consider the following list coloring with separation problem: Given a graph $G$ and integers $a,b$, find the largest integer $c$ such that for any list assignment $L$ of $G$ with $|L(v)|= a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\varphi$ of sets of integers to the vertices of $G$ such that $\varphi(u)\subset L(u)$ and $|\varphi(v)|=b$ for any vertex $u$ and $\varphi(u)\cap \varphi(v)=\emptyset$ for any edge $uv$. Such a value of $c$ is called the separation number of $(G,a,b)$. Using a special partition of a set of lists for which we obtain an improved version of Poincar\'e's crible, we determine the separation number of the c…
Intermittency in the homopolar disk-dynamo
2006
We study a modified Bullard dynamo and show that this system is equivalent to a nonlinear oscillator subject to a multiplicative noise. The stability analysis of this oscillator is performed. Two bifurcations are identified, first towards an \lq\lq intermittent\rq\rq state where the absorbing (non-dynamo) state is no more stable but the most probable value of the amplitude of the oscillator is still zero and secondly towards a \lq\lq turbulent\rq\rq (dynamo) state where it is possible to define unambiguously a (non-zero) most probable value around which the amplitude of the oscillator fluctuates. The bifurcation diagram of this system exhibits three regions which are analytically characteri…
Long Range Bond-Bond Correlations in Dense Polymer Solutions
2004
The scaling of the bond-bond correlation function $C(s)$ along linear polymer chains is investigated with respect to the curvilinear distance, $s$, along the flexible chain and the monomer density, $\rho$, via Monte Carlo and molecular dynamics simulations. % Surprisingly, the correlations in dense three dimensional solutions are found to decay with a power law $C(s) \sim s^{-\omega}$ with $\omega=3/2$ and the exponential behavior commonly assumed is clearly ruled out for long chains. % In semidilute solutions, the density dependent scaling of $C(s) \approx g^{-\omega_0} (s/g)^{-\omega}$ with $\omega_0=2-2\nu=0.824$ ($\nu=0.588$ being Flory's exponent) is set by the number of monomers $g(\r…
Inverse problems and invisibility cloaking for FEM models and resistor networks
2013
In this paper we consider inverse problems for resistor networks and for models obtained via the finite element method (FEM) for the conductivity equation. These correspond to discrete versions of the inverse conductivity problem of Calderón. We characterize FEM models corresponding to a given triangulation of the domain that are equivalent to certain resistor networks, and apply the results to study nonuniqueness of the discrete inverse problem. It turns out that the degree of nonuniqueness for the discrete problem is larger than the one for the partial differential equation. We also study invisibility cloaking for FEM models, and show how an arbitrary body can be surrounded with a layer …
Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups
2003
We prove by explicit construction that graph braid groups and most surface groups can be embedded in a natural way in right-angled Artin groups, and we point out some consequences of these embedding results. We also show that every right-angled Artin group can be embedded in a pure surface braid group. On the other hand, by generalising to right-angled Artin groups a result of Lyndon for free groups, we show that the Euler characteristic -1 surface group (given by the relation x^2y^2=z^2) never embeds in a right-angled Artin group.