Zero-one laws for graphs with edge probabilities decaying with distance. Part I

Saharon Shelah

Displaying similar documents to “Zero-one laws for graphs with edge probabilities decaying with distance. Part I”

Zero-one laws for graphs with edge probabilities decaying with distance. Part II

Saharon Shelah (2005)

Fundamenta Mathematicae

Similarity:

Let Gₙ be the random graph on [n] = 1,...,n with the probability of i,j being an edge decaying as a power of the distance, specifically the probability being $p_{| i - j |} = 1 / {| i - j |}^{α}$ , where the constant α ∈ (0,1) is irrational. We analyze this theory using an appropriate weight function on a pair (A,B) of graphs and using an equivalence relation on B∖A. We then investigate the model theory of this theory, including a “finite compactness”. Lastly, as a consequence, we prove that the zero-one law (for first...

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. Kostochka, Douglas B. West (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_{i} > i$ or $d_{n - i} \geq n - i$ . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

The independent domination number of a random graph

Lane Clark, Darin Johnson (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We prove a two-point concentration for the independent domination number of the random graph $G_{n, p}$ provided p²ln(n) ≥ 64ln((lnn)/p).

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A $(0, 2)$ -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0, λ)$ -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0, 2)$ -graph. $(0, 2)$ -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0, λ)$ -graphs and more specifically...

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In the case where G is a claw-free graph, G* is equal to G². We define $σ ° ₜ = m i n \sum_{x \in S} d_{G} (x) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t$ . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Collisions of random walks

Martin T. Barlow, Yuval Peres, Perla Sousi (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

A recurrent graph $G$ has the infinite collision property if two independent random walks on $G$ , started at the same point, collide infinitely often a.s. We give a simple criterion in terms of Green functions for a graph to have this property, and use it to prove that a critical Galton–Watson tree with finite variance conditioned to survive, the incipient infinite cluster in $ℤ^{d}$ with $d \geq 19$ and the uniform spanning tree in $ℤ^{2}$ all have the infinite collision property. For power-law combs and spherically...

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V, E)$ be a simple graph. A $3$ -valued function $f V (G) \to {- 1, 0, 1}$ is said to be a minus dominating function if for every vertex $v \in V$ , $f (N [v]) = \sum_{u \in N [v]} f (u) \geq 1$ , where $N [v]$ is the closed neighborhood of $v$ . The weight of a minus dominating function $f$ on $G$ is $f (V) = \sum_{v \in V} f (v)$ . The minus domination number of a graph $G$ , denoted by $γ^{-} (G)$ , equals the minimum weight of a minus dominating function on $G$ . In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$ , then $γ^{-} (G) \geq 4 (\sqrt{n + 1} - 1) - n .$ (2) For any negative integer $k$ and any positive integer...

The Infinite Random Order of Dimension $k$

Peter Winkler (1985)

Publications du Département de mathématiques (Lyon)

Similarity:

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

Existence of graphs with sub exponential transitions probability decay and applications

Clément Rau (2010)

Bulletin de la Société Mathématique de France

Similarity:

In this paper, we recall the existence of graphs with bounded valency such that the simple random walk has a return probability at time $n$ at the origin of order $exp (- n^{α}),$ for fixed $α \in [0, 1 [$ and with Følner function $exp (n^{\frac{2 α}{1 - α}})$ . This result was proved by Erschler (see [4], [3]); we give a more detailed proof of this construction in the appendix. In the second part, we give an application of the existence of such graphs. We obtain bounds of the correct order for some functional of the local time of a simple random...

On the Law of Large Numbers for Nonmeasurable Identically Distributed Random Variables

Alexander R. Pruss (2013)

Bulletin of the Polish Academy of Sciences. Mathematics

Similarity:

Let Ω be a countable infinite product $Ω ₁^{ℕ}$ of copies of the same probability space Ω₁, and let Ξₙ be the sequence of the coordinate projection functions from Ω to Ω₁. Let Ψ be a possibly nonmeasurable function from Ω₁ to ℝ, and let Xₙ(ω) = Ψ(Ξₙ(ω)). Then we can think of Xₙ as a sequence of independent but possibly nonmeasurable random variables on Ω. Let Sₙ = X₁ + ⋯ + Xₙ. By the ordinary Strong Law of Large Numbers, we almost surely have $E_{*} [X ₁] \leq l i m i n f S ₙ / n \leq l i m s u p S ₙ / n \leq E * [X ₁]$ , where $E_{*}$ and E* are the lower and upper expectations....

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

Similarity:

By a ternary structure we mean an ordered pair $(X_{0}, T_{0})$ , where $X_{0}$ is a finite nonempty set and $T_{0}$ is a ternary relation on $X_{0}$ . By the underlying graph of a ternary structure $(X_{0}, T_{0})$ we mean the (undirected) graph $G$ with the properties that $X_{0}$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if ${x \in X_{0} T_{0} (u, x, v)} \cup {x \in X_{0} T_{0} (v, x, u)} = {u, v} .$ A ternary structure $(X_{0}, T_{0})$ is said to be the B-structure of a connected graph $G$ if $X_{0}$ is the vertex set of $G$ and the following statement holds for all $u, x, y \in X_{0}$ : $T_{0} (x, u, y)$ if and only if $u$ belongs to an...

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V, E_{N})$ where $E_{N}$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^{k} (G) : = N (N (. . . N (G)))$ of G. In particular we investigate conditions for G and k such that $N^{k} (G)$ becomes a complete graph.

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

Similarity:

A $(p, q)$ -sigraph $S$ is an ordered pair $(G, s)$ where $G = (V, E)$ is a $(p, q)$ -graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^{+}$ and $E^{-}$ consist of $m$ positive and $n$ negative edges of $G$ , respectively, where $m + n = q$ . Given positive integers $k$ and $d$ , $S$ is said to be $(k, d)$ -graceful if the vertices of $G$ can be labeled with distinct integers from the set ${0, 1, \dots, k + (q - 1) d}$ such that when each edge $u v$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to...