All Questions
Tagged with applications graph-theory
27
questions
0
votes
0
answers
30
views
Application of threshold functions from random graph theory
I would like to know if anyone knows about some applications/models where those threshold functions from random graph theory, defined by
$$
\lim_{n \to \infty} P(\mathbb{G}_{n,p} \in \mathcal{F}) =
...
- 114
8
votes
2
answers
604
views
Longest Path in Path of Exile
Background:
In the popular online video game Path of Exile, there is a skill tree that players can allocate points to as they gain levels. The skill tree is essentially a connected graph where a node ...
- 2,004
0
votes
0
answers
524
views
Application of Graph Theory in Electrical Circuits
I've been learning about electrical circuits, and I can see how Graph Theory naturally lends itself well to problems with circuits.
I was wondering what some examples of applications of Graph Theory ...
- 140
1
vote
1
answer
392
views
What does the Lattice actually means in the Small World Propensity formula?
I am studying small-world networks and I came across the formula of Small World Propensity (reference: https://doi.org/10.1371/journal.pone.0216146.s001). And I am having trouble understanding the ...
- 131
2
votes
1
answer
60
views
Applications of a theorem on certain dense subgraphs?
In my introductory course on graph theory the following statement was proven.
Any finite graph $G$ with at least one edge contains an induced subgraph $H$ such that $\delta(H) > \frac{d(H)}{2}\...
- 3,058
6
votes
0
answers
44
views
Extending a common-neighbor statistic to more than two nodes
first time poster here (happy to edit if I am violating any guidelines, please just let me know) :)
I am curious whether the following formula from this paper by Li and Liang for the probability of an ...
- 61
0
votes
1
answer
166
views
Areas of Applied Combinatorics
I love combinatorics, but do not really want to do pure math exclusively. I like the format of pure math (that is the theorem-proof-theorem-proof format), but would also like what to do research that ...
- 342
2
votes
0
answers
73
views
Real world application of finding all simple paths on a graph
I am currently designing a general purpose graph database. Recently I have started to consider supporting the "find all simple paths between two nodes" operation on the graph. However while there are ...
- 121
2
votes
0
answers
30
views
How to randomly sample a social graph to find paths between at least 20% of profiles?
Given a Graph, where we know
Total number of nodes (~100,000)
Average no of connections per node (~200)
Maximum distance between two nodes (~5)
How many nodes (and its connections) do we have to ...
- 121
2
votes
0
answers
179
views
Applications of Algebraic Topology to urban planning
(Soft question) I was wondering if anybody knows of any applications of Algebraic Topology or Topological Graph Theory to Urban Planning/Public Transportation Planning.
¡Thanks!
- 45
11
votes
1
answer
729
views
What precisely is the Friendship Paradox (and is Wikipedia wrong?)
Friendship paradox is the somewhat well-known statement that "statistically speaking, your friends have more friends than you do".
To my mind, which is surely ignorant of any complexities of social ...
- 12.6k
1
vote
1
answer
279
views
Practical examples/applications of independent sets in hypergraphs?
A hypergraph $H$ is a collection of subsets of a set $V$. And $V$ is called its vertex-set. And those subsets are called its edges (or hyperedges.) And an independent set of $H$ is a subset $I$ of $V$ ...
- 2,085
3
votes
0
answers
30
views
Projection of sparse weighted graph into $\mathbb{Z}$
Problem statement in the title is simplified and this question is actually quite open-ended: I have a sparse undirected simple weighted graph $G$ and need to find an injective function $G \rightarrow \...
1
vote
0
answers
355
views
Handshaking lemma
I'm collecting mathematical facts that can be easily explained to non-mathematicians and that have both "unimportant" and very important applications. For example, Theorema Egregium can be applied to ...
- 155
8
votes
2
answers
453
views
The Mathematics of Symbol Recognition.
I wonder what Mathematics is behind handwriting and symbol recognition.
I was using Detexify just now and it struck me that a distinction could be made between $\varsigma$ (a variant of the Greek ...
- 45.7k