Questions tagged [graph-theory]
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
5,284
questions
-2
votes
0
answers
24
views
What’s the Fractional Shortest Path Problem in a Fractional Graph? [closed]
Fractional Shortest Path Problem in a Fractional Graph
In a traditional graph, each edge between vertices has a weight, typically representing distance, time, or cost. Consider a fractional graph ...
0
votes
0
answers
30
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 183
0
votes
0
answers
16
views
Does Sidorenko's conjecture holds when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 183
1
vote
0
answers
89
views
Can a Feynman graph be an empty set?
I was reading the section about Feynman graphs from the book Renormalization - An Introduction and this question arose. To set the notations, let $p \in \mathbb{N}_{+}$ and, for each $k \in \{1,...,p\}...
- 1,295
0
votes
0
answers
40
views
How to understand a symmetric bounded measurable function as a distribution?
In combinatorics, graphon(symmetric bounded measurable function $W:[0,1]^2\to [0,1]$) is widely studied.
Some researchers view this symmetric bounded measurable function $W:[0,1]^2\to [0,1]$ as a ...
- 183
1
vote
0
answers
53
views
How to understand "sparse graph limits"
For an $n$-vertex graph $G$, we say it is a sparse graph if $e(G)=o(n^2)$. Otherwise if $e(G)=\theta (n^2)$, we say it is a dense graph.
For a sequence of dense graphs $G_1,G_2,\dots,$ we know that it ...
- 183
17
votes
0
answers
241
views
A new basis for chromatic polynomials
Given a graph $G$ on $n$ vertices, its chromatic polynomial $P(G,x)$ is a function that gives the number of proper colorings of G using $x$ colors.
When $P(G,x)$ is written using the basis $\{x, \...
- 171
0
votes
1
answer
85
views
Countable graph with $2^{\aleph_0}$ non-isomorphic induced minors
Let $G=(V,E)$ be a simple, undirected graph. If $S, T\subseteq V$ are disjoint sets, we say that $S,T$ are connected to each other if there are $s\in S, t\in T$ such that $\{s,t\}\in E$. We say a ...
- 47.9k
0
votes
0
answers
63
views
Equivalent statement of Sidorenko's conjecture
Sidorenko's conjecture is a fundamental question in combinatorics and graph theory. Here is the analytic version: A graphon is a bounded measurable symmetric function $W:[0,1]^2\to [0,1]$. For any ...
- 183
0
votes
0
answers
19
views
Minimal bipartite graph density in the log-edge-density version
A graphon is a bounded measurable symmetric function $W:[0,1]^2\to [0,1]$. Let $\mathcal{W}$ denote the set of all graphons. For any $p\in [0,1]$, let $\mathcal{W}_p$ denote the set of all graphons $W$...
- 183
0
votes
1
answer
112
views
Chain of automorphism groups
Let $\mathrm{Aut}(\Gamma)$ be the automorphism group of a graph $\Gamma$. Also suppose that $\mathrm{Cay}(G,S)$ is the Cayley graph of a group $G$ with respect to the generating set $S$. Consider the ...
- 883
1
vote
2
answers
292
views
+100
Lower bound for the size of a family of sets
Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:
$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$
Let $\mathcal{F} = \{A_1 \...
- 816
4
votes
0
answers
61
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
0
votes
1
answer
64
views
Forced monochromatic pairs in graphs
Starting point. Consider the "$V$-graph" on the vertex set $\{1,2,3\}$ and let the edges be $\{1,2\}$ and $\{2,3\}$. This graph is clearly bipartite. It is a trivial observation that ...
- 47.9k
4
votes
2
answers
261
views
Multiplicity of the smallest non-zero Laplacian eigenvalue for tree graphs
How accurate is the following statement: "For tree graphs, the multiplicity of the smallest non-zero eigenvalue $\lambda_2$ of the Laplacian is 1." If not valid, in which cases does it fail ...
- 91