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

Clara Shikhelman

Clara Shikhelman 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.PR

Catalog footprint

What is connected

4works
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

4 published item(s)

preprint2015arXiv

Many $T$ copies in $H$-free graphs

For two graphs $T$ and $H$ with no isolated vertices and for an integer $n$, let $ex(n,T,H)$ denote the maximum possible number of copies of $T$ in an $H$-free graph on $n$ vertices. The study of this function when $T=K_2$ is a single edge is the main subject of extremal graph theory. In the present paper we investigate the general function, focusing on the cases of triangles, complete graphs, complete bipartite graphs and trees. These cases reveal several interesting phenomena. Three representative results are: (i) $ex(n,K_3,C_5) \leq (1+o(1)) \frac{\sqrt 3}{2} n^{3/2},$ (ii) For any fixed $m$, $s \geq 2m-2$ and $t \geq (s-1)!+1 $, $ex(n,K_m,K_{s,t})=Θ(n^{m-\binom{m}{2}/s})$ and (iii) For any two trees $H$ and $T$, $ex(n,T,H) =Θ(n^m)$ where $m=m(T,H)$ is an integer depending on $H$ and $T$ (its precise definition is given in Section 1). The first result improves (slightly) an estimate of Bollobás and Győri. The proofs combine combinatorial and probabilistic arguments with simple spectral techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Converse of Talagrand's Influence Inequality

In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of numbers $0<a_1,a_2,\ldots,a_n\le 1$ such that $\sum_{j=1}^n a_j/(1-\log a_j)\ge C$ for some constant $C>0$, it is possible to find a roughly balanced Boolean function $f$ such that $\textrm{Inf}_j[f] < a_j$ for every $1 \le j \le n$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Packing a randomly edge-colored random graph with rainbow $k$-outs

Let $G$ be a graph on $n$ vertices and let $k$ be a fixed positive integer. We denote by $\mathcal G_{\text{$k$-out}}(G)$ the probability space consisting of subgraphs of $G$ where each vertex $v\in V(G)$ randomly picks $k$ neighbors from $G$, independently from all other vertices. We show that if $δ(G)=ω(\log n)$ and $k\geq 2$, then the following holds for every $p=ω(\log n/δ(G))$. Let $H$ be a random graph obtained by keeping each $e\in E(G)$ with probability $p$ independently at random and then coloring its edges independently and uniformly at random with elements from the set $[kn]$. Then, w.h.p. $H$ contains $t:=(1-o(1))δ(G)p/(2k)$ edge-disjoint graphs $H_1,...,H_t$ such that each of the $H_i$ is \emph{rainbow} (that is, all the edges are colored with distinct colors), and such that for every monotone increasing property of graphs $\mathcal P$ and for every $1\leq i\leq t$ we have $\Pr[\mathcal G_{\text{$k$-out}}(G)\models \mathcal P]\leq \Pr[H_i\models \mathcal P]+n^{-ω(1)}$. Note that since (in this case) a typical member of $\mathcal G_{\text{$k$-out}}(G)$ has average degree roughly $2k$, this result is asymptotically best possible. We present several applications of this; for example, we use this result to prove that for $p=ω(\log n/n)$ and $c=23n$, a graph $H\sim \mathcal G_{c}(K_n,p)$ w.h.p. contains $(1-o(1))np/46$ edge-disjoint rainbow Hamilton cycles. More generally, using a recent result of Frieze and Johansson, the same method allows us to prove that if $G$ has minimum degree $δ(G)\geq (1+\varepsilon)n/2$, then there exist functions $c=O(n)$ and $t=Θ(np)$ (depending on $\varepsilon$) such that the random subgraph $H\sim \mathcal G_{c}(G,p)$ w.h.p. contains $t$ edge-disjoint rainbow Hamilton cycles.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Thresholds and expectation-thresholds of monotone properties with small minterms

Let $N$ be a finite set, let $p \in (0,1)$, and let $N_p$ denote a random binomial subset of $N$ where every element of $N$ is taken to belong to the subset independently with probability $p$ . This defines a product measure $μ_p$ on the power set of $N$, where for $\mathcal{A} \subseteq 2^N$ $μ_p(\mathcal{A}) := Pr[N_p \in \mathcal{A}]$. In this paper we study upward-closed families $\mathcal{A}$ for which all minimal sets in $\mathcal{A}$ have size at most $k$, for some positive integer $k$. We prove that for such a family $μ_p(\mathcal{A}) / p^k $ is a decreasing function, which implies a uniform bound on the coarseness of the thresholds of such families. We also prove a structure theorem which enables to identify in $\mathcal{A}$ either a substantial subfamily $\mathcal{A}_0$ for which the first moment method gives a good approximation of its measure, or a subfamily which can be well approximated by a family with all minimal sets of size strictly smaller than $k$. Finally, we relate the (fractional) expectation threshold and the probability threshold of such a family, using duality of linear programming. This is related to the threshold conjecture of Kahn and Kalai.

0 citations0 reviewsNo code linkedOpen access