On bipartite divisor graphs for group conjugacy class sizes

In this paper we study various properties of a bipartite graph related to the sizes of the conjugacy classes of a finite group. It is proved that some invariants of the graph are rather strongly connected to the group structure. In particular we prove that the diameter is at most 6, and classify those groups for which the graphs have diameter 6. Moreover, if the graph is acyclic then the diameter is shown to be at most 5, and groups for which the graph is a path of length 5 are characterised.     

A characterization of the finite simple group L<Subscript>16</Subscript>(2) by its prime graph

In this paper as the main result we prove that the projective special linear group L ₁₆(2) is uniquely determined by its prime graph. In fact we give a positive answer to an open problem arose in Zavarnitsin (Algebra Logic 43(4), 220–231, 2006) and we obtain a first example of a finite group with connected prime graph which is uniquely determined by its prime graph. This research was in part supported by a grant from IPM (No. 86200023).     

Topology of dynamical systems in finite groups and number theory

We study and develop a very new object introduced by V.I. Arnold: a monad is a triple consisting of a finite set, a map from that finite set to itself and the monad graph which is the directed graph whose vertices are the elements of the finite set and whose arrows lead each vertex to its image (by the map). We consider the case in which the finite set entering in the monad definition is a finite group G and the map is the Frobenius map, for some k∈Z. We study the Frobenius dynamical system defined by the iteration of the monad fk, and also study the combinatorics and topology (i.e., the discrete invariants) of the monad graph. Our study provides useful information about several structures on the group associated to the monad graph. So, for example, several properties of the quadratic residues of finite commutative groups can be obtained in terms of the graph of the Frobenius monad .     

Finite-type invariants for graphs and graph reconstructions

Many of the fundamental open problems in graph theory have the following general form: How much information does one need to know about a graph G in order to determine G uniquely. In this article we investigate a new approach to this sort of problem motivated by the notion of a finite-type invariant, recently introduced in the study of knots. We introduce the concepts of vertex-finite-type invariants of graphs, and edge-finite-type invariants of graphs, and show that these sets of functions have surprising algebraic properties. The study of these invariants is intimately related with the classical vertex- and edge-reconstruction conjectures, and we demonstrate that the algebraic properties of the finite-type invariants lead immediately to some of the fundamental results in graph reconstruction theory.     

Upper escape rate of Markov chains on weighted graphs

We obtain an upper escape rate function for a continuous time minimal symmetric Markov chain defined on a locally finite weighted graph. This upper rate function, which has the same form as the manifold setting, is given in terms of the volume growth with respect to an adapted path metric. Our approach also gives a weak form of Folz’s theorem on the conservativeness as a consequence.     

Finite difference approach to trigonometry

Two interrelated, finite difference and graph theoretic, approaches to trigonometry are developed by combining a generalization of the finite difference method first employed by Viète, with solution techniques, based on signal flow graphs, for finite difference equations with variable coefficients, and a scaling approach to trigonometry, based on the polygonometric identities.     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive graphs.     

Analysis of the physical Laplacian and the heat flow on a locally finite graph

We study the physical Laplacian and the corresponding heat flow on an infinite, locally finite graph with possibly unbounded valence.     

On the hamiltonicity of line graphs of locally finite, 6‐edge‐connected graphs

The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6‐edge‐connected graph with a finite number of ends, each of which is thin, is hamiltonian.     

Stochastic control under progressive enlargement of filtrations and applications to multiple defaults risk management

We formulate and investigate a general stochastic control problem under a progressive enlargement of filtration. The global information is enlarged from a reference filtration and the knowledge of multiple random times together with associated marks when they occur. By working under a density hypothesis on the conditional joint distribution of the random times and marks, we prove a decomposition of the original stochastic control problem under the global filtration into classical stochastic control problems under the reference filtration, which is determined in a finite backward induction. Our method revisits and extends in particular stochastic control of diffusion processes with a finite number of jumps. This study is motivated by optimization problems arising in default risk management, and we provide applications of our decomposition result for the indifference pricing of defaultable claims, and the optimal investment under bilateral counterparty risk. The solutions are expressed in terms of BSDEs involving only Brownian filtration, and remarkably without jump terms coming from the default times and marks in the global filtration.     

