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

Yuval Peled

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

ResearcherUnclaimed source record
math.COmath.PRmath.AT

Catalog footprint

What is connected

9works
3topics
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

9 published item(s)

preprint2022arXiv

On the $d$-dimensional algebraic connectivity of graphs

The $d$-dimensional algebraic connectivity $a_d(G)$ of a graph $G=(V,E)$, introduced by Jordán and Tanigawa, is a quantitative measure of the $d$-dimensional rigidity of $G$ that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set $V$ into $\mathbb{R}^d$. Here, we analyze the $d$-dimensional algebraic connectivity of complete graphs. In particular, we show that, for $d\geq 3$, $a_d(K_{d+1})=1$, and for $n\geq 2d$, \[ \left\lceil\frac{n}{2d}\right\rceil-2d+1\leq a_d(K_n) \leq \frac{2n}{3(d-1)}+\frac{1}{3}. \]

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The threshold for stacked triangulations

A \emph{stacked triangulation} of a $d$-simplex $\mathbf{o}=\{1,\ldots,d+1\}$ ($d\geq 2$) is a triangulation obtained by repeatedly subdividing a $d$-simplex into $d+1$ new ones via a new vertex (the case $d=2$ is known as an Appolonian network). We study the occurrence of such a triangulation in the Linial--Meshulam model, i.e., for which $p$ does the random simplicial complex $Y\sim \mathcal{Y}_d(n,p)$ contain the faces of a stacked triangulation of the $d$-simplex $\mathbf{o}$, with its internal vertices labeled in $[n]$. In the language of bootstrap percolation in hypergraphs, it pertains to the threshold for $K_{d+2}^{d+1}$, the $(d+1)$-uniform clique on $d+2$ vertices. Our main result identifies this threshold for every $d\geq 2$, showing it is asymptotically $(α_d n)^{-1/d}$, where $α_d$ is the growth rate of the Fuss--Catalan numbers of order $d$. The proof hinges on a second moment argument in the supercritical regime, and on Kalai's algebraic shifting in the subcritical regime.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Noise sensitivity of critical random graphs

We study noise sensitivity of properties of the largest components $({\cal C}_j)_{j\geq 1}$ of the random graph ${\cal G}(n,p)$ in its critical window $p=(1+λn^{-1/3})/n$. For instance, is the property "$|{\cal C}_1|$ exceeds its median size" noise sensitive? Roberts and Şengül (2018) proved that the answer to this is yes if the noise $ε$ is such that $ε\gg n^{-1/6}$, and conjectured the correct threshold is $ε\gg n^{-1/3}$. That is, the threshold for sensitivity should coincide with the critical window---as shown for the existence of long cycles by the first author and Steif (2015). We prove that for $ε\gg n^{-1/3}$ the pair of vectors $ n^{-2/3}(|{\cal C}_j|)_{j\geq 1}$ before and after the noise converges in distribution to a pair of i.i.d. random variables, whereas for $ε\ll n^{-1/3}$ the $\ell^2$-distance between the two goes to 0 in probability. This confirms the above conjecture: any Boolean function of the vector of rescaled component sizes is sensitive in the former case and stable in the latter. We also look at the effect of the noise on the metric space $n^{-1/3}({\cal C}_j)_{j\geq 1}$. E.g., for $ε\geq n^{-1/3+o(1)}$, we show that the joint law of the spaces before and after the noise converges to a product measure, implying noise sensitivity of any property seen in the limit, e.g., "the diameter of ${\cal C}_1$ exceeds its median."

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the phase transition in random simplicial complexes

It is well-known that the $G(n,p)$ model of random graphs undergoes a dramatic change around $p=\frac 1n$. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant (i.e., order $Ω(n)$) connected component. Several years ago, Linial and Meshulam have introduced the $X_d(n,p)$ model, a probability space of $n$-vertex $d$-dimensional simplicial complexes, where $X_1(n,p)$ coincides with $G(n,p)$. Within this model we prove a natural $d$-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real $d$-th homology of complexes from $X_d(n,p)$. We also compute the real Betti numbers of $X_d(n,p)$ for $p=c/n$. Finally, we establish the emergence of giant shadow at this threshold. (For $d=1$ a giant shadow and a giant component are equivalent). Unlike the case for graphs, for $d\ge 2$ the emergence of the giant shadow is a first order phase transition.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A random triadic process

Given a random 3-uniform hypergraph $H=H(n,p)$ on $n$ vertices where each triple independently appears with probability $p$, consider the following graph process. We start with the star $G_0$ on the same vertex set, containing all the edges incident to some vertex $v_0$, and repeatedly add an edge $xy$ if there is a vertex $z$ such that $xz$ and $zy$ are already in the graph and $xzy \in H$. We say that the process propagates if it reaches the complete graph before it terminates. In this paper we prove that the threshold probability for propagation is $p=\frac{1}{2\sqrt{n}}$. We conclude that $p=\frac{1}{2\sqrt{n}}$ is an upper bound for the threshold probability that a random 2-dimensional simplicial complex is simply connected.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Extremal problems on shadows and hypercuts in simplicial complexes

Let $F$ be an $n$-vertex forest. We say that an edge $e\notin F$ is in the shadow of $F$ if $F\cup\{e\}$ contains a cycle. It is easy to see that if $F$ is "almost a tree", that is, it has $n-2$ edges, then at least $\lfloor\frac{n^2}{4}\rfloor$ edges are in its shadow and this is tight. Equivalently, the largest number of edges an $n$-vertex cut can have is $\lfloor\frac{n^2}{4}\rfloor$. These notions have natural analogs in higher $d$-dimensional simplicial complexes, graphs being the case $d=1$. The results in dimension $d>1$ turn out to be remarkably different from the case in graphs. In particular the corresponding bounds depend on the underlying field of coefficients. We find the (tight) analogous theorems for $d=2$. We construct $2$-dimensional "$\mathbb Q$-almost-hypertrees" (defined below) with an empty shadow. We also show that the shadow of an "$\mathbb F_2$-almost-hypertree" cannot be empty, and its least possible density is $Θ(\frac{1}{n})$. In addition we construct very large hyperforests with a shadow that is empty over every field. For $d\ge 4$ even, we construct $d$-dimensional $\mathbb{F} _2$-almost-hypertree whose shadow has density $o_n(1)$. Finally, we mention several intriguing open questions.

0 citations0 reviewsNo code linkedOpen access