All Questions
Tagged with applications graph-theory
27
questions
0
votes
0
answers
31
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
605
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,014
0
votes
0
answers
532
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
395
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,068
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
732
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.7k
1
vote
1
answer
280
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,075
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
356
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.8k
3
votes
0
answers
779
views
Importance of graph planarity for applications
What is the real-life motivation for studying (or inventing) effective algorithms to check whether or not a graph is planar (which seems to have garnered interest in recent years)? Why is planarity an ...
- 361
10
votes
1
answer
1k
views
Application of Combinatorics/Graph Theory to Organic Chemistry?
Recently, I have been self-teaching graph theory and having an organic chemistry course at school.
When I was learning isomer enumeration I found great resemblance between organic molecules and ...
- 8,656
4
votes
0
answers
719
views
Applications of Prüfer sequence
Reading a book about a graph theory I found out about Prüfer's sequences which converts a labeled tree of $n$ vertices into an array of $n-2$ numbers.
I was actually pretty surprised by this and was ...
- 2,665
4
votes
1
answer
537
views
Graph theory application of homology
I am struggling with the idea of local homology groups and would like to see an example of how to go about finding them in general.
I'm thinking of the most trivial case to apply the theory of local ...
- 291
5
votes
1
answer
171
views
How to draw Congressional districts to mirror the Popular Vote
Let me preface this by saying that I'm not sure whether this is fundamentally a mathematical question or not, but I think it is.
In the United States, the House of Representatives is elected roughly ...
- 10.3k
0
votes
0
answers
248
views
Pascal's Identity and Trees
Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
- 43
8
votes
0
answers
724
views
How is graph theory used to solve problems in number theory?
What are some applications of graph theory in number theory? How can a graph theory approach be useful to solving number theory problems? In general, is graph theory ever useful in making number ...
- 2,231
5
votes
3
answers
2k
views
Does "Big Data" Have a Ramsey Theory Problem?
I'm erring on the side of conservatism asking here rather than MO, as it is possible this is a complex question.
"Big Data" is the Silicon Valley term for the issues surrounding the huge amounts of ...
user452
3
votes
1
answer
1k
views
Graph (or Group) in Astronomy
Is there an application of graph theory (or group theory) in astronomy. If there is, refer me some references.
- 207
8
votes
3
answers
4k
views
Uses of the incidence matrix of a graph
The incidence matrix of a graph is a way to represent the graph. Why go through the trouble of creating this representation of a graph? In other words what are the applications of the incidence matrix ...
- 106k
29
votes
3
answers
2k
views
Exceptional books on real world applications of graph theory.
What are some exceptional graph theory books geared explicitly towards real-world applications?
I would be interested in both general books on the subject (essentially surveys of applied graph theory ...
- 27.2k
2
votes
3
answers
2k
views
Applications of the number of spanning trees in graphs
Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$.
There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to me) ...
- 5,032