203 results
Search Results
2. Some Remarks on a Paper of A. F. Beardon and P. L. Waterman about Strongly Discrete Subgroups of SL(2, C)
- Author
-
Gerhard Rosenberger
- Subjects
Discrete mathematics ,Combinatorics ,General Mathematics ,Mathematics - Published
- 1983
3. A Note on Tutte's Paper 'The Factorization of Linear Graphs'*
- Author
-
F. G. Maunsell
- Subjects
Combinatorics ,Discrete mathematics ,Factorization ,General Mathematics ,Tutte 12-cage ,Nowhere-zero flow ,Tutte matrix ,Chromatic polynomial ,Tutte theorem ,Mathematics - Published
- 1952
4. Bounds for Shannon and Zipf-Mandelbrot entropies
- Author
-
Muhammad Adil Khan, Đilda Pečarić, and Josip Pečarić
- Subjects
convex function ,Jensen inequality ,Shannon entropy ,Zipf-Mandelbrot entropy ,Discrete mathematics ,Mathematics::Dynamical Systems ,Shannon's source coding theorem ,General Mathematics ,010102 general mathematics ,General Engineering ,Maximum entropy thermodynamics ,Min entropy ,Entropy in thermodynamics and information theory ,01 natural sciences ,010101 applied mathematics ,Rényi entropy ,Entropy power inequality ,Combinatorics ,0101 mathematics ,Entropic uncertainty ,Limiting density of discrete points ,Mathematics - Abstract
Shannon and Zipf-Mandelbrot entropies have many applications in many applied sciences, for example, in information theory, biology and economics, etc. In this paper, we consider two refinements of the well-know Jensen inequality and obtain different bounds for Shannon and Zipf-Mandelbrot entropies. First of all, we use some convex functions and manipulate the weights and domain of the functions and deduce results for Shannon entropy. We also discuss their particular cases. By using Zipf-Mandelbrot laws for different parameters in Shannon entropies results, we obtain bounds for Zipf-Mandelbrot entropy. The idea used in this paper for obtaining the results may stimulate further research in this area, particularly for Zipf-Mandelbrot entropy.
- Published
- 2017
5. How does the core sit inside the mantle?
- Author
-
Kathrin Skubch, Mihyun Kang, Oliver Cooley, and Amin Coja-Oghlan
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,General Mathematics ,05C80 ,Structure (category theory) ,0102 computer and information sciences ,Characterization (mathematics) ,01 natural sciences ,Mantle (geology) ,Combinatorics ,010104 statistics & probability ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,0101 mathematics ,Mathematics ,Branching process ,Discrete mathematics ,Random graph ,Series (mathematics) ,Degree (graph theory) ,Applied Mathematics ,Probability (math.PR) ,Computer Graphics and Computer-Aided Design ,Tree (graph theory) ,Vertex (geometry) ,010201 computation theory & mathematics ,Bounded function ,Core (graph theory) ,Combinatorics (math.CO) ,Combinatorial theory ,Mathematics - Probability ,Software ,Computer Science - Discrete Mathematics - Abstract
The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017
- Published
- 2017
6. Meyniel's conjecture holds for random graphs
- Author
-
Nicholas C. Wormald and Paweł Prałat
- Subjects
Random graph ,Discrete mathematics ,Conjecture ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,16. Peace & justice ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Random regular graph ,Almost surely ,0101 mathematics ,Absolute constant ,Software ,Connectivity ,Mathematics - Abstract
In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016
- Published
- 2015
7. Degenerate random environments
- Author
-
Thomas S. Salisbury and Mark Holmes
- Subjects
Random graph ,Discrete mathematics ,Percolation critical exponents ,Random field ,Applied Mathematics ,General Mathematics ,Probability (math.PR) ,010102 general mathematics ,Random function ,Random element ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Directed percolation ,Combinatorics ,010104 statistics & probability ,FOS: Mathematics ,Random compact set ,Continuum percolation theory ,0101 mathematics ,Mathematics - Probability ,Software ,Mathematics - Abstract
We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014
- Published
- 2012
8. Random graphs containing few disjoint excluded minors
- Author
-
Colin McDiarmid and Valentas Kurauskas
- Subjects
Discrete mathematics ,Clique-sum ,Applied Mathematics ,General Mathematics ,Robertson–Seymour theorem ,Computer Graphics and Computer-Aided Design ,1-planar graph ,Planar graph ,Combinatorics ,symbols.namesake ,Pathwidth ,Graph power ,symbols ,Cograph ,Software ,Forbidden graph characterization ,Mathematics - Abstract
The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n] = {1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.
- Published
- 2012
9. The diameter of a random subgraph of the hypercube
- Author
-
Tomáš Kulich
- Subjects
Random graph ,Discrete mathematics ,Applied Mathematics ,General Mathematics ,Dimension (graph theory) ,Sampling (statistics) ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Combinatorics ,Random regular graph ,Almost surely ,struct ,Hypercube ,Software ,Mathematics - Abstract
In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + mp ≤ D(Gn) ≤ n + mp + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and mp depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(Gn) = n + mp (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.
- Published
- 2012
10. Counting strongly-connected, moderately sparse directed graphs
- Author
-
Boris Pittel
- Subjects
Discrete mathematics ,Strongly connected component ,Degree (graph theory) ,Applied Mathematics ,General Mathematics ,Directed graph ,Term (logic) ,Computer Graphics and Computer-Aided Design ,Combinatorics ,Modular decomposition ,Indifference graph ,Chordal graph ,Asymptotic formula ,Software ,Mathematics - Abstract
A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m - n ≫ n2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters m and n among all such digraphs with positive in/out-degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013
- Published
- 2012
11. Hamiltonian cycles in the generating graphs of finite groups
- Author
-
Attila Maróti, Gábor P. Nagy, Thomas Breuer, Robert M. Guralnick, and Andrea Lucchini
- Subjects
Normal subgroup ,Discrete mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Hamiltonian path ,Graph ,Vertex (geometry) ,Combinatorics ,symbols.namesake ,Subgroup ,010201 computation theory & mathematics ,Solvable group ,Simple group ,finite simple groups ,symbols ,generating graphs of finite groups ,0101 mathematics ,Mathematics - Abstract
For a flnite group G let i(G) denote the graph deflned on the non- identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. In this paper it is shown that the graph i(G) contains a Hamiltonian cycle for many flnite groups G. In the literature many deep results about flnite simple groups G can equivalently be stated as theorems about i(G). Three examples are given. Guralnick and Shalev (10) showed that for su-ciently large G the graph i(G) has diameter at most 2. Guralnick and Kantor (9) showed that there is no isolated vertex in i(G). Finally, Breuer, Guralnick, Kantor (4) showed that the diameter of i(G) is at most 2 for all G. In this paper those flnite groups G are considered for which i(G) contains a Hamiltonian cycle. The following proposition reduces the investigations to those non-solvable groups G for which G=N is cyclic for any non-trivial normal subgroup N of G. Proposition 1.1. Let G be a flnite solvable group that has at least 4 elements. Then the graph i(G) contains a Hamiltonian cycle if and only if G=N is cyclic for all non-trivial normal subgroups N of G. The three main results of this paper are Theorems 1.2, 1.3, and 1.4.
- Published
- 2010
12. Variant sandwich pairs
- Author
-
Martin Schechter
- Subjects
Discrete mathematics ,Combinatorics ,Set (abstract data type) ,Sequence ,Partial differential equation ,Development (topology) ,General Mathematics ,Bounded function ,Mathematics - Abstract
Since the development of the calculus of variations there has been interest in finding critical points of functionals. This was intensified by the fact that for many equations arising in practice, the solutions are critical points. In searching for such points, there is a distinct advantage if the functional G is semibounded. In this case one can find a Palais-Smale (PS) sequence G (uk) c, G ′(uk) 0 or even a Cerami sequence G (uk) c, (1 + ‖uk ‖)G ′(uk) 0. These sequences produce critical points if they have convergent subsequences. However, there is no clear method of finding critical points of functionals which are not semibounded. Linking subsets do provide such a method. They can produce a PS sequence provided they separate the functional. In previous papers we have shown that there are pairs of subsets that can produce Cerami-like sequences even though they do not separate the functional. We call such sets sandwich pairs. All that is required is that the functional be bounded from above on one ofthe sets and bounded from below on the other, with no relationship needed between the bounds. This provides a distinct advantage in applications. The present paper discusses the situation in which one cannot find linking subsets which separate the functional or sandwich pairs for which the functional is bounded below on one set and bounded above on the other. We develop a method which can deal with such situations. We apply the method to problems in partial differential equations (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
- Published
- 2010
13. CRESTED PRODUCTS OF ASSOCIATION SCHEMES
- Author
-
R. A. Bailey and Peter J. Cameron
- Subjects
Discrete mathematics ,Combinatorics ,Normal subgroup ,Association scheme ,Wreath product ,General Mathematics ,Equivalence relation ,Distributive lattice ,Permutation group ,Direct product ,Mathematics ,Cyclic permutation - Abstract
The paper defines a new type of product of association schemes (and of the related objects, permutation groups and orthogonal block structures), which generalizes the direct and wreath products (which are referred to as 'crossing' and 'nesting' in the statistical literature). Given two association schemes for , each having an inherent partition (that is, a partition whose equivalence relation is a union of adjacency relations in the association scheme), a product of the two schemes is defined, which reduces to the direct product if or , and to the wreath product if and , where and are the relation of equality and the universal relation on . The character table of the crested product is calculated, and it is shown that, if the two schemes and have formal duals, then so does their crested product (and a simple description of this dual is given). An analogous definition for permutation groups with intransitive normal subgroups is created, and it is shown that the constructions for association schemes and permutation groups are related in a natural way. The definition can be generalized to association schemes with families of inherent partitions, or permutation groups with families of intransitive normal subgroups. This time the correspondence is not so straightforward, and it works as expected only if the inherent partitions (or orbit partitions) form a distributive lattice. The paper concludes with some open problems.
- Published
- 2005
14. A solution of the isomorphism problem for circulant graphs
- Author
-
Mikhail Muzychuk
- Subjects
Discrete mathematics ,General Mathematics ,Subgraph isomorphism problem ,Combinatorics ,Indifference graph ,Circulant graph ,Chordal graph ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Induced subgraph isomorphism problem ,Isomorphism ,Graph isomorphism ,Circulant matrix ,Physics::Atmospheric and Oceanic Physics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
The isomorphism problem for circulant graphs (Cayley graphs over the cyclic group) which has been open since 1967 is completely solved in this paper. The main result of the paper gives an efficient isomorphism criterion for circulant graphs of arbitrary order. This result also solves an isomorphism problem for colored circulant graphs and some classes of cyclic codes.
- Published
- 2004
15. On rank invariance of moment matrices of nonnegative Hermitian-valued Borel measures on the unit circle
- Author
-
Bernd Kirstein, Andreas Lasarow, and Bernd Fritzsche
- Subjects
Combinatorics ,Discrete mathematics ,Matrix (mathematics) ,Sequence ,Unit circle ,Rank (linear algebra) ,Borel hierarchy ,General Mathematics ,Borel measure ,Hermitian matrix ,Orthogonal basis ,Mathematics - Abstract
This paper provides first tools for generalizing the theory of orthogonal rational functions on the unit circle created by Bultheel, Gonzalez-Vera, Hendriksen and Njastad to the matrix case. A crucial part in this generalization is the definition of the spaces of matrix-valued rational functions for which an orthogonal basis is to be constructed. An important feature of the matrix case is that these spaces will be considered simultaneously as left and right modules over the algebra ℂq×q. In this modules we will define simultaneously left and right matrix-valued inner products with the aid of a nonnegative Hermitian-valued q × q Borel measure on the unit circle. Given a sequence (αj)j∈ℕ of complex numbers located in ℂ\ (especially in “good position” with respect to the unit circle) we will introduce a concept of rank for nonnegative Hermitian-valued q × q Borel measures on the unit circle which is based on the Gramian matrix of particular rational matrix-valued functions with prescribed pole structure. A main result of this paper is that this concept of rank is universal. More precisely, it turns out that the rank of a matrix measure does not depend on the given sequence (αj)j∈ℕ. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
- Published
- 2004
16. Regularity properties for triple systems
- Author
-
Vojtech Rödl and Brendan Nagle
- Subjects
Discrete mathematics ,Combinatorics ,Applied Mathematics ,General Mathematics ,Graph theory ,Computer Graphics and Computer-Aided Design ,Software ,Graph ,Mathematics ,Extremal graph theory - Abstract
Szemeredi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory [J. Komlos and M. Simonovits, Szemeredi's Regularity Lemma and its applications in graph theory, Combinatorics 2 (1996), 295-352]. Many of its applications are based on the following technical fact: If G is a k-partite graph with V(G) = ∪ki=1 Vi, |Vi| = n for all i ∈ [k], and all pairs {Vi, Vj}, 1 ≤ i < j ≤ k, are e-regular of density d, then G contains d??nk(1 + f(e)) cliques K(2)k, where f(e) → 0 as e → 0. The aim of this paper is to establish the analogous statement for 3-uniform hypergraphs. Our result, to which we refer as The Counting Lemma, together with Theorem 3.5 of P. Frankl and V. Rodl [Extremal problems on set systems, Random Structures Algorithms 20(2) (2002), 131-164), a Regularity Lemma for Hypergraphs, can be applied in various situations as Szemeredi's Regularity Lemma is for graphs. Some of these applications are discussed in previous papers, as well as in upcoming papers, of the authors and others.
- Published
- 2003
17. On characterizing hypergraph regularity
- Author
-
Penny Haxell, V. Rödl, Yulia Dementieva, and Brendan Nagle
- Subjects
Discrete mathematics ,Hypergraph ,Lemma (mathematics) ,Mathematics::Combinatorics ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Graph theory ,Szemerédi regularity lemma ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Extremal graph theory ,Combinatorics ,010201 computation theory & mathematics ,Bipartite graph ,Verifiable secret sharing ,0101 mathematics ,Software ,Mathematics - Abstract
Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].
- Published
- 2002
18. Hamilton cycles containing randomly selected edges in random regular graphs
- Author
-
Nicholas C. Wormald and Robert W. Robinson
- Subjects
Discrete mathematics ,Distribution (number theory) ,Applied Mathematics ,General Mathematics ,Contiguity ,Computer Graphics and Computer-Aided Design ,Hamiltonian path ,Combinatorics ,symbols.namesake ,Random regular graph ,symbols ,Cubic graph ,Probability distribution ,Almost surely ,Hamiltonian (quantum mechanics) ,Software ,Mathematics - Abstract
In previous papers the authors showed that almost all d-regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001
- Published
- 2001
19. Set Theory is Interpretable in the Automorphism Group of an Infinitely Generated Free Group
- Author
-
Vladimir Tolstykh
- Subjects
p-group ,Combinatorics ,Discrete mathematics ,Endomorphism ,Inner automorphism ,Symmetric group ,General Mathematics ,Quaternion group ,Outer automorphism group ,Alternating group ,Automorphism ,Mathematics - Abstract
In [6] S. Shelah showed that in the endomorphism semi-group of an infinitely generated algebra which is free in a variety one can interpret some set theory. It follows from his results that, for an algebra Fℵ which is free of infinite rank ℵ in a variety of algebras in a language L, if ℵ > |L|, then the first-order theory of the endomorphism semi-group of Fℵ, Th(End(Fℵ)), syntactically interprets Th(ℵ,L2), the second-order theory of the cardinal ℵ. This means that for any second-order sentence χ of empty language there exists χ*, a first-order sentence of semi-group language, such that for any infinite cardinal ℵ > |L|,formula hereIn his paper Shelah notes that it is natural to study a similar problem for automorphism groups instead of endomorphism semi-groups; a priori the expressive power of the first-order logic for automorphism groups is less than the one for endomorphism semi-groups. For instance, according to Shelah's results on permutation groups [4, 5], one cannot interpret set theory by means of first-order logic in the permutation group of an infinite set, the automorphism group of an algebra in empty language. On the other hand, one can do this in the endomorphism semi-group of such an algebra.In [7, 8] the author found a solution for the case of the variety of vector spaces over a fixed field. If V is a vector space of an infinite dimension ℵ over a division ring D, then the theory Th(ℵ, L2) is interpretable in the first-order theory of GL(V), the automorphism group of V. When a field D is countable and definable up to isomorphism by a second-order sentence, then the theories Th(GL(V)) and Th(ℵ, L2) are mutually syntactically interpretable. In the general case, the formulation is a bit more complicated.The main result of this paper states that a similar result holds for the variety of all groups.
- Published
- 2000
20. Convex Bodies, Graphs and Partial Orders
- Author
-
Graham R. Brightwel and Béla Bollobás
- Subjects
Combinatorics ,Convex analysis ,Discrete mathematics ,General Mathematics ,Content (measure theory) ,Convex polytope ,Convex set ,Convex body ,Convex combination ,QA Mathematics ,Support function ,Subderivative ,Mathematics - Abstract
A {\em convex corner} is a compact convex down-set of full dimension in . Convex corners arise in graph theory, for instance as stable set polytopes of graphs. They are also natural objects of study in geometry, as they correspond to 1-unconditional norms in an obvious way. In this paper, we study a parameter of convex corners, which we call the {\em content}, that is related to the volume. This parameter has appeared implicitly before: both in geometry, chiefly in a paper of Meyer ({\em Israel J.\ Math.} 55 (1986) 317--327) effectively using content to give a proof of Saint-Raymond's Inequality on the volume product of a convex corner, and in combinatorics, especially in a paper of Sidorenko ({\em Order} 8 (1991) 331--340) relating content to the number of linear extensions of a partial order. One of our main aims is to expose connections between work in these two areas. We prove many new results, giving in particular various generalizations of Saint-Raymond's Inequality. Content also behaves well under the operation of {\em pointwise product} of two convex corners; our results enable us to give counter-examples to two conjectures of Bollob\'as and Leader ({\em Oper.\ Theory Adv.\ Appl.} 77 (1995) 13--24) on pointwise products. 1991 Mathematics Subject Classification: 52C07, 51M25, 52B11, 05C60, 06A07.
- Published
- 2000
21. Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- Author
-
Artur Czumaj and Christian Schiedeler
- Subjects
Discrete mathematics ,Polynomial ,Class (set theory) ,Mathematics::Combinatorics ,Applied Mathematics ,General Mathematics ,Sieve (category theory) ,Mathematical proof ,Computer Graphics and Computer-Aided Design ,Randomized algorithm ,Combinatorics ,Time complexity ,Lovász local lemma ,Software ,Algorithmic Lovász local lemma ,Mathematics - Abstract
The Lovasz local lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz local lemma does not supply a polynomial-time algorithm for finding these structures. Beck was the first who gave a method of converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. He applied his technique to the symmetric form of the Lovasz local lemma and, in particular, to the problem of 2-coloring uniform hypergraphs. In this paper we investigate the general form of the Lovasz local lemma. Our main result is a randomized algorithm for 2-coloring nonuniform hypergraphs that runs in expected linear time. Even for uniform hypergraphs no algorithm with such a runtime bound was previously known, and no polynomial-time algorithm was known at all for the class of nonuniform hypergraphs we will consider in this paper. Our algorithm and its analysis provide a novel approach to the general Lovasz local lemma that may be of independent interest. We also show how to extend our result to the c-coloring problem. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 213–237, 2000
- Published
- 2000
22. Approximating the unsatisfiability threshold of random formulas
- Author
-
Yannis C. Stamatiou, Danny Krizanc, Lefteris M. Kirousis, and Evangelos Kranakis
- Subjects
Discrete mathematics ,Sequence ,True quantified Boolean formula ,Applied Mathematics ,General Mathematics ,Zero (complex analysis) ,Expected value ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Satisfiability ,Combinatorics ,Random variable ,Software ,Mathematics ,Real number - Abstract
Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by Kamath et al. to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253
- Published
- 1998
23. Maximal full subspaces in random projective spaces-thresholds and Poisson approximation
- Author
-
Wojciech Kordecki
- Subjects
Random graph ,Discrete mathematics ,Generalization ,Applied Mathematics ,General Mathematics ,Poisson distribution ,Mathematical proof ,Computer Graphics and Computer-Aided Design ,Linear subspace ,Matroid ,Combinatorics ,symbols.namesake ,symbols ,Rank (graph theory) ,Projective test ,Software ,Mathematics - Abstract
Let Gn, p denote a random graph on n vertices. It is an interesting problem when small cliques arise and what distributions of the number of small cliques may occur. Matroids are natural generalization of graphs; therefore, we can try to investigate maximal flats of a small rank in random matroids. The most studied and most interesting seem to be “random projective geometries” introduced by Kelly and Oxley. Many of the theorems in our paper are based on the results published in a long paper of Barbour, Janson, Karoski, and Ruciski. However, proofs for projective geometries generally are more complicated. © 1995 Wiley Periodicals, Inc.
- Published
- 1995
24. Connectivity of Knight's Graphs
- Author
-
F. Rhodes and Stephen E. Wilson
- Subjects
Combinatorics ,Connected component ,Discrete mathematics ,Graph center ,Transitive relation ,Planar ,General Mathematics ,Independent set ,Path graph ,Special case ,Vertex (geometry) ,Mathematics - Abstract
This paper is concerned with connectivity of graphs associated with generalized knight's moves. The minimal connected generalized knight's graphs are shown to be planar or toroidal, which was unexpected in view of the complex nature of the graph generated by knight's moves on a chess-board. Each move of a knight in chess takes the knight two steps parallel to one side of the board and one step parallel to the other side. Using moves of this kind a knight can move between any two positions on a standard 8 by 8 chess-board. Indeed it can move between any two positions on a 3 by 4 board, but not on any smaller board. A metrical geometry on the digital plane determined by standard knight's moves has been studied recently [1,6], and further metrics associated with generalized knight's moves have been noted [2]. The first step is to determine which knight's moves are transitive on an unbounded board. It is then natural to try to determine for each of these the smallest board on which it is transitive. It is convenient to express the problem in terms of knight's graphs in which the vertices are points in the plane with integer coefficients and the edges correspond to the knight's moves. An edge in the graph of a {p, ^}-knight joins two vertices where the difference between one of their coordinates is p and the difference between the other is q. Transitivity of a knight's moves on a board corresponds to connectivity of a knight's graph. The problem on the unrestricted set of vertices is easily solved. It is shown in §2 that the {p, ^}-knight's graph on Z 2 is connected if and only if p and q are mutually prime and their sum is odd. This is a special case of more general results on knight's graphs on Z" which have been studied by G. A. Jones [3]. The problem on restricted sets of vertices is more difficult. In this paper it is shown that if the {p, q)-knight's graph is connected on Z 2 and p
- Published
- 1993
25. Szemerédi's partition and quasirandomness
- Author
-
Miklós Simonovits and Vera T. Sós
- Subjects
Discrete mathematics ,Pseudorandom number generator ,Random graph ,Hypergraph ,Applied Mathematics ,General Mathematics ,Computer Graphics and Computer-Aided Design ,Combinatorics ,Probability space ,Probability theory ,If and only if ,Random regular graph ,Partition (number theory) ,Software ,Mathematics - Abstract
In this paper we shall investigate the connection between the SzemerCdi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (G,) is quasirandom if and only if in the SzemerCdi partitions of G, almost all densities are $ + o(1). Many attempts have been made to clarify when an individual event could be called random and in what sense. Both the fundamental problems of probability theory and some practical application need this clarification very much. For example, in applications of the Monte-Carlo method one needs to know if the random number generator used yields a sequence which can be regarded “pseudorandom” or not. The literature on this question is extremely extensive. Thomason [6-81 and Chung, Graham, and Wilson [2,3], and also Frankl, Rodl, and Wilson [4] started a new line of investigation, where (instead of regarding numerical sequences) they gave some characterizations of “randomlike” graph sequences, matrix sequences, and hypergraph sequences. The aim of this paper is to contribute to this question in case of graphs, continuing the above line of investigation. Let %(n, p) denote the probability space of labelled graphs on n vertices, where the edges are chosen independently and at random, with probability p. We shall say that “a random graph sequence (G,) has property P”
- Published
- 1991
26. A new combinatorial representation of the additive coalescent
- Author
-
Jean-François Marckert, Minmin Wang, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Pierre et Marie Curie - Paris 6 (UPMC), Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires] (CONICET), ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), Marckert, Jean-François, and Appel à projets générique - GRaphes et Arbres ALéatoires - - GRAAL2014 - ANR-14-CE25-0014 - Appel à projets générique - VALID
- Subjects
[MATH.MATH-PR] Mathematics [math]/Probability [math.PR] ,parking ,General Mathematics ,68R05 Key Words: additive coalescent ,Markov process ,0102 computer and information sciences ,01 natural sciences ,increasing trees ,Coalescent theory ,Combinatorics ,symbols.namesake ,60J25 ,60F05 ,Representation (mathematics) ,ComputingMilieux_MISCELLANEOUS ,construction Mathematics Subject Classification (2000) 60C05 ,Mathematics ,Block (data storage) ,Discrete mathematics ,Applied Mathematics ,Probabilistic logic ,Cayley trees ,Computer Graphics and Computer-Aided Design ,Tree (graph theory) ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,random walks on trees ,60K35 ,010201 computation theory & mathematics ,symbols ,Node (circuits) ,Variety (universal algebra) ,Software - Abstract
The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing & Louchard as the block sizes in a parking scheme. In the coalescent forest representation, some edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by adding edges between the roots. This construction induces the same process at the level of cluster sizes, but allows one to make numerous connections with some combinatorial and probabilistic models that were not known to be connected with additive coalescent. The variety of the combinatorial objects involved here – size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees – justifies our interests in this Acknowledgement : The research has been supported by ANR-14-CE25-0014 (ANR GRAAL).
- Published
- 2018
27. The random connection model: Connectivity, edge lengths, and degree distributions
- Author
-
Srikanth K. Iyer
- Subjects
Random graph ,Discrete mathematics ,Unit sphere ,Applied Mathematics ,General Mathematics ,Degree distribution ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Vertex (geometry) ,Combinatorics ,010104 statistics & probability ,Connection model ,0103 physical sciences ,Poisson point process ,0101 mathematics ,010306 general physics ,Random geometric graph ,Software ,Mathematics - Abstract
Consider the random graph G(Pn,r) whose vertex set Pn is a Poisson point process of intensity n on (-12,12]d,d2. Any two vertices Xi,XjPn are connected by an edge with probability g(d(Xi,Xj)r), independently of all other edges, and independent of the other points of Pn. d is the toroidal metric, r > 0 and g:0,)0,1] is non-increasing and =dg(|x|)dx ) does not have any isolated nodes satisfies lim?nnMndlog?n=1. Let =inf?{x > 0:xg(x)> 1}, and be the volume of the unit ball in d. Then for all >, G(Pn,(log?nn)1d) is connected with probability approaching one as n. The bound can be seen to be tight for the usual random geometric graph obtained by setting g=10,1]. We also prove some useful results on the asymptotic behavior of the length of the edges and the degree distribution in the connectivity regime. The results in this paper work for connection functions g that are not necessarily compactly supported but satisfy g(r)=o(r-c).
- Published
- 2017
28. Coloring graphs of various maximum degree from random lists
- Author
-
Carl Johan Casselgren
- Subjects
FOS: Computer and information sciences ,Discrete mathematics ,Discrete Mathematics (cs.DM) ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Vertex (geometry) ,Combinatorics ,010201 computation theory & mathematics ,coloring from random lists ,list coloring ,random list ,FOS: Mathematics ,Mathematics - Combinatorics ,Sannolikhetsteori och statistik ,Combinatorics (math.CO) ,0101 mathematics ,Probability Theory and Statistics ,Software ,Computer Science - Discrete Mathematics ,Mathematics ,List coloring - Abstract
Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $\Delta=\Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $\sigma$, in terms of $n$, $k$ and $\Delta$, which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $\sigma(n) = \omega(n^{1/k^2} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ and $\Delta= \Omega(n^{1/2})$, then the same conclusion holds provided that $\sigma=\omega(\Delta)$. We also give related results for other bounds on $\Delta$, when $k$ is constant or a strictly increasing function of $n$.
- Published
- 2017
29. On spaces Cb(X) weakly K-analytic
- Author
-
Manuel López-Pellicer, Juan Carlos Ferrando, and Jerzy Ka̧kol
- Subjects
Pointwise convergence ,Discrete mathematics ,General Mathematics ,010102 general mathematics ,Banach space ,01 natural sciences ,Pseudocompact space ,010101 applied mathematics ,Combinatorics ,Isolated point ,Compact space ,Bounded function ,Regular space ,0101 mathematics ,Subspace topology ,Mathematics - Abstract
A subset Y of the dual closed unit ball BE* of a Banach space E is called a Rainwater set for E if every bounded sequence of E that converges pointwise on Y converges weakly in E. In this paper, topological properties of Rainwater sets for the Banach space Cb(X) of the real-valued continuous and bounded functions defined on a completely regular space X equipped with the supremum-norm are studied. This applies to characterize the weak K-analyticity of Cb(X) in terms of certain Rainwater sets for Cb(X). Particularly, we show that Cb(X) is weakly K-analytic if and only if there exists a Rainwater set Y for Cb(X) such that Cb(X),σY is both K-analytic and angelic, where σY denotes the topology on Cb(X) of the pointwise convergence on Y. For the case when X is compact, one gets classic Talagrand's theorem. As an application we show that if X is a compact space and Y is a Gδ-dense subspace, then X is Talagrand compact, i.e., Cp(X) is K-analytic, if and only if the space (C(X),σY) is K-analytic.
- Published
- 2017
30. Q-integral unicyclic, bicyclic and tricyclic graphs
- Author
-
Caixia Song, Qiongxiang Huang, Xueyi Huang, and Jing Zhang
- Subjects
Discrete mathematics ,Algebraic connectivity ,Bicyclic molecule ,General Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,010103 numerical & computational mathematics ,02 engineering and technology ,Mathematics::Spectral Theory ,Signless laplacian ,01 natural sciences ,Graph ,Combinatorics ,0101 mathematics ,Laplacian matrix ,Eigenvalues and eigenvectors ,Mathematics - Abstract
A graph is called Q-integral if its signless Laplacian spectrum consists of integers. In this paper, we characterize a class of k-cyclic graphs whose second smallest signless Laplacian eigenvalue is less than one. Using this result we determine all the Q-integral unicyclic, bicyclic and tricyclic graphs.
- Published
- 2017
31. Triangle factors of graphs without large independent sets and of weighted graphs
- Author
-
Maryam Sharifzadeh, Theodore Molla, and József Balogh
- Subjects
Vertex (graph theory) ,Discrete mathematics ,Conjecture ,Sublinear function ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Combinatorics ,Quadratic equation ,Probabilistic method ,Factorization ,010201 computation theory & mathematics ,0101 mathematics ,Software ,Independence number ,Mathematics - Abstract
The classical Corr adi-Hajnal theorem claims that every n-vertex graph G with (G) 2n=3 contains a triangle factor, when 3jn. In this paper we asymptotically determine the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with (G) = o(n) and (G) (1=2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratic many edges, and (G) (1=2 +o(1))n, then G has a Kr-factor for n suciently large. We also propose many related open problems whose solutions could show a relationship with RamseyTur an theory. Additionally, we also consider a fractional variant of the Corr adi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t2 (0; 1) and w : E(Kn)! [0; 1]. We call a triangle in Kn heavy if the sum of the weights on its edges is more than 3t. We prove that if 3jn and w is such that for every vertex v the sum of w(e)
- Published
- 2016
32. The probability of connectivity in a hyperbolic model of complex networks
- Author
-
Bode, Michel, Fountoulakis, Nikolaos, Müller, Tobias, Sub Mathematical Modeling, Mathematical Modeling, Sub Mathematical Modeling, and Mathematical Modeling
- Subjects
Discrete mathematics ,Mathematics(all) ,Uniform distribution (continuous) ,Degree (graph theory) ,Applied Mathematics ,General Mathematics ,Hyperbolic geometry ,Zero (complex analysis) ,complex networks ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,random geometric graphs ,Combinatorics ,010104 statistics & probability ,Bounded function ,0103 physical sciences ,Exponent ,Graph (abstract data type) ,0101 mathematics ,010306 general physics ,Constant (mathematics) ,Software ,Mathematics - Abstract
We consider a model for complex networks that was introduced by Krioukov et al. (Phys Rev E 82 (2010) 036106). In this model, N points are chosen randomly inside a disk on the hyperbolic plane according to a distorted version of the uniform distribution and any two of them are joined by an edge if they are within a certain hyperbolic distance. This model exhibits a power-law degree sequence, small distances and high clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power-law and ν controls the average degree. In this paper we focus on the probability that the graph is connected. We show the following results. For α > 1/2 and ν arbitrary, the graph is disconnected with high probability. For α < 1/2 and ν arbitrary, the graph is connected with high probability. When α = 1/2 and ν is fixed then the probability of being connected tends to a constant f(ν) that depends only on ν, in a continuous manner. Curiously, f(ν) = 1 for ν ≥ Π while it is strictly increasing, and in particular bounded away from zero and one, for 0 < ν < Π. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 65–94, 2016.
- Published
- 2016
33. Existence of solutions to a non-variational singular elliptic system with unbounded weights
- Author
-
Francescantonio Oliva, Marta Strani, and L. M. De Cave
- Subjects
Discrete mathematics ,General Mathematics ,Operator (physics) ,010102 general mathematics ,Open set ,Fixed-point theorem ,Lebesgue integration ,01 natural sciences ,Omega ,010101 applied mathematics ,Combinatorics ,symbols.namesake ,Bounded function ,symbols ,0101 mathematics ,Element (category theory) ,Mathematics - Abstract
In this paper we prove an existence result for the following singular elliptic system {z > 0 in Omega, z is an element of W-0(iota,p)(Omega) : -Delta(p)z = a(x)z(q-iota)u(theta) , u > 0 in Omega, u is an element of W-0(iota,p)(Omega) : -Delta(p)u = b(x)z(q)u(theta-iota) , where Omega is a bounded open set in R-N (N >= 2), -Delta(p) is the p-laplacian operator, a(x) and b(x) are suitable Lebesgue functions and q > 0, 0 1 are positive parameters satisfying suitable assumptions. (C) 2016 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
- Published
- 2016
34. Bounds for pairs in judicious partitioning of graphs
- Author
-
Genghua Fan and Jianfeng Hou
- Subjects
Discrete mathematics ,Conjecture ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Chernoff bound ,struct ,0101 mathematics ,Software ,Mathematics - Abstract
In 2002, Bollobas and Scott posed the following problem: for an integer k≥2 and a graph G of m edges, what is the smallest f(k, m) such that V(G) can be partitioned into V 1,…,Vk in which e(Vi∪Vj)≤f(k,m) for all 1≤i≠j≤k, where e(Vi∪Vj) denotes the number of edges with both ends in Vi∪Vj? In this paper, we solve this problem asymptotically by showing that f(k,m)≤m/(k−1)+o(m). We also show that V(G) can be partitioned into V1,…,Vk such that e(Vi∪Vj)≤4m/k2+4Δ/k+o(m) for 1≤i≠j≤k, where Δ denotes the maximum degree of G. This confirms a conjecture of Bollobas and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017
- Published
- 2016
35. A combinatorial characterization of smooth LTCs and applications
- Author
-
Michael Viderman and Eli Ben-Sasson
- Subjects
Discrete mathematics ,0209 industrial biotechnology ,Hadamard code ,Applied Mathematics ,General Mathematics ,Reed–Muller code ,0102 computer and information sciences ,02 engineering and technology ,Locally decodable code ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Combinatorics ,020901 industrial engineering & automation ,010201 computation theory & mathematics ,Code (cryptography) ,Error detection and correction ,Tanner graph ,Software ,Word (computer architecture) ,Testability ,Mathematics - Abstract
The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet, we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs and whether asymptotically good linear LTCs with constant query complexity exist. In this paper, we provide a combinatorial characterization of smooth locally testable codes, which are locally testable codes whose associated tester queries every bit of the tested word with equal probability. Our main contribution is a combinatorial property defined on the Tanner graph associated with the code tester (“well-structured tester”). We show that a family of codes is smoothly locally testable if and only if it has a well-structured tester. As a case study we show that the standard tester for the Hadamard code is “well-structured,” giving an alternative proof of the local testability of the Hadamard code, originally proved by (Blum, Luby, Rubinfeld, J. Comput. Syst. Sci. 47 (1993) 549–595) (STOC 1990). Additional connections to the works of (Ben-Sasson, Harsha, Raskhodnikova, SIAM J. Comput 35 (2005) 1–21) (SICOMP 2005) and of (Lachish, Newman and Shapira, Comput Complex 17 (2008) 70–93) are also discussed. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016
- Published
- 2016
36. A local central limit theorem for triangles in a random graph
- Author
-
Justin Gilmer and Swastik Kopparty
- Subjects
Random graph ,Discrete mathematics ,Characteristic function (probability theory) ,Distribution (number theory) ,Applied Mathematics ,General Mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Combinatorics ,010104 statistics & probability ,010201 computation theory & mathematics ,Perfect graph ,Random regular graph ,Limit (mathematics) ,0101 mathematics ,Nested triangles graph ,Software ,Central limit theorem ,Mathematics - Abstract
In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph G(n, p), where is a fixed constant. Our proof is based on bounding the characteristic function of the number of triangles, and uses several different conditioning arguments for handling different ranges of t. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016
- Published
- 2016
37. Random directed graphs are robustly Hamiltonian
- Author
-
Dan Hefetz, Benny Sudakov, and Angelika Steger
- Subjects
Discrete mathematics ,Random graph ,Strongly connected component ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,Directed graph ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Feedback arc set ,Combinatorics ,Cycle rank ,Nearest neighbor graph ,010201 computation theory & mathematics ,Random regular graph ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Software ,Pancyclic graph ,Mathematics - Abstract
A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph ${\mathcal D}(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $p \gg \log n/\sqrt{n}$, then a.a.s. every subdigraph of ${\mathcal D}(n,p)$ with minimum out-degree and in-degree at least $(1/2 + o(1)) n p$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs., Comment: 35 pages, 1 figure
- Published
- 2015
38. Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
- Author
-
Boris Pittel and Daniel J. Poole
- Subjects
Discrete mathematics ,Applied Mathematics ,General Mathematics ,Asymptotic distribution ,Digraph ,0102 computer and information sciences ,Covariance ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Giant component ,010101 applied mathematics ,Combinatorics ,010201 computation theory & mathematics ,Joint probability distribution ,Order (group theory) ,0101 mathematics ,Realization (systems) ,Software ,Central limit theorem ,Mathematics - Abstract
Two models of a random digraph on n vertices, D(n; Prob(arc) = p) and D(n; number of arcs = m) are studied. In 1990, Karp for D(n;p) and independently T. Luczak for D(n;m = cn) proved that for c > 1, with probability tending to 1, there is an unique strong component of size of order n. Karp showed, in fact, that the giant component has likely size asymptotic to n 2 , where = (c) is the unique positive root of 1 = e c . In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector n (c), (c) := ( 2 ;c 2 ) and two distinct 2 2 covariance matrices, nB(c) and n B(c) +c( 0 (c)) T ( 0 (c))) . To this end, we introduce and analyze a randomized deletion process which determines the directed (1; 1)-core, the maximal digraph with minimum in-degree and out-degree at least 1. This (1; 1)-core contains all nontrivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the (1; 1)-core, those outside the largest strong component, are of polylog order, thus dwarfed by anticipated uctuations, on the scale of n 1=2 , of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.
- Published
- 2015
39. Increasing Hamiltonian paths in random edge orderings
- Author
-
Mikhail Lavrov and Po-Shen Loh
- Subjects
Discrete mathematics ,Random graph ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Hamiltonian path ,Vertex (geometry) ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,Path (graph theory) ,symbols ,Bijection ,Almost surely ,0101 mathematics ,Hamiltonian (quantum mechanics) ,Software ,Mathematics - Abstract
Let f be an edge ordering of Kn: a bijection . For an edge , we call f(e) the label of e. An increasing path in Kn is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvatal and Komlos raised the question of estimating m(n): the minimum value of S(f) over all orderings f of Kn. The best known bounds on m(n) are , due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n – 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/ e. We also prove that with probability 1- o(1), there is an increasing path of length at least 0.85 n, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015
- Published
- 2015
40. On the max-cut of sparse random graphs
- Author
-
Quan Li, David Gamarnik, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Sloan School of Management, Gamarnik, David, and Li, Quan
- Subjects
Random graph ,Discrete mathematics ,Applied Mathematics ,General Mathematics ,Maximum cut ,Probability (math.PR) ,Second moment of area ,0102 computer and information sciences ,Expected value ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Combinatorics ,010104 statistics & probability ,010201 computation theory & mathematics ,FOS: Mathematics ,Cubic graph ,Large deviations theory ,Second moment method ,0101 mathematics ,Software ,Mathematics - Probability ,Mathematics - Abstract
We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erd\H{o}s-R\'{e}nyi graph on $n$ nodes and $\lfloor cn \rfloor$ edges. It is shown in Coppersmith et al. ~\cite{Coppersmith2004} that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region $[c/2+0.37613\sqrt{c},c/2+0.58870\sqrt{c}]$ with high probability (w.h.p.) as $n$ increases, for all sufficiently large $c$. In this paper we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval $[c/2+0.47523\sqrt{c},c/2+0.55909\sqrt{c}]$ w.h.p. as $n$ increases, for all sufficiently large $c$. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as $c$ increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value $c/2+0.47523\sqrt{c}$. It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of $1.36000n$ on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of $1.33773n$., Comment: To appear in Random Structures & Algorithms
- Published
- 2017
41. Spira's theorems on complete linear proofs of systems of linear inequalities
- Author
-
Victor Klee
- Subjects
Combinatorics ,Discrete mathematics ,Linear inequality ,Polyhedron ,Proof theory ,General Mathematics ,Convex polytope ,Convex set ,Mathematical proof ,Convexity ,Mathematics ,Counterexample - Abstract
Motivated by questions of computational complexity, Rabin [7] introduced the notion of a complete proof of a system of inequalities. His work and the related paper of Spira [8] should interest geometers as well as computer scientists, for both papers involve convexity in an essential way. Spira's results concern the possibility of covering the intersection of a convex set C and a convex polyhedron Q with a finite collection P of polyhedra subject to certain conditions, while in Rabin's work the members of P may be more general than polyhedra. Both papers are interesting and treat important questions, but only Rabin's paper is correct in all respects. The present note contains counterexamples to some of Spira's results and establishes a correct version of one of them.
- Published
- 1975
42. Interminable Paths and Trails: Extreme Cases
- Author
-
Gabriel Andrew Dirac
- Subjects
Combinatorics ,Discrete mathematics ,General Mathematics ,Multiplicity (mathematics) ,Notation ,Graph ,Mathematics - Abstract
This paper is concerned with terminable and interminable paths and trails in infinite graphs. It is shown that The only connected graphs which contain no 2 – ∞ way and in which no finite path is terminable are precisely all the 1 – ∞ multiways. The only connected graphs which have no 2 – ∞ trail and in which no finite trail is terminable are precisely all the 1 – ∞ multiways all of whose multiplicities are odd numbers and which have infinitely many bridges. In addition the strucuture of those connected graphs is determined which have a 1 – ∞ trail and in which no 1 – ∞ trail but every finite trail is terminable. In this paper the terminology and notation of a previous paper of the writer [1] and of F. HARARY's book [6] will be used. Furthermore, a graph consisting of the distinct nodes n1,…,nδ (where δ≧1) and of one or more (ni, ni+1)-edges for i = 1,…, δ – 1 will be called a multiway, and analogously for 1 – ∞ and 2 – ∞ multiways. The number of edges joining ni and ni+1 will be called the (ni,+1)-multiplicity. Thus a multiway in which each multiplicity is 1 is a way. Multiplicities are allowed to be infinite.
- Published
- 1978
43. Bewertungen von Limesräumen
- Author
-
K. Weber and W. Filter
- Subjects
Combinatorics ,Set (abstract data type) ,Discrete mathematics ,Generalization ,General Mathematics ,Subadditivity ,Limit (mathematics) ,Uniform space ,Pretopological space ,Mathematics - Abstract
The first aim of this paper is to characterize those limit spaces (X, τ) which can be valuated, i.e. for which a set E of valuations exists such that for each x ∈ X, τ(x) equals the set of filters on X which converge to x relative to E. It is shown further that a separated pretopological space is a URYSOHN-space iff it can be valuated by a set of subadditive valuations. In the second part of the paper a completion is constructed for the separated subadditively valuated limit spaces which can be considered as a generalization of the usual completion of a uniform space.
- Published
- 1989
44. Metric Diophantine approximation with two restricted variables II: A prime and a square‐free integer
- Author
-
Glyn Harman
- Subjects
Combinatorics ,Discrete mathematics ,Lebesgue measure ,Integer ,General Mathematics ,Metric (mathematics) ,Square-free integer ,Diophantine approximation ,Prime (order theory) ,Mathematics ,Real number - Abstract
In this paper we continue the investigation begun in [6] concerning the number of solutions of the inequality for almost all α (in the sense of Lebesgue measure on ℝ), where β is a given real number, , and both m and n are confined to sets of numbertheoretic interest. Our aim is to extend existing results ([7], [8], [5] for example), where only n is restricted. Here we shall prove the following result where, as elsewhere in this paper, p denotes a prime, and a square-free integer may be positive or negative.
- Published
- 1988
45. Two Theorems on Doubly Transitive Permutation Groups
- Author
-
Michael M. Atkinson
- Subjects
Combinatorics ,Discrete mathematics ,Permutation ,Transitive relation ,Series (mathematics) ,Degree (graph theory) ,Group (mathematics) ,General Mathematics ,Permutation group ,Automorphism ,Prime (order theory) ,Mathematics - Abstract
M. D. ATKINSONIn a series of papers [3, 4 and 5] on insoluble (transitive) permutation groupsof degree p = 2q +1, where p and q are primes, N. Ito has shown that, apart from asmall number of exceptions, such a group must be at least quadruply transitive.One of the results which he uses is that an insoluble 2q grou +1 p of degree p =which is not doubly primitive must be isomorphi (3, 2)c wit to PSh p =L 7. Thisresult is due to H. Wielandt, and ltd gives a proof in [3]. It is quite easy to extendthis proof to give the following result: a doubly transitive group of degree 2q + l,where q is prime, which is not doubly primitive, is either sharply doubly transitiveor a group of automorphisms of a bloc A = 1 ank desigd k = 3n wit. Ouh rnotation for the parameters of a block design, v, b, X, k, i r,s standard; see [9].In this paper we shall prove two results about doubly transitive but not doublyprimitive groups which resemble the two results mentioned above.
- Published
- 1973
46. The threshold for d-collapsibility in random complexes*
- Author
-
Nathan Linial and Lior Aronshtam
- Subjects
Discrete mathematics ,Applied Mathematics ,General Mathematics ,010102 general mathematics ,Statistical model ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Combinatorics ,Simplicial complex ,010201 computation theory & mathematics ,struct ,Almost surely ,0101 mathematics ,Software ,Topology (chemistry) ,Mathematics - Abstract
In this paper we determine the threshold for d-collapsibility in the probabilistic model Xdn,p of d-dimensional simplicial complexes. A lower bound for this threshold p=i¾?dn was established in Aronshtam and Linial, Random Struct. Algorithms 46 2015 26-35, and here we show that this is indeed the correct threshold. Namely, for every c>i¾?d, a complex drawn from Xdn,cn is asymptotically almost surely not d-collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260-269, 2016
- Published
- 2015
47. On induced Ramsey numbers fork-uniform hypergraphs
- Author
-
Steven La Fleur, Vojtěch Rödl, and Domingos Dellamonica
- Subjects
Discrete mathematics ,Hypergraph ,Mathematics::Combinatorics ,Applied Mathematics ,General Mathematics ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Combinatorics ,Probabilistic method ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Order (group theory) ,Ramsey's theorem ,Software ,Mathematics - Abstract
Let denote the complete k-uniform k-partite hypergraph with classes of size t and the complete k-uniform hypergraph of order s. One can show that the Ramsey number for and satisfies when t = so(1) as s ∞. The main part of this paper gives an analogous result for induced Ramsey numbers: Let be an arbitrary k-partite k-uniform hypergraph with classes of size t and an arbitrary k-graph of order s. We use the probabilistic method to show that the induced Ramsey number (i.e. the smallest n for which there exists a hypergraph such that any red/blue coloring of yields either an induced red copy of or an induced blue copy of ) satisfies . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 2016
- Published
- 2015
48. Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
- Author
-
Amir Leshem and Oshri Naparstek
- Subjects
Discrete mathematics ,Average-case complexity ,Matching (graph theory) ,Applied Mathematics ,General Mathematics ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,Auction algorithm ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Combinatorics ,010201 computation theory & mathematics ,3-dimensional matching ,0202 electrical engineering, electronic engineering, information engineering ,Worst-case complexity ,Algorithm ,Time complexity ,Software ,Blossom algorithm ,Hopcroft–Karp algorithm ,Mathematics - Abstract
In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We first prove that if for every non-maximum matching on graph G there exist an augmenting path with a length of at most 2l + 1 then the auction algorithm converges after N i¾? l iterations at most. Then, we prove that the expected time complexity of the auction algorithm for bipartite matching on random graphs with edge probability p=clogNN and c > 1 is ONlog2NlogNp w.h.p. This time complexity is equal to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with OlogN processors and shared memory with an expected time complexity of ONlogN. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384-395, 2016
- Published
- 2014
49. How many T-tessellations on k lines? Existence of associated Gibbs measures on bounded convex domains
- Author
-
Jonas Kahn, Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS), and Laboratoire Paul Painlevé - UMR 8524 (LPP)
- Subjects
Discrete mathematics ,Applied Mathematics ,General Mathematics ,Probability (math.PR) ,Regular polygon ,Computer Science::Computational Geometry ,Computer Graphics and Computer-Aided Design ,GeneralLiterature_MISCELLANEOUS ,Enumerative combinatorics ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,Combinatorics ,Set (abstract data type) ,Bounded function ,FOS: Mathematics ,60D05 ,Stochastic geometry ,Mathematics - Probability ,Software ,ComputingMethodologies_COMPUTERGRAPHICS ,Mathematics - Abstract
The paper bounds the number of tessellations with T-shaped vertices on a fixed set of $k$ lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a completely random T-tessellation, as defined by Ki\^en Ki\^eu et al., and of its Gibbsian modifications. The combinatorial bound is sharp, but likely pessimistic in typical cases., Comment: 34 pages, third revised version. Introduction sections 2 and 3 have been reorganised. No change in results or method of proof
- Published
- 2014
50. Diffusivity of a random walk on random walks
- Author
-
Serge Cohen, Thibault Espinasse, James Norris, Emmanuel Boissard, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Statistical Laboratory [Cambridge], Department of Pure Mathematics and Mathematical Statistics (DPMMS), Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM)-Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), and Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Random graph ,Discrete mathematics ,Heterogeneous random walk in one dimension ,Applied Mathematics ,General Mathematics ,Probability (math.PR) ,Central limit theorem ,Loop-erased random walk ,Random element ,Random walk ,05C81, 60F05 ,Computer Graphics and Computer-Aided Design ,Graph ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,Combinatorics ,Mathematics::Probability ,Lévy flight ,FOS: Mathematics ,Quantum walk ,Mathematics - Probability ,ComputingMilieux_MISCELLANEOUS ,Software ,Self-avoiding walk ,Mathematics - Abstract
We consider a random walk Zn1,',ZnK+1∈i¾?K+1 with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor i¾?K2=2K+2 with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267-283, 2015
- Published
- 2014
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.