All Questions
Tagged with random-graphs hypergraph
8 questions
1
vote
1
answer
152
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
- 3,446
3
votes
1
answer
192
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a ...
- 3,446
5
votes
2
answers
265
views
Triangle coloring in random graph
Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that ...
- 367
3
votes
1
answer
164
views
making a random uniform hypergraph linear
Let $\mathcal{H}_{n,p,h}=(V,E)$ be a random $h$-uniform hypergraph on $[n]$, sampled according to the usual binomial distribution. We known that with high probability, the number of edges in $\mathcal{...
3
votes
1
answer
159
views
Hyper-degree sequences: How to count them and how to construct hyper-graphs from them?
From an answer to this question I have learned how to ask this question properly.
Consider a $k$-uniform hypergraph on $n$ nodes, i.e. a family of $k$-subsets of $[n]= \{1,2,\dots,n\}$ (the hyperedges)...
- 9,720
3
votes
1
answer
394
views
small hyperworlds ?
The theory of random graphs, after the pioneering classic work of Erdős & Rényi, has come to prominence with many further refinements, most notably the small world theory (Barabási, Watts, etc).
...
- 7,853
2
votes
1
answer
203
views
matchings in hypergraphs
I have been reading Pippenger and Spencer's paper "Asymptotic behavior of the chromatic index for hypergraphs" and they comment that their result is applicable to the family of random k-uniform ...
- 201
5
votes
0
answers
179
views
Small Configurations in Random Hypergraphs
I have a somewhat technical question regarding the distribution of small hypergraphs in randomly chosen hypergraphs. (My hope is that this is something that can be done using standard ideas about ...
- 7,145