Source author record

Clara Shikhelman

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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

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.

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.

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.

Clara Shikhelman

Research overview

Is this your work?

4 publications

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

On the Converse of Talagrand's Influence Inequality

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

Thresholds and expectation-thresholds of monotone properties with small minterms

See the researcher in context

Building this map preview

Clara Shikhelman

Research overview

Is this your work?

4 publications

Many TTT copies in HHH-free graphs

On the Converse of Talagrand's Influence Inequality

Packing a randomly edge-colored random graph with rainbow kkk-outs

Thresholds and expectation-thresholds of monotone properties with small minterms

See the researcher in context

Building this map preview

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

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