Questions tagged [infinite-graphs]
The study of graphs with an infinite number of vertices.
55
questions
0
votes
1
answer
27
views
Example of a locally finite graph without a uniform degree bound
We call an infinite graph locally finite if every vertex of it is of finite degree. A locally finite graph is said to have a uniform degree bound if the degree of every vertex of it is bounded by some ...
0
votes
1
answer
39
views
Finding an isomorphism between an infinite tree and a subgraph of $\mathbb{Z}^3$
I was wondering if there exists a construction of an infinite tree, with some properties, that is isomorphic to subgraph of $\mathbb{Z}^3$.
Notation
Let $\Gamma_n$ denote the tree's vertices at ...
- 1,956
3
votes
1
answer
96
views
Infinite core graphs
Let $G$ be an infinite graph (directed, loops okay, no multi-edges, so essentially a set with a binary relation). $G$ is called core if every one of its endomorphisms is surjective. Does this ever ...
- 1,193
3
votes
0
answers
88
views
Compactness argument for countable subgraphs and beyond
I am interested whether there exists a certain generalization of so-called compactness argument in graph theory.
First let me define what I mean by "compactness argument"
Let $G = (V, E)$ be ...
- 129
1
vote
0
answers
35
views
Vertex sets separated only by infinitely many vertices imply an infinite number of disjoint paths between them.
In Reinhard Diestel's book "Graph Theory" (5th ed.) there is a chapter on infinite graphs (chapter 8).
In that chapter Diestel states the following fact related to Menger's Theorem:
...
- 11
1
vote
0
answers
34
views
Infinite game (Ehrenfeucht-Fraïssé?) for Linear Temporal Logics
Imagine we have two LTL formulae: A and B. I would like to prove whether they are equivalent or not (the formulae can have the "Globally" operator, so the game is infinite).
To do so I have ...
- 141
3
votes
0
answers
114
views
Is there a locally finite tree having every other locally finite tree as a subgraph?
Is there a locally finite tree $T$ such that any locally finite tree is isomorphic to a subgraph of $T$?
- 39
1
vote
2
answers
41
views
Differentiating condition for two infinite graphs
From the tiling of $\mathbb{R}^2$ with squares I get an infinite graph where each node has 4 neighbors.
I can create an infinite tree by attaching 4 nodes to a root node and then keep attaching 3 new ...
- 549
1
vote
0
answers
352
views
Infinite recursive graphs and different ways to build them
Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications.
They can be identified with binary relations, in other words as elements of the power set ...
- 341
2
votes
1
answer
66
views
Monomorphisms Between Infinite Graphs
I'm really curious about this question:
Let $G(V_G,E_G)$ and $H(V_H,E_H)$ be infinite (infinite!, not finite) graphs, such that $$|V_G|=|V_H|,$$ and let $f$, $g$ be functions $f: G\rightarrow H$, $g: ...
- 1,461
0
votes
0
answers
64
views
Brooks' theorem in the infinite
Let $G=(V;E)$ be an infinite graph, with $|V|$ an uncountable cardinal. Suppose that the maximum degree of any $v \in V$ is $\kappa$, where $\kappa \leq |V|$ is an infinite cardinal. Does it follow ...
user631464
2
votes
1
answer
42
views
A new language construction
I'm interested if the following language construction was studied. Let $\Sigma$ be an alphabet and $\Sigma^*$ is the set of all words over $\Sigma$. Consider a directed graph $G=\langle\Sigma^*,E\...
2
votes
1
answer
42
views
Does every infinite graph contain a maximal clique?
The original problem is stated in terms of the tolerance relation (reflexive and symmetric, but not necessarily transitive): Is every tolerance subset contained in a maximal tolerance subset?
For a ...
- 23
0
votes
1
answer
48
views
Determining set and Automorphism group of a graph
Let $G$ be a simple graph. A set $S\subset V(G)$ is said to be determining set of $G$, if for any two Automorphisms $f,g \in Aut(G)$ whenever $f(s)=g(s)$ for all $s\in S$, then $f=g$. That is, an ...
- 572
2
votes
1
answer
62
views
Finite automorphism group of a graph
Let $G$ be a simple graph and $Aut(G)$ denotes the automorphism group. Then prove or disprove,
Suppose $Aut(G)$ and $diam(G)$ are finite for a graph $G$. Then $|V(G)|$ is finite.
I know $Aut(G)$ ...
- 572
2
votes
1
answer
65
views
Eccentricity in infinite tournaments
Definitions. A tournament is an oriented complete graph, that is, it's what you get by taking a (finite or infinite) complete graph and assigning a unique direction to each edge. If $T$ is a ...
- 70.1k
4
votes
2
answers
216
views
If all subgraphs of two graphs are pairwise isomorphic, are the graphs themselves isomorphic?
For two graphs $G,H$ let's write $G\cong H$ if they are isomorphic.
Let's denote the set of all subgraphs of $G$ by $\mathcal S(G)$. Note that $G\in \mathcal S(G)$ and there can be elements $a,b\in \...
- 2,785
0
votes
1
answer
80
views
Is there a correspondence between different hyperbolic automorphisms of a regular tree?
First, recall that a regular tree $\mathcal{T}_n$ ($n>1$), is an infinite tree in which every vertex has valency $n$. It is known that the automorphisms of a regular tree can be classified into ...
- 471
0
votes
1
answer
136
views
How do I apply the infinite Ramsey theorem to graph theory?
The infinite Ramsey theorem reads as such:
Theorem. Let $X$ be some infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists ...
- 2,785
0
votes
1
answer
70
views
The minor relation on infinite graphs. [closed]
The minor relation is defined in 1.7, GTM173.
The question is from the exercise 1.24
We already know that the minor relation defines a partial ordering on finite graphs.
Is it true for infinite graphs?...
- 317
2
votes
0
answers
33
views
Can the (infinite) graph of a tiling of the plane have no two vertices of the same degree?
I mean for each region to have three or more edges in its boundary. If there's a term for that I'd appreciate a comment as to the term. Another way to state this requirement is that the graph not have ...
- 6,647
2
votes
1
answer
61
views
How to think of formal derivation $\Gamma \vdash \phi$ in terms of trees/graphs?
According to my text, a finite set of formulas $\Gamma$ in a given language $L$ is derivable, denoted $\vdash \Gamma$, if $\Gamma$ belongs to the least collection of finite sets of formulas, denoted $...
- 1,829
1
vote
1
answer
497
views
Does Kőnig's theorem hold for infinite bipartite graphs?
Kőnig's theorem states that in a bipartite graph the size of the maximal matching equals the size of the minimal vertex cover.
I learned it as an equivalence to Hall's theorem and we proved it using ...
- 50
4
votes
4
answers
264
views
Visual example of an infinite planar graph with degree sequence $(4^4,6^\infty)$
After reading some graph theory and talking with experts, I was intrigued. I would like to construct and visualise an infinite planar graph with degree sequence:
$$D=(4^4,6^\infty)$$
where the ...
- 725
6
votes
1
answer
379
views
Finite Unions of Dendrites [closed]
The question is a bit specific, but seems to be the most general question to ask after handling some obvious counterexamples.
Initially, I was wondering the following. Let $X$ be a one-dimensional ...
- 601
0
votes
1
answer
66
views
Is there a name for graphs with this property?
The property of the graph is the following: it's countable, undirected, simple, and for any infinite subset of vertices there are two vertices connected(by infinite Ramsey theorem this is in fact ...
- 1,251
1
vote
0
answers
32
views
non-$n$-colorability of an infinite graph and generic partitions of the vertices
I have an infinite graph $G$ and a natural number $n$, and I am interested in the property of $n$-colorability of $G$. I have the naive idea that
(1) if almost every partition of the vertices of $...
- 7,230
2
votes
2
answers
194
views
Does every infinite connected graph contain a ray?
I read a proof that every infinite, connected, locally finite graph contains a ray, and the proof relies on the graph being locally finite. I didn't want to assume that the lack of that condition made ...
- 31
1
vote
2
answers
143
views
Why does the graph of $y=\frac{\tan(x)/\sin(x)}{\cos(x)}$ have minima at multiples of $\pi$?
I was just messing around is Desmos and plotted the graph of $$y=\frac{\frac{\tan(x)}{\sin(x)}}{\cos(x)}$$ and I realised that all the minimum points on the graph were multiples of $\pi$. Could ...
- 166
2
votes
1
answer
65
views
Is this proposition a sufficient condition for a countably infinite simple-digraph to be a polytree? If so is it also a necessary condition?
If any countably infinite simple digraph $G$ is such that every weakly connected, spanning subgraph of $G$ is equal to $G$ then must $G$ always be a polytree (an orientation of an undirected tree ...
- 487
4
votes
3
answers
95
views
What does $\lim\limits_{x \to \infty} f'(x)=3$ mean?
What I did was to see that the function is behaving as a straight line with gradient $3$ at infinity which implies that the function has an oblique asymptote as $x \to \infty$ but my testing portal ...
- 343
2
votes
1
answer
56
views
Unbounded, Repeated Figures in Non-periodic Tilings
I was just wondering something about non-periodic tilings (of the plane, though I imagine the dimension is irrelevant for finite dimensions; would be interesting if it wasn't!).
I assume we know what ...
- 601
1
vote
0
answers
31
views
How to find a minimal planar covering of a graph
Every graph has a planar covering graph. In particular, the Universal cover, being a tree, will be planar.
How do we find a minimal planar covering $P$ graph of a graph $G$? By minimal, I mean that ...
- 9,520
19
votes
1
answer
797
views
Cantor-Bernstein-Schröder Theorem: small proof using Graph Theory, is this correct?
The theorem:
Suppose there exist injective functions $A \to B$ and $B \to A$ between two infinite sets $A$ and $B$. Then there exists a bijection $A \to B$.
Proof:
Let $f: A \to B$ and $g: B \to A$...
- 1,097
0
votes
1
answer
358
views
How does colorability work in infinite (countable and uncountable) graphs?
Some background:
I know that for finite graphs, iff a graph has no odd cycle (i.e. it is bipartite), it can be $2$-colored. Similarly, a graph without $K_5$ or $K_{3,3}$ is planar, so it can be $4$-...
- 25.9k
3
votes
1
answer
198
views
Hairy Points in Infinite Graphs (and Peano Continua)
I may have to throw this over to overflow, but I figured I would try here, first. This is a question in continuum theory, but it reduces to a combinatorial/graph-theoretical question. I am highly ...
- 601
1
vote
0
answers
72
views
Infinite Perfect Graphs
A graph $G$ is perfect if every induced subgraph $H$ of $G$ can be coloured with $k$ colours, where $k$ is the size of a largest clique in $H$.
The Perfect Graph Theorem (conjectured by Berge and ...
- 1,345
0
votes
1
answer
46
views
Countable subtrees with given order
Let $T$ be a tree. Let $T^0=T$. For an ordinal $\xi=\eta+1$ we define $T^\xi$ to be the complement of the set of all maximal elements of $T^\eta$. For a limit ordinal $\xi$ we set $T^\xi = \bigcap_{\...
- 15.3k
0
votes
1
answer
293
views
Hamilton Cycle Theorem?!
I've come across this link, where the author states: "Hamilton Cycle Theorem fails for infinite graphs unless ..."
Please help me on this, what does he mean by "Hamilton Cycle Theorem"? I studied a ...
- 196
6
votes
1
answer
1k
views
There exists no zero-order or first-order theory for connected graphs
Prove that no zero-order theory (i.e. propositional calculus, without quantification) or first-order theory can describe the "connected graph" (i.e. from any point one can reach each other point in ...
- 2,950
1
vote
3
answers
176
views
Given a path between 2 vertices of a graph, there is only a finite number of vertices in the path?
Let us have a weighted graph $G=(V,E)$ with set of vertices $V$ and set of edges $E$, with a function $E\to V\times V$, a weight function $w:E\to\mathbb{R}_{>0}$ etc.
Take the topological ...
- 871
3
votes
0
answers
696
views
Is this proof of the four color theorem for infinite graphs legit?
So you got an infinite planar graph $G$. I will prove that it is four colorable.
So, construct an infinite number of statements about graphs:
The first is "is four colorable"
Next, for each vertex $...
- 9,520
2
votes
2
answers
195
views
Is it possible to construct the Rado Graph as a countably infinite graph with non-constant edge probabilities?
Let's say we have a countably infinite set $V$ of vertices and a map $f:V\times{V}\to{(0,1)}$ that assigns to each pair $(i,j)$ of vertices an edge with probability $f(i,j) = p$. I believe that if ...
- 193
0
votes
1
answer
103
views
Probability that a random graph on countably many vertices is connected
Fix $0 < p < 1$ and let $G$ be a random graph on elements $\mathbb{N}$ where for $n,m \in \mathbb{N}$, the probability that there is an edge between $n$ and $m$ will $p$. What is the probability ...
- 750
2
votes
2
answers
491
views
Confusion between spectral radius of matrix and spectral radius of the operator
The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of https://en.wikipedia.org/wiki/...
- 143
4
votes
2
answers
517
views
Labelings of infinite directed acyclic graphs
Let $G=(V,E)$ be a countably infinite directed acyclic graph and $L$ be a finite set of vertex labels. The number $\left|V\right|$ of vertices is countable infinity and some vertices may have an ...
- 63
2
votes
1
answer
77
views
How to computably reduce the number of colors in (infinite) Ramsey's theorem
Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a 3-...
- 7,230
-1
votes
1
answer
1k
views
Is there infinite number between two integers?
With more specific saying,
if there is a function that is in continuum from a to b, a and b are real numbers, and bijective to its range, is the number of the function's range infinite?
If it is, ...
5
votes
1
answer
228
views
Why is it so difficult to obtain the spectral properties related to infinite matrices, especially when they are not symmetric?
I believe most of the spectral theory is revolving around the bounded self-adjoint linear operators being analogous to real symmetric infinite matrices. Whereas, there are cases when the matrices are ...
- 143
-2
votes
1
answer
84
views
A Question Regarding Representing $\mathscr P$($\omega$) as a Digraph and CH
It is well known that one can represent sets as digraphs. What is the proper digraph representation of $\mathscr P$($\omega$)? I ask this because $\mathscr P$($\omega$) is $\Pi_1$ in the Levy ...
- 1,185