On the possible values of the entropy of undirected graphs

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contains finitely many possible values of the entropy of an undirected graph. We also determine all the possible values for the entropy of an undirected graph up to the value of four.     

Diffusion processes on graphs: stochastic differential equations,large deviation principle

Ito's rule is established for the diffusion processes on the graphs. We also consider a family of diffusions processes with small noise on a graph. Large deviation principle is proved for these diffusion processes and their local times at the vertices. Received: 12 February 1997 / Revised version: 3 March 1999     

A Characterization of the Interval Function of a (Finite or Infinite) Connected Graph

By the interval function of a finite connected graph we mean the interval function in the sense of H. M. Mulder. This function is very important for studying properties of a finite connected graph which depend on the distance between vertices. The interval function of a finite connected graph was characterized by the present author. The interval function of an infinite connected graph can be defined similarly to that of a finite one. In the present paper we give a characterization of the interval function of each connected graph.     

The mean value property for harmonic functions on graphs and trees

Following the Euclidean example, we introduce the strong and weak mean value property for finite variation measures on graphs. We completely characterize finite variation measures with bounded support on radial trees which have the strong mean value property. We show that for counting measures on bounded subsets of a tree with root o, the strong mean value property is equivalent to the invariance of the subset under the action of the stabilizer of o in the automorphism group. We finally characterize, using the discrete Laplacian, the finite variation measures on a generic graph which have the weak mean value property and we give a non-trivial example. Received: July 21, 2000; in final form: March 13, 2001?Published online: March 19, 2002     

Biased random walks

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, at each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.     

Statistical ranking and combinatorial Hodge theory

We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian, which is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We shall study the graph Helmholtzian using combinatorial Hodge theory, which provides a way to unravel ranking information from edge flows. In particular, we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the l ₂-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained—if this is large, then it indicates that the data does not have a good global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency in the ranking data arises locally or globally. When applied to statistical ranking problems, Hodge decomposition sheds light on whether a given dataset may be globally ranked in a meaningful way or if the data is inherently inconsistent and thus could not have any reasonable global ranking; in the latter case it provides information on the nature of the inconsistencies. An obvious advantage over the NP-hardness of Kemeny optimization is that HodgeRank may be easily computed via a linear least squares regression. We also discuss connections with well-known ordinal ranking techniques such as Kemeny optimization and Borda count from social choice theory.     

Nonexistence of universal graphs without some trees

IfG is a finite tree with a unique vertex of largest, and 4 degree which is adjacent to a leaf then there is no universal countableG-free graph.Research partially supported by the Hungarian Science Research Grant OTKA No. 2117 and by the European Communities (Cooperation in Science and Technology with Central and Eastern European Countries) contract number ERBCIPACT930113.     

Optimal admission control in a queueing system with heterogeneous traffic

We consider optimal admission control of the GI/PH/1-type queueing system. The problem is then reduced to that of determining multi-threshold strategies. Some numerical examples are presented. The results have applications in the optimal input control of information flow in a computer communication network with heterogeneous traffic.     

On the cohomology of flows of stochastic and random differential equations

We consider the flow of a stochastic differential equation on d-dimensional Euclidean space. We show that if the Lie algebra generated by its diffusion vector fields is finite dimensional and solvable, then the flow is conjugate to the flow of a non-autonomous random differential equation, i.e. one can be transformed into the other via a random diffeomorphism of d-dimensional Euclidean space. Viewing a stochastic differential equation in this form which appears closer to the setting of ergodic theory, can be an advantage when dealing with asymptotic properties of the system. To illustrate this, we give sufficient criteria for the existence of global random attractors in terms of the random differential equation, which are applied in the case of the Duffing-van der Pol oscillator with two independent sources of noise. Received: 25 May 1999 / Revised version: 19 October 2000 / Published online: 26 April 2001     

A combined mixed and discontinuous Galerkin method for compressible miscible displacement problem in porous media

In this paper, we present a numerical scheme for solving the coupled system of compressible miscible displacement problem in porous media. The flow equation is solved by the mixed finite element method, and the transport equation is approximated by a discontinuous Galerkin method. The scheme is continuous in time and a priori hp error estimates is presented.