✦ LIBER ✦

Dense expanders and pseudo-random bipartite graphs

✍ Scribed by Andrew Thomason

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 331 KB
Volume: 75
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90101-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The random bipartite nearest neighbor gr

The random bipartite nearest neighbor graphs

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 301 KB

The bipartite kth nearest neighbor graphs B are studied. It is shown that B k 1 has a limiting expected matching number of approximately 80% of its vertices, that with high Ž . probability whp B has at least 2 log nr13 log log n vertices not matched, and that whp B 2 3 does have a perfect matching.

Sparse pseudo-random graphs are Hamilton

Sparse pseudo-random graphs are Hamiltonian

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

## Abstract In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a __d__‐regular graph __G__ on __n__ vertices satisfies and __n__ is large enough, then __G__ is Hamiltonian. We also show how our main resu

Pseudo-random properties of self-complem

Pseudo-random properties of self-complementary symmetric graphs

✍ Andrzej Kisielewicz; Wojciech Peisert 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 74 KB

## Abstract There are some results in the literature showing that Paley graphs behave in many ways like random graphs __G__(__n__, 1/2). In this paper, we extend these results to the other family of self‐complementary symmetric graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 310–316, 2004

Long cycles in subgraphs of (pseudo)rand

Long cycles in subgraphs of (pseudo)random directed graphs

✍ Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant __c__ = __c__(γ) such that the following holds. Let __G__ = (__V, E__) be a (pseudo)random directed graph on __n__ vertice

Static and Dynamic Path Selection on Exp

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach

✍ Andrei Z. Broder; Alan M. Frieze; Eli Upfal 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 2 views

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is

On Dense Bipartite Graphs of Girth Eight

On Dense Bipartite Graphs of Girth Eight and Upper Bounds for Certain Configurations in Planar Point–Line Systems

✍ D de Caen; L.A Székely 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 956 KB

In earlier work we showed that if G(m, n) is a bipartite graph with no 4-cycles or 6-cycles, and if m<c 1 n 2 and n<c 2 m 2 , then the number of edges e is O((mn) 2Â3 ). Here we give a more streamlined proof, obtaining some sharp results; for example, if G has minimum degree at least two then e 3 -