Search

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-three}. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model $G(2n,p,q)$, which is a random graph consisting of two distinct Erdős-Renyi graphs $G(n,p)$ joined by random edges with density $q\leq p$. We obtain two main results. First, if $p=\omega(\log n/n)$ and $r=q/p$ is a constant, we show that there is a phase transition in $r$ with threshold $r^*$ (specifically, $r^*=\sqrt{5}-2$ for the Best-of-two, and $r^*=1/7$ for the Best-of-three). If $r>r^*$, the process reaches consensus within $O(\log \log n+\log n/\log (np))$ steps for any initial opinion configuration with a bias of $\Omega(n)$. By contrast, if $r r^*$, we show that, for any initial opinion configuration, the process reaches consensus within $O(\log n)$ steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.

A uniform attachment graph (with parameter $k$), denoted $G_{n,k}$ in the paper, is a random graph on the vertex set $[n]$, where each vertex $v$ makes $k$ selections from $[v-1]$ uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well-studied random graphs: $k$-out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of $G_{n,k}$ to show that the conductance of $G_{n,k}$ is of order $(\log n)^{-1}$. We also study the bootstrap percolation on $G_{n,k}$, where, each vertex is either initially infected with probability $p$, independently of others, or gets infected later as a result of having $r$ infected neighbors at some point. We show that, for $2\le r\le k-1$, if $p\ll (\log n)^{-r/(r-1)}$, then, with probability approaching 1, the process ends before all vertices get infected. On the other hand, if $p\ge \omega(\log n)^{-r/(r-1)}$, where $\omega$ is a certain very slowly growing function, then all the vertices get infected with probability approaching 1.

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the graph. Suppose also that $r < m$, where $2m$ is the average degree. We determine a critical function $a_c(t)$ such that when $a(t) \gg a_c(t)$, complete infection occurs with high probability as $t \rightarrow \infty$, but when $a(t) \ll a_c (t)$, then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to $a(t)$., This paper is significantly different to the previous version

This paper studies a higher dimensional generalization of Frieze's $\zeta(3)$-limit theorem in the Erd\"os-R\'enyi graph process. Frieze's theorem states that the expected weight of the minimum spanning tree converges to $\zeta(3)$ as the number of vertices goes to infinity. In this paper, we study the $d$-Linial-Meshulam process as a model for random simplicial complexes, where $d=1$ corresponds to the Erd\"os-R\'enyi graph process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in $O(n^{d-1})$., Comment: 24 pages

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

We consider consecutive random subdivision of polygons described as follows. Given an initial convex polygon with $d\ge 3$ edges, we choose a point at random on each edge, such that the proportions in which these points divide edges are i.i.d. copies of some random variable $\xi$. These new points form a new (smaller) polygon. By repeatedly implementing this procedure we obtain a sequence of random polygons. The aim of this paper is to show that under very mild non-degenerateness conditions on $\xi$, the shapes of these polygons eventually become "flat" The convergence rate to flatness is also investigated; in particular, in the case of triangles ($d=3$), we show how to calculate the exact value of the rate of convergence, connected to Lyapunov exponents. Using the theory of products of random matrices our paper greatly generalizes the results of Volkov (2013) which are achieved mostly by using ad hoc methods., Comment: 35 pages, 2 figures

Staircase tableaux are combinatorial objects that were first introduced due to a connection with the asymmetric simple exclusion process (ASEP) and Askey-Wilson polynomials. Since their introduction, staircase tableaux have been the object of study in many recent papers. Relevant to this paper, Hitczenko and Janson proved that distribution of parameters on the first diagonal is asymptotically normal. In addition, they conjectured that other diagonals would be asymptotically Poisson. Since then, only the second and the third diagonal were proven to follow the conjecture. This paper builds upon those results to prove the conjecture for the kth diagonal where k is fixed. In particular, we prove that the distribution of the number of α's (β's) on the kth diagonal, k > 1, is asymptotically Poisson with parameter 1/2. In addition, we prove that symbols on the kth diagonal are asymptotically independent and thus, collectively follow the Poisson distribution with parameter 1. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 795–818, 2016

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

