# Questions tagged [extremal-graph-theory]

Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.

244 questions
Filter by
Sorted by
Tagged with
16 views

### Homomorphism density of complete bipartite graph via local Sidorenko

Let $0<p<1$ and $G$ be a graphon with edge density $p$ and $\lVert G-p \rVert_\square\leq1.1p.$ Let $K_{ab}$ be a complete bipartite graph with each part's order $a,b.$ Let $t(K_{ab},G)$ be the ...
• 155
48 views

### Cut norm via power trick

Let $G$ be a graph with vertex set $V$ and edge set $E(G)$, define it's $k$'th power trick as a graph $G^k$ with vertex set $V^k$ and for any $x=(x_1,x_2,\dots , x_k), y=(y_1,y_2,\dots , y_k)\in V^k$, ...
• 155
40 views

• 155
36 views

### Does this "linear-approximated" version of Graph Counting Lemma hold?

Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
• 155
318 views

89 views

### Turán number of even cycles with diagonal

Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle. What is known about the Turán ...
• 18.5k
56 views

### Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi: Lemma: For any $\alpha>0$ and a graph $F$, ...
• 281
1 vote
69 views

### Lower bound for the sum of the number of vertices of some subgraphs of a directed graph

Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$. Let $C(V_i)$ be the union of ...
1 vote
69 views

130 views

305 views

### Reference for a topological result

I am reading the short paper due to Erdös and Bollobás "On a Ramsey-Turán type problem", where they obtain a lower bound for the number of edges on an $n$-graph without $K_4$ as a subgraph ...
• 1,543
104 views

### Maximal graphs with a property that is invariant w.r.t. vertex removal

Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$. Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...
• 31.5k
191 views

### Cover a graph with small size complete graphs

Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$:...
• 53
53 views

### Comparing spectral radius of two graphs using the entry of Perron vector

Suppose we have a graph $G$. Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector. Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$. We ...
• 199
244 views

• 419
249 views

• 373
53 views

### A variant of the regularity lemma that depends on the number of vertices

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side. For sets $X \subseteq U$ and $Y \subseteq V$, let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...
• 419
190 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,543
126 views

• 19.3k
452 views

### Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
• 73
264 views

### Intuition on inequality in proving a bound on the sum of squares of degrees of a graph

Given a simple connected graph $G$ with $n$ vertices and $m$ edges, let $d_1, ..., d_n$ denote the degrees of the vertices of the graph. In this very short paper, the author prove the inequality \...
• 652
### $K_4$ or n vertices without triangles
For which minimal $m(n)$ any graph on $m$ vertices contains either a complete subgraph on 4 vertices $K_4$ or $n$-vertices subgraph without triangles? I know a quadratic upper bound $2n^2$, but I am ...