1
$\begingroup$

The following question is loosely based on the friendship paradox.

Let $G=(V,E)$ be a simple, undirected graph. For $v\in V$, we let the neighborhood of $v$ be $N(v) = \big\{w\in V:\{v,w\}\in E\big\}$ and the degree is defined by $\newcommand{\deg}{\text{deg}}\deg(v)=|N(v)|$. Moreover, for $v\in V$ we define the set of its popular neighbors by $\newcommand{\Pop}{\text{Pop}}\Pop(v) = \{p\in N(v): \deg(p)>\deg(v)\}$.

Finally, we say $v\in V$ is shy if $|\Pop(v)|>|N(v)\setminus \Pop(v)|$.

We call a set $A\subseteq\mathbb{N}$ large if $\lim\inf_{n\to\infty}\frac{|A\cap\{1,\ldots,n+1\}|}{n+1} = 1$.

Question. Is there a graph on $\mathbb{N}$ such that every vertex has finite degree, and the collection of shy vertices is large?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
5
$\begingroup$

All vertices can be shy. You may add edges to your graph recursively, on $n$-th step fixing all edges from $1,2,\ldots,n$ and possibly some other (finitely many) edges, so that $1,2,\ldots,n$ already have more than a half popular neighbors. There are no problems to perform each, say, $n$-th step: you simply add many edges from $n$ and many-many edges from its new neighbors.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Quite remarkable that all vertices can be shy, thanks for this example! $\endgroup$ Commented Mar 8, 2024 at 21:02
  • 2
    $\begingroup$ Concretely, let the vertices be finite sequences $(a_1,a_2,\dots,a_n)$ with $a_i\in\{1,2,\dots,i\}$ and make $(a_1,\dots,a_n)$ adjacent to $(a_1,\dots,a_n,a_{n+1})$. $\endgroup$ Commented Mar 12, 2024 at 2:45
  • $\begingroup$ @bof ah, a graded tree with every vertex on the $n$-the level having $n$ children $\endgroup$ Commented Mar 12, 2024 at 5:28
4
$\begingroup$

In a star graph, all but one vertex is shy, so a simple construction is to build a star graph from $\{1,\ldots,4\}$, another from $\{5,\ldots,12\}$, etc., doubling the size each time.

Improve this answer
$\endgroup$
3
$\begingroup$

Take any locally finite countable graph with infinitely many shy vertices, e.g., the disjoint union of $\aleph_0$ copies of $K_{1,2}$. Identify the vertex set with $\mathbb N$ in such a way that the set of non-shy vertices is identified with a set of density zero.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.