Summary This paper deals with the equivalent resistance for the m × n resistor network in both finite and infinite cases. Firstly, we build a difference equation driven by a tridiagonal matrix to model the network; then by performing the diagonalizing transformation on the driving matrix, and using the auxiliary function tz(x,n), we derive two formulae of the equivalent resistance between two corner nodes on a common edge of the network. By comparing two different formulae, we also obtain a new trigonometric identity here. Our framework can be effectively applied in complex impedance networks. As in applications in the LC network, we find that our formulation leads to the occurrence of resonances at frequencies associated with (n + 1)ϕt = kπ. This somewhat curious result suggests the possibility of practical applications of our formulae to resonant circuits. At the end of the paper, two other formulae of an m × n resistor network are proposed. Copyright © 2014 John Wiley & Sons, Ltd.

SUMMARY In this paper, we study the perturbation bound for the Perron vector of an mth-order n-dimensional transition probability tensor P=(pi1,i2,…,im) with pi1,i2,…,im⩾0 and ∑i1=1npi1,i2,…,im=1. The Perron vector x associated to the largest Z-eigenvalue 1 of P, satisfies Pxm−1=x where the entries xi of x are non-negative and ∑i=1nxi=1. The main contribution of this paper is to show that when P is perturbed to an another transition probability tensor P by ΔP, the 1-norm error between x and x is bounded by m, ΔP, and the computable quantity related to the uniqueness condition for the Perron vector x of P. Based on our analysis, we can derive a new perturbation bound for the Perron vector of a transition probability matrix which refers to the case of m = 2. Numerical examples are presented to illustrate the theoretical results of our perturbation analysis. Copyright © 2013 John Wiley & Sons, Ltd.

The eigenproblems of the rank-one updates of the matrices have lots of applications in scientific computation and engineering such as the symmetric tridiagonal eigenproblems by the divide-andconquer method and Web search engine. Many researchers have well studied the algorithms for computing eigenvalues of Hermitian matrices updated by a rank-one matrix [1–6]. Recently, Ding and Zhou studied a spectral perturbation theorem for rank-one updated matrices of special structure in [7] and considered two applications. Cheng, Luo, and Li considered the bounds of the smallest and largest eigenvalues for rank-one modification of Hermitian matrices [8]. Eigenvalue bounds for perturbations of Hermitian matrices have been considered by Ipsen and Nadler in [9]. In this paper, we consider the bounds of the eigenvalues for rank-one modification of Hermitian matrices. The ideas of this paper were mainly motivated by one of [9]. We study the following form

In this paper, a digital filter for the generation/correlation of binary Golay pairs of sequences of length 2Ni¾?10Mi¾?26PN, M and P are non-negative integers is proposed. It is carried out by means of a novel Golay kernel 26 decomposition, also introduced in this paper, combined with building blocks of Golay kernels 2 and 10, presented in previous works. The proposed filter has a similar architecture to the digital filter for the generation/correlation of Golay multilevel pairs of sequences, where the parameters at intermediate stages have to be adjusted to obtain Golay binary pairs of sequences in the final stage. Copyright © 2013 John Wiley & Sons, Ltd.

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

Two new eigenvalue inclusion sets for tensors are established. It is proved that the new eigenvalue inclusion sets are tighter than that in Qi’s paper “Eigenvalues of a real supersymmetric tensor”. As applications, upper bounds for the spectral radius of a nonnegative tensor are obtained, and it is proved that these upper bounds are sharper than that in Yang’s paper “Further results for Perron–Frobenius theorem for nonnegative tensors”. And some sufficient conditions of the positive definiteness for an even-order real supersymmetric tensor are given. Copyright © 2012 John Wiley & Sons, Ltd.

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.

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.

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

This paper presents a framework for comparing bivariate distributions according to their degree of regression dependence. We introduce the general concept of a regression dependence order (RDO). In addition, we deflne a new nonparametric measure of regression dependence and study its properties. Beside being monotone in the new RDOs, the measure takes on its extreme values precisely at independence and almost sure functional dependence, respectively. A consistent nonparametric estimator of the new measure is constructed and its asymptotic properties are investigated. Finally, the flnite sample properties of the estimate are studied by means of small simulation study. 1. Introduction and motivation. There is an extensive body of literature on the problem of ordering and measuring the dependence of two random variables. Almost all of the research in this area is concerned with the concept of positive dependence. Orders of positive dependence were considered by many authors, e.g., Lehmann [16], Esary et al. [7] and Schriever [24]; see also Scarsini and Shaked [23] for a detailed survey. Axiomatic approaches to orders and measures of positive dependence were introduced by Kimeldorf and Sampson [14] and Scarsini [22], respectively. The abundance of notions of positive dependence contrasts, however, with the silence concerning regression dependence, with the exception of the work of Da , browska [3, 4] and the measure suggested by Hall [12]. This paper presents a new approach to the problem of ordering and measuring regression dependence in the bivariate case. The terms \order" and \ordering" are used in the sense of a preorder, i.e., a re∞exive and transitive relation. We drop the requirement of antisymmetry in order to allow for an arbitrary functional form of the regression. For convenience, an order for random variables and the corresponding relations for distributions and distribution functions are used synonymously. Also, we do not strictly dis

