Questions tagged [infinite-graphs]

The study of graphs with an infinite number of vertices.

38 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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?...
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 ...
48 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 inﬁnite sets $A$ and $B$. Then there exists a bijection $A \to B$. Proof: Let $f: A \to B$ and $g: B \to A$...
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$-...
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 ...
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 ...
40 views

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 ...
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 ...
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/...
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 ...
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-...
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, ...
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 ...
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 ...
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$ ...