All Questions
Tagged with random-graphs extremal-graph-theory
11 questions
0
votes
0
answers
55
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 349
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 349
0
votes
0
answers
52
views
Does "epsilon-regular" equal to "cut distance less than epsilon"?
Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal?
$G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
- 349
4
votes
1
answer
216
views
Quasi-random vs pseudo-random graphs
My question is somehow concerning terminology on extremal graph theory.
Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
- 1,561
2
votes
0
answers
36
views
Is homomorphism density of partially labeled graph continuous with respect to cut metric
Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
- 371
4
votes
3
answers
430
views
How to show that random graphs cannot be embedded with short edges
For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio
$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
- 9,720
0
votes
0
answers
101
views
4-cycles vs eigenvalue information on quasi-random graphs
My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...
- 1,561
4
votes
0
answers
82
views
Expected number of bridges in a random subgraph
I am researching connectivity in random subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
- 175
2
votes
1
answer
237
views
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...
- 393
0
votes
1
answer
1k
views
Vertex cover of regular graph
(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...
user76479
2
votes
2
answers
1k
views
Random graphs require O(n log(n)) edges until they are almost certainly fully connected - what are more concrete boundaries ?
As far as I understand my literature, the probability of a random graph being fully connected tends toward one as the number of edges approaches a value of size $O(n \log(n))$
The way I read this, ...
- 21