Movatterモバイル変換

Question 1

2votes

1answer

46views

Size of family of pairs of edges overlapping at exactly 1 vertex in a non two colorable hypergraph

Show that every n-uniform non 2 colorable hypergraph $H$ contains atleast $\frac{n}{2} {2n-1 \choose n-1}$ unordered pairs of edges each overalapping at exactly 1 vertex. I came across this problem in ...

psychohistorian

41

asked2 days ago

Question 2

2votes

0answers

61views

Every k-fold cover of the real line by intervals can be decomposed into k distinct covers.

A k-fold cover of the real line is a family of sets such that each point is contained inside atleast k sets in the family.I am trying to prove the following fact which i came across in Yufei Zhao's ...

psychohistorian

41

askedNov 22 at 4:18

Question 3

1vote

0answers

40views

Understanding the combinatorial bound choice in a covering argument (Vershynin's HDP)

I'm studying Roman Vershynin's High-Dimensional Probability and am working through Corollary 0.0.4, where he constructs an epsilon-net for a polytope $P$ via averages of vertices. Here's what confused ...

Sophia

21

askedOct 21 at 18:52

Question 4

0votes

1answer

224views

A proof of Rolle's theorem using an uniform distribution

I want to know if the following proof is correct or not. Is this proof known in the literature? Thank you very much for your reply.Rolle’s Theorem: Let $f:[a,b]\to\mathbb{R}$ be such that $f\in C^1\...

TRUSKI

1,155

askedAug 10 at 3:25

Question 5

0votes

1answer

101views

The Probabilistic Method, exercise 2.7.9

This is Exercise 2.7.9 from "The Probabilistic Method" by Noga Alon and Joel Spencer. It's stated as follow:Let $G = (V, E)$ be a bipartite graph with $n$ vertices and a list $S(v)$ of ...

NVA

468

askedJul 3 at 9:51

Question 6

2votes

0answers

76views

topics in probabilistic group theory

I'm a graduate student interested in probabilistic group theory, particularly applications of probability to finite groups beyond commuting probabilities and word maps. I’ve explored topics like gap ...

Muhammad Siddiq Wira Awaldy

31

askedJun 24 at 10:43

Question 7

0votes

0answers

52views

Erdős-Spencer bound on size of covering designs

Theorem 13.4 in "Probabilistic Methods in Combinatorics" by Erdős & Spencer (1974) states that$$M(n,k,\ell) \le \frac{{n \choose \ell}}{{k \choose \ell}} \big( 1 + \log {k \choose \ell} ...

Thomas Steinke

945

askedJun 20 at 22:11

Question 8

1vote

1answer

102views

Ex 13.6.5 of 'The Probabilistic Method 4th' written by Alon-Spencer. Where's my mistake?

I saw this problem Probabilistic methodsand I tried to solve it.Let $n>cm\sqrt{\ln m}$ where $c$ is a large constant. For $1\leq i\leq n$, let $\overrightarrow {u_i}\in\mathbb{R}^m$ with $\|\...

Ross

1,334

askedMar 26 at 6:30

Question 9

2votes

2answers

182views

Chromatic number of a graph with prohibited cliques

How can I bound the maximal possible chromatic number of a graph $G$ with $N$ vertices, such that $\omega(G)≤\kappa$ (where $\omega(G)$ is clique number)?I can pretty simply prove that for any ...

徳山宏樹

47

askedFeb 28 at 15:32

Question 10

1vote

1answer

71views

How does the explanation of this overestimation here work?

I am reading about count-min-sketch which for the implementation is based on a 2 dimensional array to store the frequencies.The width of the array (the number of columns) is calculated by $$\frac{e}{\...

Jim

1,737

askedFeb 4 at 21:53

Question 11

0votes

0answers

112views

Tournament on n vertices that has property $S_k$ [duplicate]

A tournament is an orientation of the edges of a complete graph. We say that a tournament has property $S_k$ if for every set of $k$ players there is one who beats them all. We are able to prove that ...

314r1rf

285

askedJan 23 at 15:28

Question 12

0votes

1answer

118views

Probabilistic Method to construct a low intersecting family of sets

I have a question to the following exercise I found in this book:If I understand the hint correctly, we construct some set $S_i$ by going through each element of the "universe" $\{1, ..., ...

Yellowyeti

35

askedNov 24, 2024 at 10:56

Question 13

1vote

1answer

117views

An inequality of a sum

This inequality is from equation $\left(\bf 20\right)$ in this paper.$\ell \geq 1$ is a variable related to the big O notation below.$\gamma := \lfloor \log_{0.9}(1/l)\rfloor + 1$.For $i \geq 1$, $\...

Student

29

askedNov 4, 2024 at 17:53

Question 14

0votes

1answer

71views

Comparison of two crossing number inequalities

Let $G$ be a simple graph with $n$ vertices and $m$ edges. Thecrossing number of $G$, denoted by $cr(G)$, is the minimum number of crossings in a planar embedding ...

Yixuan Huang

469

askedSep 4, 2024 at 6:22

Question 15

2votes

0answers

138views

Asymptotic upper bound on independence number in random graph

currently I'm learning about random graphs, and struggle with the following result, which is supposed to be well known. Nonetheless I couldn't find a proof of this, and I'm stuck proving it myself:...

Immanuel

621

askedAug 20, 2024 at 14:15

Movatterモバイル変換

Stack Exchange Network

Questions tagged [probabilistic-method]

Size of family of pairs of edges overlapping at exactly 1 vertex in a non two colorable hypergraph

Every k-fold cover of the real line by intervals can be decomposed into k distinct covers.

Understanding the combinatorial bound choice in a covering argument (Vershynin's HDP)

A proof of Rolle's theorem using an uniform distribution

The Probabilistic Method, exercise 2.7.9

topics in probabilistic group theory

Erdős-Spencer bound on size of covering designs

Ex 13.6.5 of 'The Probabilistic Method 4th' written by Alon-Spencer. Where's my mistake?

Chromatic number of a graph with prohibited cliques

How does the explanation of this overestimation here work?

Tournament on n vertices that has property $S_k$ [duplicate]

Probabilistic Method to construct a low intersecting family of sets

An inequality of a sum

Comparison of two crossing number inequalities

Asymptotic upper bound on independence number in random graph

Hot Network Questions

Subscribe to RSS