In a recent paper on the same topic, we studied the problem of modifying the optimal solution to a class of transportation problems with linear fractional objective function when basis preserving rim operators are applied to vary the rim conditions as a linear function of a single parameter. We continue this study in the present paper and study various transformations arising as a result of applying cost and bound operators. As before, we confine to basis preserving operators and develop algorithms for applying any of the cost operators and for finding the maximum limit for δ. A small numerical example is solved at the end to illustrate various results. In Teil I wurde fur eine Klasse von Transportproblemen mit gebrochen-linearer Zielfunktion die Modifikation der optimalen Losung untersucht, falls basiserhaltende RIM-Operatoren angewandt werden, um die RIM- Bedingungen als lineare Funktion eines einzigen Parameters zu andern. Im vorliegenden Teil II setzen wir diese Untersuchungen fort und studieren verschiedene Transformationen, die als Ergebnis von Kosten- und Schranken-Operatoren auftreten. Wie zuvor beschranken wir uns auf basiserhaltende Operatoren und entwickeln Algorithmen, um jeden Kosten-Operator anzuwenden und um die ausersten Grenzen fur δ zu finden. Ein kleines numerisches Beispiel wurde gelost, um die verschiedenen Ergebnisse zu veranschaulichen.

Let A be an n × n symmetric matrix of bandwidth 2m + 1. The matrix need not be positive definite. In this paper we will present an algorithm for factoring A which preserves symmetry and the band structure and limits element growth in the factorization. With this factorization one may solve a linear system with A as the coefficient matrix and determine the inertia of A, the number of positive, negative, and zero eigenvalues of A. The algorithm requires between 1/2nm2 and 5/4nm2 multiplications and at most (2m + 1)n locations compared to non-symmetric Gaussian elimination which requires between nm2 and 2nm2 multiplications and at most (3m + 1)n locations. Our algorithm reduces A to block diagonal form with 1 × 1 and 2 × 2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce non-zero elements outside the original band, column/row transformations are used to retract the bandwidth. To decrease the operation count and the necessary storage, we use the fact that the correction outside the band is rank-1 and invert the process, applying the transformations that would restore the bandwidth first, followed by a modified correction. This paper contains an element growth analysis and a computational comparison with LAPACKs non-symmetric band routines and the Snap-back code of Irony and Toledo. Copyright © 2007 John Wiley & Sons, Ltd.

In this paper, we derive asymptotic formulas for the signless noncentral q-Stirling numbers of the first kind and for the corresponding series. The signless noncentral q-Stirling numbers of the first kind appear as coefficients of a polynomial of q-number [t]q, expressing the noncentral ascending q-factorial of t of order m and noncentrality parameter k. In this paper, we have two main purposes. The first is to give an expression by which we obtain the asymptotic behavior of these coefficients, using the saddle point method. The second main purpose is to derive an asymptotic expression for the signless noncentral q-Stirling of the first kind series by using the singularity analysis method. We then apply our first formula to provide asymptotic expressions for probability functions of the number of successes in m trials and of the number of trials until the occurrence of the nth success in sequences of Bernoulli trials with varying success probability which are both written in terms of the signless noncentral q-Stirling numbers of the first kind. In addition, we present some numerical calculations using the computer program MAPLE indicating that our expressions are close to the actual values of the signless noncentral q-Stirling numbers of the first kind and of the corresponding series even for moderate values of m.

The rotation correspondence is a map that sends the set of plane trees onto the set of binary trees. In this paper, we first show that when n goes to + ∞, the image by the rotation correspondence of a uniformly chosen random plane tree τ with n nodes is close to 2τ (in a sense to be defined). The second part of the paper is devoted to the right and left depth of nodes in binary trees. We show that the empiric measure (suitably normalized) associated with the difference of the right depth and the left depth processes converges to the integrated super Brownian excursion.

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.

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].

