What is the Solution to POTW #230 - Oct 25, 2016?

  • MHB
  • Thread starter Euge
  • Start date
  • Tags
    2016
In summary, the conversation discussed the problem in POTW #230 - Oct 25, 2016, which was finding the shortest path between two points in a given maze. This type of problem has many real-world applications and was solved using a graph traversal algorithm called Breadth-First Search (BFS). BFS explores neighboring nodes to find the shortest path and uses a queue data structure for efficiency. However, BFS may not always find the shortest path in certain types of mazes, requiring the use of other algorithms like Dijkstra's.
  • #1
Euge
Gold Member
MHB
POTW Director
2,054
209
Here is this week's POTW:

-----
Show that if $(X,\mathcal{M},\mu)$, $(Y,\mathcal{N},\nu)$ are finite measure spaces, $1 < p < \infty$, and $K$ is a measurable function on $X\times Y$, there is a bounded integral operator $I(K) : \mathscr{L}^p(\nu) \to \mathscr{L}^p(\mu)$ given by

$$I(K)(f) :x \mapsto \int_Y K(x,y)\,f(y)\, d\nu(y)\quad (f\in \mathscr{L}^p(\mu)),$$

provided that the kernel $K$ satisfies the conditions $\sup_x \int_Y \lvert K(x,y)\rvert\, d\nu(y) < \infty$ and $\sup_y \int_X \lvert K(x,y)\rvert \, d\mu(x) < \infty$.
-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
  • #2
No one answered this week's problem. That's ok though, because the problem statement originally had some typos -- they have been corrected. :D You can read my solution below.
Assume the conditions on $K$ hold. Let $\alpha$ be the supremum of all the integrals $\int_Y \lvert K(x,y)\vert\, d\nu(y)$ as $x$ ranges over $X$; similarly define $\beta$ as the supremum of all integrals $\int_X \lvert K(x,y)\vert\, d\mu(x)$ as $y$ ranges over $Y$. Let $q$ be the conjugate exponent of $p$. Given $f\in \mathscr{L}^p$ with $\|f\|_p = 1$,

$$\lvert I(K)f\rvert \le \int_Y \lvert K(x,y)\rvert^{1/q} \lvert K(x,y)\rvert^{1/p}\lvert f(y)\rvert\, d\nu(y) \le \alpha^{1/q}\left(\int_Y \lvert K(x,y)\rvert \lvert f(y)\rvert^p\, d\nu(y)\right)^{1/p},$$

using Hölder's inequality, and by Fubini,

$$\|I(K)f\|_p \le \alpha^{1/q}\left(\int_X\int_Y \lvert K(x,y)\rvert \lvert f(y)\rvert^p\, d\nu(y)\, d\mu(x)\right)^{1/p}
= \alpha^{1/q}\left(\int_Y \lvert f(y)\rvert^p \left[\int_X \lvert K(x,y)\rvert\, d\mu(x)\right] d\nu(y)\right)^{1/p}
\le \alpha^{1/q}\beta^{1/p}\|f\|_p = \alpha^{1/q}\beta^{1/p}$$

As $f$ was arbitrary, $T$ is bounded (by $\alpha^{1/q}\beta^{1/p}$). In fact, as $0 \le \alpha, \beta \le \max\{\alpha,\beta\}$, we may deduce $\|I(K)\| \le \max\{\alpha,\beta\}$.
 

1. What was the problem in POTW #230 - Oct 25, 2016?

The problem in POTW #230 - Oct 25, 2016 was to find the shortest path between two points in a given maze.

2. What is the significance of this problem?

This type of problem is known as a graph theory problem and has many real-world applications, such as finding the shortest route for a delivery truck or optimizing a transportation network.

3. What approach did you use to solve this problem?

I used a graph traversal algorithm known as Breadth-First Search (BFS) to find the shortest path between the starting and ending point in the maze.

4. How does BFS work?

BFS starts at the given starting point and explores all neighboring nodes before moving on to the next level of nodes. This ensures that the shortest path is found before exploring longer paths. It also uses a queue data structure to keep track of the nodes to be explored, ensuring that the algorithm is efficient and doesn't get stuck in a loop.

5. Are there any limitations to this solution?

While BFS is a reliable and efficient algorithm, it may not always find the shortest path in certain types of mazes, such as ones with multiple paths of the same length. In such cases, other graph traversal algorithms, like Dijkstra's algorithm, may be more suitable.

Similar threads

  • Math POTW for Graduate Students
Replies
1
Views
2K
Replies
1
Views
1K
  • Math POTW for Graduate Students
Replies
1
Views
1K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
2K
  • Math POTW for Graduate Students
Replies
1
Views
4K
Back
Top