BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mary Radcliffe

Mary Radcliffe appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.PRData Structures and Algorithmsmath.SPSocial and Information Networks

Catalog footprint

What is connected

6works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2015arXiv

A linear k-fold Cheeger inequality

Given an undirected graph $G$, the classical Cheeger constant, $h_G$, measures the optimal partition of the vertices into 2 parts with relatively few edges between them based upon the sizes of the parts. The well-known Cheeger's inequality states that $2 λ_1 \le h_G \le \sqrt {2 λ_1}$ where $λ_1$ is the minimum nontrivial eigenvalue of the normalized Laplacian matrix. Recent work has generalized the concept of the Cheeger constant when partitioning the vertices of a graph into $k > 2$ parts. While there are several approaches, recent results have shown these higher-order Cheeger constants to be tightly controlled by $λ_{k-1}$, the $(k-1)$-th nontrivial eigenvalue, to within a quadratic factor. We present a new higher-order Cheeger inequality with several new perspectives. First, we use an alternative higher-order Cheeger constant which considers an "average case" approach. We show this measure is related to the average of the first $k-1$ nontrivial eigenvalues of the normalized Laplacian matrix. Further, using recent techniques, our results provide linear inequalities using the $\infty$-norms of the corresponding eigenvectors. Consequently, unlike previous results, this result is relevant even when $λ_{k-1} \to 1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A proof of the Cycle Double Cover Conjecture

Given a bridgeless graph $G$, the Cycle Double Cover Conjecture posits that there is a list of cycles of $G$, such that every edge appears in exactly two cycles on the list. This conjecture was originally posed independently in 1973 by Szekeres and 1979 by Seymour. In 1985, Jaeger demonstrated that it is sufficient to prove in the case that $G$ is a cubic graph. We here present a proof that every bridgeless cubic graph has a cycle double cover by analyzing certain kinds of cycles in the line graph of $G$. Further, in the case that $G$ is cubic, we prove the stronger conjecture that given a bridgeless graph $G$ and a cycle $C$ in $G$, then there exists a cycle double cover of $G$ containing $C$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Bounds on Geometric Eigenvalues of Graphs

The smallest nonzero eigenvalue of the normalized Laplacian matrix of a graph has been extensively studied and shown to have many connections to properties of the graph. We here study a generalization of this eigenvalue, denoted $λ(G, X)$, introduced by Mendel and Naor in 2010, obtained by embedding the vertices of the graph $G$ into a metric space $X$. We consider general bounds on $λ(G, X)$ and $λ(G, H)$, where $H$ is a graph under the standard distance metric, generalizing some existing results for the standard eigenvalue. We consider how $λ(G, H)$ is affected by changes to $G$ or $H$, and show $λ(G, H)$ is not monotone in either $G$ or $H$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Connectivity and giant component in random distance graphs

Various different random graph models have been proposed in which the vertices of the graph are seen as members of a metric space, and edges between vertices are determined as a function of the distance between the corresponding metric space elements. We here propose a model $G=G(X, f)$, in which $(X, d)$ is a metric space, $V(G)=X$, and $\mathbb{P}(u\sim v) = f(d(u, v))$, where $f$ is a decreasing function on the set of possible distances in $X$. We consider the case that $X$ is the $n\times n \times \dots\times n$ integer lattice in dimension $r$, with $d$ the $\ell_1$ metric, and $f(d) = \frac{1}{n^βd}$, and determine a threshold for the emergence of the giant component and connectivity in this model. We compare this model with a traditional Waxman graph. Further, we discuss expected degrees of nodes in detail for dimension 2.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Connectivity and Giant Component of Stochastic Kronecker Graphs

Stochastic Kronecker graphs are a model for complex networks where each edge is present independently according the Kronecker (tensor) product of a fixed matrix k-by-k matrix P with entries in [0,1]. We develop a novel correspondence between the adjacencies in a general stochastic Kronecker graph and the action of a fixed Markov chain. Using this correspondence we are able to generalize the arguments of Horn and Radcliffe on the emergence of the giant component from the case where k = 2 to arbitrary k. We are also able to use this correspondence to completely analyze the connectivity of a general stochastic Kronecker graph.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On expansion of $G_{n, d}$ with respect to $G_{m, d}$

In several works, Mendel and Naor have introduced and developed theory surrounding a nonlinear expansion constant similar to the spectral gap for sequences of graphs, in which one considers embeddings of a graph $G$ into a metric space $X$ \cite{mendel2010towards, mendel2013nonlinear, mendel2014expanders}. Here, we investigate the open question of whether the random regular graph $G_{n, d}$ is an expander when embedded into the metric space of a random regular graph $G_{m, d}$ a.a.s., where $m\leq n$. We show that if $m$ is fixed, the answer is affirmative. In addition, when $m\to \infty$, we provide partial solutions to the problem in the case that $d$ is fixed or that $d\to \infty$ under the constraint $d=o(m^{1/2})$.

0 citations0 reviewsNo code linkedOpen access