In this paper, we consider a sequence of multibubble solutions u k of the equation (0.1) Δ 0 u k + ρ k (he uk /f M he u k d μ -1)=0 in M, where h is a C 2,β positive function in a compact Riemann surface M, and ρ k is a constant satisfying lim k→+ ∞ ρ k = 8mπ for some positive integer m ≥ 1. We prove among other things that ρ k - 8mπ = 2/m m Σ/j=1h -1 (p k,j )(Δ 0 log h(p k,j ) + 8mπ - 2K(p k,j ))λ k,j e -λk,j + O(e -λk,j ), where p k,j are centers of the bubbles of u k and λ k,j are the local maxima of u k after adding a constant. This yields a uniform bound of solutions as ρ k converges to 8mπ from below provided that Δ 0 log h(p k,j ) + 8mπ - 2K(p k,j ) > 0. It generalizes a previous result, due to Ding, Jost, Li, and Wang [18] and Nolasco and Tarantello [31], which says that any sequence of minimizers u k is uniformly bounded if ρ k 0 for any maximum point p of the sum of 2 log h and the regular part of the Green function, where K is the Gaussian curvature of M. The analytic work of this paper is the first step toward computing the topological degree of (0.1), which was initiated by Li [24].

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

This paper reviews geometric measures used to assess the shape of finite elements in two- and three-dimensional meshes. Measures have been normalized and made scale invariant whenever possible. This paper also introduces a Universal Similarity Region that enhances comparisons of triangles and their measures. As a byproduct, the USR provides a dynamic way to compare improved triangular meshes. Copyright © 2000 John Wiley & Sons, Ltd.

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

We consider the problem of sampling independent sets of a graph with maximum degree δ. The weight of each independent set is expressed in terms of a fixed positive parameter λ≤2/(δ−2), where the weight of an independent set σ is λ|σ|. The Glauber dynamics is a simple Markov chain Monte Carlo method for sampling from this distribution. We show fast convergence (in O(n log n) time) of this dynamics. This paper gives the more interesting proof for triangle-free graphs. The proof for arbitrary graphs is given in a companion paper (E. Vigoda, Technical Report TR-99-003, International Computer Institute, Berkeley, CA, 1998). We also prove complementary hardness of approximation results, which show that it is hard to sample from this distribution when λ>c/δ for a constant c≤0. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 229–241, 1999

This paper is mainly concerned with sets which do not contain four-term arithmetic progressions, but are still very rich in three term arithmetic progressions, in the sense that all sufficiently large subsets contain at least one such progression. We prove that there exists a positive constant c and a set A ⊂ F^n_q which does not contain a four-term arithmetic progression, with the property that for every subset A′ ⊂ A with |A′| ≥ |A|^(1−c), A′ contains a nontrivial three term arithmetic progression. We derive this from a more general quantitative Roth-type theorem in random subsets of F^n_q, which improves a result of Kohayakawa-Luczak-Rodl/Tao-Vu. We also discuss a similar phenomenon over the integers, where we show that for all ϵ > 0, and all sufficiently large N ∈ N, there exists a four-term progression-free set A of size N with the property that for every subset A′ ⊂ A with |A′| ≫ 1/(logN)^(1−ϵ)⋅ N contains a nontrivial three term arithmetic progression. Finally, we include another application of our methods, showing that for sets in F^n_q or Z the property of "having nontrivial three-term progressions in all large subsets" is almost entirely uncorrelated with the property of "having large additive energy".

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

Given a graph sequence $\{G_n\}_{n \geq 1}$ denote by $T_3(G_n)$ the number of monochromatic triangles in a uniformly random coloring of the vertices of $G_n$ with $c \geq 2$ colors. This arises as a generalization of the birthday paradox, where $G_n$ corresponds to a friendship network and $T_3(G_n)$ counts the number of triples of friends with matching birthdays. In this paper we prove a central limit theorem (CLT) for $T_3(G_n)$ with explicit error rates. The proof involves constructing a martingale difference sequence by carefully ordering the vertices of $G_n$, based on a certain combinatorial score function, and using a quantitive version of the martingale CLT. We then relate this error term to the well-known fourth moment phenomenon, which, interestingly, holds only when the number of colors $c \geq 5$. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any $c \geq 2$, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of $T_3(G_n)$, whenever $c \geq 5$. Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in Bhattacharya et al. (2017)., Comment: 30 pages, 2 figures

