A note on coloring sparse random graphs

Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring , Random Structures and Algorithms 24 (3) (2004) 259-278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors G_n,p with the minimal number of colors and has expected linear running time, provided that np≤1.33.     

A note on random greedy coloring of uniform hypergraphs

The smallest number of edges forming an n‐uniform hypergraph which is not r‐colorable is denoted by m(n,r). Erd?s and Lovász conjectured that . The best known lower bound was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on the analysis of a random greedy coloring algorithm investigated by Pluhár in 2009. The proof method extends to the case of r‐coloring, and we show that for any fixed r we have improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n‐uniform hypergraph that is not r‐colorable. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 407–413, 2015     

A note on the sum of uniform random variables

An inductive procedure is used to obtain distributions and probability densities for the sum S_n of independent, non-equally uniform random variables. Some known results are then shown to follow immediately as special cases. Under the assumption of equally uniform random variables some new formulas are obtained for probabilities and means related to S_n. Finally, some new recursive formulas involving distributions are derived.     

Connectivity of the uniform random intersection graph

A uniform random intersection graphG(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks, in particular when modelling the network graph of the well-known key predistribution technique due to Eschenauer and Gligor.The paper determines the threshold for connectivity of the graph G(n,m,k) when n→∞ in many situations. For example, when k is a function of n such that k≥2 and m=⌊n^α⌋ for some fixed positive real number α then G(n,m,k) is almost surely connected when

lim infk²n/mlogn>1,     

Perfect matchings in random intersection graphs

Let W ₁,??,W _n be independent random subsets of [m]={1,??,m}. Assuming that each W _i is uniformly distributed in the class of d-subsets of?[m] we study the uniform random intersection graph G _s (n,m,d) on the vertex set {W ₁,??W _n }, defined by the adjacency relation: W _i ??W _j whenever |W _i ??W _j |?Rs. For even?n we show that as n,m???? the edge density threshold for the property that G _s (n,m,d) contains a perfect matching is asymptotically the same as that for G _s (n,m,d) being connected.     

Hamiltonicity of random graphs produced by 2‐processes

Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2‐regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Hamiltonicity in balancedk-partite graphs

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graphG has orderp and minimum degree at least thenG is hamiltonian. Moon and Moser showed that a balanced bipartite graph (the two partite sets have the same order)G has orderp and minimum degree more than thenG is hamiltonian. In this paper, their idea is generalized tok-partite graphs and the following result is obtained: LetG be a balancedk-partite graph with orderp = kn. If the minimum degree

A note on the existence of fractional f-factors in random graphs

Let G=Gn,p be a binomial random graph with n vertices and edge probability p=p(n),and f be a nonnegative integer-valued function defined on V(G) such that 0a≤f(x)≤bnp-2np ㏒n for every x ∈V(G). An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h(e) in [0,1] so that for each vertex x,we have dh G(x)=f(x),where dh G(x) = x∈e h(e) is the fractional degree of x in G. Set Eh = {e:e ∈E(G) and h(e)=0}.If Gh is a spanning subgraph of G such that E(Gh)=Eh,then Gh is called an fractional f-factor of G. In this paper,we prove that for any binomial random graph Gn,p with p≥n-23,almost surely Gn,p contains an fractional f-factor.     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

图的能量与哈密尔顿性

设G是一个无向简单图, A(G)为$G$的邻接矩阵. 用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件; 其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件. 这些结果改进了一些已知的结果.     

A note on uniform exponential convergence of sample average approximation of random functions

Shapiro and Xu (2008) [17] investigated uniform large deviation of a class of Hölder continuous random functions. It is shown under some standard moment conditions that with probability approaching one at exponential rate with the increase of sample size, the sample average approximation of the random function converges to its expected value uniformly over a compact set. This note extends the result to a class of discontinuous functions whose expected values are continuous and the Hölder continuity may be violated for some negligible random realizations. The extension entails the application of the exponential convergence result to a substantially larger class of practically interesting functions in stochastic optimization.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

图的能量与哈密尔顿性

设G是一个无向简单图,A（G）为G的邻接矩阵．用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件：其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件．这些结果改进了一些已知的结果．     

γ-variable first-order logic of uniform attachment random graphs

We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with m edges joining the new vertex with m different vertices chosen uniformly at random from $1,\dots ,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m?2$ variables.     

Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let Γ be a connected simple graph, let V(Γ) and E(Γ) denote the vertex-set and the edge-set of Γ, respectively, and let n=|V(Γ)|. For 1≤i≤n, let e_i be the element of elementary abelian group which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(Γ)={e_i∣1≤i≤n}. We define a set Ω by Ω={e_i+e_j∣{e_i,e_j}∈E(Γ)}, and let Cay_Γ denote the Cayley graph over with respect to Ω. It turns out that Cay_Γ contains Γ as an isometric subgraph. In this paper, the relations between the spectra of Γ and Cay_Γ are discussed. Some conditions on the existence of Hamilton paths and cycles in Γ are obtained.     

Hamiltonicity and colorings of arrangement graphs

We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical) arrangements. While arrangements as geometric objects are well studied in discrete and computational geometry, their graph theoretical properties seem to have received little attention so far. In this paper we show that they provide well-structured examples of families of planar and projective-planar graphs with very interesting properties. Most prominently, spherical arrangements admit decompositions into two Hamilton cycles; this is a new addition to the relatively few families of 4-regular graphs that are known to have Hamiltonian decompositions. Other classes of arrangements have interesting properties as well: 4-connectivity, 3-vertex coloring or Hamilton paths and cycles. We show a number of negative results as well: there are projective arrangements which cannot be 3-vertex colored. A number of conjectures and open questions accompany our results.     

关于一致半格的注记

首先证明了满足极大条件的无限链一定是一致半格.其次,通过探究一致半格与极大条件之间的关系,给出了一致半格为满足极大条件的无限链的充分必要条件.最后,讨论了一致半格与极小条件以及反一致半格与极大条件之间的内在关系,并且给出了相应的例子.