Questions tagged [infinite-graphs]

The study of graphs with an infinite number of vertices.

Filter by
Sorted by
Tagged with
0
votes
1answer
34 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 ...
0
votes
1answer
30 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 ...
0
votes
1answer
22 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?...
2
votes
0answers
24 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 ...
2
votes
1answer
48 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
vote
1answer
79 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 ...
4
votes
4answers
127 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 ...
1
vote
0answers
71 views

Finite Unions of Dendrites

I will ask the main question first, and then give the motivation for this one! The question is a bit specific, but seems to be the most general question to ask after handling some obvious ...
0
votes
1answer
48 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
vote
0answers
31 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 $...
2
votes
2answers
126 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 ...
1
vote
2answers
68 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 ...
2
votes
1answer
40 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 ...
4
votes
3answers
65 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 ...
1
vote
1answer
29 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 ...
1
vote
0answers
30 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 ...
15
votes
1answer
448 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$...
0
votes
1answer
126 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$-...
3
votes
1answer
155 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 ...
1
vote
0answers
43 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 ...
0
votes
1answer
40 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_{\...
0
votes
1answer
223 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 ...
3
votes
1answer
579 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 ...
1
vote
3answers
104 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 ...
3
votes
0answers
480 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 $...
1
vote
2answers
160 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 ...
0
votes
1answer
81 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 ...
2
votes
2answers
318 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/...
4
votes
2answers
359 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 ...
2
votes
1answer
72 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-...
-1
votes
1answer
713 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
1answer
157 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 ...
-2
votes
1answer
80 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
vote
1answer
31 views

Clarification from a proof that a certain type of graph can be endowed with a group operation

I need some help sorting out a construction of a group out of the vertices of a digraph with a certain property. I'll just throw some definitions here first... Definitions. An alphabet $A$ ...
1
vote
1answer
462 views

Example of infinite graph

First of all, I review some terms and notations. Let set of all ends of graph $G$ be $\Omega(G)$. For every end $\omega$ and every finite set $S\subseteq V(G)$, there is a unique component $C(S, \...
7
votes
1answer
180 views

Graphs with uncountably many vertices

Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
24
votes
4answers
696 views

Is this graph connected

Define the following graph on the vertex set ${\mathbb N}_{\geq1}\>$: Two numbers $a$, $b\in {\mathbb N}_{\geq1}$ are connected by an edge (written $a \ \mathcal{R} \ b)$ if and only if $a+b \ | \...
6
votes
1answer
142 views

Killer Tree! (one of my old questions)

There is a problem that killed me! but I couldn't solve it: We have a tree graph witch its structure is what is on image. Proof that there is no reduplicative numbers in each line.