This paper is devoted to the study of flows associated to non-smooth vector fields. We prove the well-posedness of regular Lagrangian flows associated to vector fields $\mathbf{B}=(\mathbf{B}^1,...,\mathbf{B}^d)\in L^1(\mathbb{R}_+;L^1(\mathbb{R}^d)+L^\infty(\mathbb{R}^d))$ satisfying $ \mathbf{B}^i=\sum_{j=1}^{m}\mathbf{K}_j^i*b_j,$ $b_j\in L^1(\mathbb{R}_+,BV(\mathbb{R}^d))$ and $\operatorname{div}(\mathbf{B})\in L^1(\mathbb{R}_+;L^\infty(\mathbb{R}^d))$ for $d,m\geq 2$, where $(\mathbf{K}_j^i)_{i,j}$ are singular kernels in $\mathbb{R}^d$. Moreover, we also show that there exist an autonomous vector-field $\mathbf{B}\in L^1(\mathbb{R}^2)+L^\infty(\mathbb{R}^2)$ and singular kernels $(\mathbf{K}_j^i)_{i,j}$, singular Radon measures $\mu_{ijk}$ in $\mathbb{R}^2$ satisfying $\partial_{x_k} \mathbf{B}^i=\sum_{j=1}^{m}\mathbf{K}_j^i\star\mu_{ijk}$ in distributional sense for some $m\geq 2$ and for $k,i=1,2$ such that regular Lagrangian flows associated to vector field $\mathbf{B}$ are not unique.

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.

