搜索结果: 1-15 共查到“数理逻辑与数学基础 graphs”相关记录18条 . 查询时间(0.014 秒)
Given a sequence {αn} in (0, 1) converging to a rational, we examine
the model theoretic properties of structures obtained as limits of ShelahSpencer
graphs G(m, m−αn ). We show that in most c...
THRESHOLD GRAPH LIMITS AND RANDOM THRESHOLD GRAPHS
Limit theory the threshold figure model random threshold figure
2015/7/8
We study the limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples for the emerging theory of graph limits.
RANDOM GRAPHS WITH A GIVEN DEGREE SEQUENCE。
On incompactness for chromatic number of graphs
set theory graphs chromatic number compactness non-reflecting stationary sets
2012/5/9
We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality kappa . We prove that one can define a graph G whose chromatic number is > kappa, while the chromatic nu...
Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
edge-colored graph rainbow connection number Nordhaus-Gaddumtype
2011/1/21
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted rc(G), is the minimum number of c...
A directed graph is set-homogeneous if, whenever U and V are isomorphic finite subdigraphs, there is an automorphism g of the digraph with U^g=V. Here, extending work of Lachlan on finite homogeneous...
Induced subgraphs in sparse random graphs with given degree sequence
Induced subgraphs math
2010/11/22
For any $S\subset [n]$, we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is a given graph $H$ on the vertex set $S$. The result holds for any $d=o(n^{1/3})$ and is fu...
The rainbow connectivity of Cayley graphs of Abelian groups
The rainbow connectivity Cayley graphs of Abelian groups
2010/11/9
A path in an edge-colored graph $G$, where adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connectivity $rc(G)$ of $G$ i...
Segment representation of a subclass of co-planar graphs
Segment representation a subclass of co-planar graphs
2010/11/11
A graph is said to be a segment graph if its vertices can be mapped to line segments in the plane such that two vertices have an edge between them if and only if their corresponding line segments int...
Connectivity and Minimal Distance Spectral Radius of Graphs
Connectivity Spectral Radius of Graphs
2010/11/15
In this paper, we study how the distance spectral radius behaves when the graph is perturbed by grafting edges. As applications, we also determine the graph with $k$ cut vertices (respectively, $k$ cu...
Spectral distributions of adjacency and Laplacian matrices of random graphs
Spectral distributions Laplacian matrices random graphs
2010/11/18
In this paper, we investigate the spectral properties of the adjacency and the Laplacian matrices of random graphs. We prove that: (i) the law of large numbers for the spectral norms and the largest ...
A probabilistic approach to local limit theorems with applications to random graphs
local limit theorems applications to random graphs
2010/11/19
In this article, we develop a general method to obtain local limit theorems from distributional limit theorems. Our results use probabilistic arguments and yield explicit bounds on the quality of app...
A stationary random graph is a random rooted graph whose distribution is invariant under re-rooting along the simple random walk. We adapt the entropy technique developed for Cayley graphs and show i...
The Fractional Chromatic Number of Triangle-free Graphs with $\Delta\leq 3$
Triangle-free Graphs Combinatorics
2010/11/18
Let $G$ be any triangle-free graph with maximum degree $\Delta\leq 3$. Staton proved that the independence number of $G$ is at least $\frac{5}{14}n$. Heckman and Thomas conjectured that Staton's resul...
On the Banach space valued Azuma inequality and small set isoperimetry of Alon-Roichman graphs
Banach space valued Azuma inequality small set isoperimetry of Alon-Roichman graphs
2010/12/14
We discuss the connection between the expansion of small sets in graphs, and the Schatten norms of their adjacency matrix. In conjunction with a variant of the Azuma inequality for uniformly smooth no...