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.
250
questions
0
votes
0
answers
51
views
Proving we can minimize the number of crossings by having a planar embedding of $K_{2,2}$ encircle another out of any 2 such embeddings
Say that we draw a graph in the following way: we first draw $n$ planar embeddings of $K_{2,2}$ (that is, we first draw $n$ quadrilaterals) such there are no edges which cross. Then for each of the $...
- 1
2
votes
0
answers
40
views
On planar graphs with specific spanning tree count and poly number of vertices
Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 13.8k
1
vote
0
answers
53
views
Is there any other norms besides cut norm defined on graphon?
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 163
1
vote
1
answer
131
views
Covering a bounded degree graph with subgraphs of bounded sizes
Let $G$ be a connected graph on $n$ vertices with maximum degree $\Delta \ge 2$. Let $\mathcal G = \{G_1,G_2,\ldots\}$ be a collection of subgraphs of $G$ such that every edge of $G$ is contained in ...
- 237
0
votes
0
answers
39
views
Locally uniformly convexity in kernels (generalized definition of graphon) with cut norm
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 163
0
votes
0
answers
50
views
Dense set in the tensor power trick of a graphon
Let $W$ be a graphon and $W^k$ be its $k$'th tensor power with sufficient large integer $k$. If there exist a vertex set $V$ of $W^k$ such that all but at most 0.99 of vertices that adjoint with $V$ ...
- 163
0
votes
0
answers
24
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 ...
- 163
0
votes
0
answers
50
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$, ...
- 163
0
votes
0
answers
44
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|\...
- 163
0
votes
0
answers
38
views
Property of edge-vertex transitive graphs
Recently I am reading a paper (https://arxiv.org/abs/1504.00858) with respect to edge-vertex transitive graphs. What is the property of the graph that is edge transitive and vertex transitive? I know ...
- 163
3
votes
1
answer
140
views
Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?
Does the following holds?
For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as ...
- 163
0
votes
0
answers
29
views
Does there exist a Graph Counting Lemma in the Cut density condition?
Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...
- 163
0
votes
0
answers
37
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 ...
- 163
4
votes
1
answer
329
views
A question related to "Locally Sidorenko" type problem
Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant.
Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...
- 163
3
votes
1
answer
69
views
Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?
I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...