In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $\alpha(G)\geq (f(d,r)-\epsilon(g,d,r))n$, where $\epsilon(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

Orthogonal systems in $\mathrm{L}_2(\mathbb{R})$, once implemented in spectral methods, enjoy a number of important advantages if their differentiation matrix is skew-symmetric and highly structured. Such systems, where the differentiation matrix is skew-symmetric, tridiagonal and irreducible, have been recently fully characterised. In this paper we go a step further, imposing the extra requirement of fast computation: specifically, that the first $N$ coefficients {of the expansion} can be computed to high accuracy in $\mathcal{O}(N\log_2N)$ operations. We consider two settings, one approximating a function $f$ directly in $(-\infty,\infty)$ and the other approximating $[f(x)+f(-x)]/2$ and $[f(x)-f(-x)]/2$ separately in $[0,\infty)$. In each setting we prove that there is a single family, parametrised by $\alpha,\beta > -1$, of orthogonal systems with a skew-symmetric, tridiagonal, irreducible differentiation matrix and whose coefficients can be computed as Jacobi polynomial coefficients of a modified function. The four special cases where $\alpha, \beta= \pm 1/2$ are of particular interest, since coefficients can be computed using fast sine and cosine transforms. Banded, Toeplitz-plus-Hankel multiplication operators are also possible for representing variable coefficients in a spectral method. In Fourier space these orthogonal systems are related to an apparently new generalisation of the Carlitz polynomials.

The $r$-size-Ramsey number $\hat{R}_r(H)$ of a graph $H$ is the smallest number of edges a graph $G$ can have, such that for every edge-coloring of $G$ with $r$ colors there exists a monochromatic copy of $H$ in $G$. The notion of size-Ramsey numbers has been introduced by Erdős, Faudree, Rousseau and Schelp in 1978, and has attracted a lot of attention ever since. For a graph $H$, we denote by $H^q$ the graph obtained from $H$ by subdividing its edges with $q{-}1$ vertices each. In a recent paper of Kohayakawa, Retter and R{o}dl, it is shown that for all constant integers $q,r\geq 2$ and every graph $H$ on $n$ vertices and of bounded maximum degree, the $r$-size-Ramsey number of $H^q$ is at most $(\log n)^{20(q-1)}n^{1+1/q}$, for $n$ large enough. We improve upon this result using a significantly shorter argument by showing that $\hat{R}_r(H^q)\leq O(n^{1+1/q})$ for any such graph $H$.

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”

Let T-n be a twist knot with n half-twists and G(n) be the graph of T-n. The closed neighborhood N[v] of a vertex v in G(n), which included at least one colored vertex for each color in a proper n-coloring of G(n), is called a rainbow neighborhood. There are different types of graph coloring in the literature. We consider some of these types in here. In this paper, we determine the chromatic number of graphs of twist knots and study rainbow neighborhood of graphs of twist knots. We determine the rainbow neighborhood number and the fading number of them. Furthermore, we determine coupon coloring and the coupon coloring number of graphs of twist knots.

Given graphs $F,H$ and $G$, we say that $G$ is $(F,H)_v$-Ramsey if every red/blue vertex colouring of $G$ contains a red copy of $F$ or a blue copy of $H$. Results of {\L}uczak, Ruci\'nski and Voigt and, subsequently, Kreuter determine the threshold for the property that the random graph $G(n,p)$ is $(F,H)_v$-Ramsey. In this paper we consider the sister problem in the setting of randomly perturbed graphs. In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is $(F,H)_v$-Ramsey for all pairs $(F,H)$ that involve at least one clique., Comment: 21 pages

SUMMARY This paper gives information about the spectral decomposition of the covariance matrices of a multinomial. It is a note to the paper of Tanabe and Sagae which gives fascinating information about the Cholesky decomposition of the covariance matrices of multinomial distributions.

We provide the first nontrivial upper bound for the chemical distance exponent in two-dimensional critical percolation. Specifically, we prove that the expected length of the shortest horizontal crossing path of a box of side length $n$ in critical percolation on $\mathbb{Z}^2$ is bounded by $Cn^{2-\delta}\pi_3(n)$, for some $\delta>0$, where $\pi_3(n)$ is the "three-arm probability to distance $n$." This implies that the ratio of this length to the length of the lowest crossing is bounded by an inverse power of $n$ with high probability. In the case of site percolation on the triangular lattice, we obtain a strict upper bound for the exponent of $4/3$. The proof builds on the strategy developed in our previous paper, but with a new iterative scheme, and a new large deviation inequality for events in annuli conditional on arm events, which may be of independent interest.

A recent result of Condon, Kim, K\"{u}hn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. Moreover, this implies that for any $\alpha>0$ and an $n$-vertex almost $\alpha n$-regular graph $G$, with high probability, the randomly perturbed graph $G\cup \mathbf{G}(n,O(\frac{1}{n}))$ has an approximate decomposition into all collections of bounded degree trees of size at most $(1-o(1))n$ simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey-Tur\'an theory and the randomly perturbed graph model., Comment: 15 pages

In this paper we propose algorithms for allocating $n$ sequential balls into $n$ bins that are interconnected as a $d$-regular $n$-vertex graph $G$, where $d\ge3$ can be any integer.Let $l$ be a given positive integer. In each round $t$, $1\le t\le n$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk of length $l$ from the chosen node.Then it allocates itself on one of the visited nodes with minimum load (ties are broken uniformly at random). Suppose that $G$ has a sufficiently large girth and $d=\omega(\log n)$. Then we establish an upper bound for the maximum number of balls at any bin after allocating $n$ balls by the algorithm, called {\it maximum load}, in terms of $l$ with high probability. We also show that the upper bound is at most an $O(\log\log n)$ factor above the lower bound that is proved for the algorithm. In particular, we show that if we set $l=\lfloor(\log n)^{\frac{1+\epsilon}{2}}\rfloor$, for every constant $\epsilon\in (0, 1)$, and $G$ has girth at least $\omega(l)$, then the maximum load attained by the algorithm is bounded by $O(1/\epsilon)$ with high probability.Finally, we slightly modify the algorithm to have similar results for balanced allocation on $d$-regular graph with $d\in[3, O(\log n)]$ and sufficiently large girth.

Let $\{G_i\}$ be the random graph process: starting with an empty graph $G_0$ with $n$ vertices, in every step $i \geq 1$ the graph $G_i$ is formed by taking an edge chosen uniformly at random among the non-existing ones and adding it to the graph $G_{i - 1}$. The classical `hitting-time' result of Ajtai, Koml\'{o}s, and Szemer\'{e}di, and independently Bollob\'{a}s, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches $2$, that is if $\delta(G_i) \ge 2$ then $G_i$ is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for $m \geq (\tfrac{1}{6} + o(1))n\log n$ edges, the $2$-core of the graph $G_m$ remains Hamiltonian even after an adversary removes $(\tfrac{1}{2} - o(1))$-fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings., Comment: 23 pages; small updates to the paper after anonymous reviewers' reports

It is well known that many random graphs with infinite variance degrees are ultra-small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k -(τ - 1) with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to 2 log log n | log ( τ - 2 ) | and 4 log log n | log ( τ - 2 ) | , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order log log n precisely when the minimal forward degree d fwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus 2 / log d fwd . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.