Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
56 views

Does Forcing conjecture equals to assume the host graph is regular?

Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally, $$ t(H, ...
tom jerry's user avatar
  • 349
0 votes
0 answers
45 views

Another version of Sidorenko's conjecture(?)

I would like to ask a question about Sidorenko's conjecture. Here is the background of my question: Quasi-random graphs A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
tom jerry's user avatar
  • 349
3 votes
0 answers
81 views

Can we remove the restriction on a parameter in Talagrand concentration inequality?

Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
Xin Zhang's user avatar
  • 1,190
2 votes
1 answer
80 views

Positive-semidefiniteness of Laplacian of signed graph

Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}\in\{-1,+1\}$. Define the Laplacian matrix as $L:=D-A$ where $D$ is the degree matrix, $D_{ii}=\sum_{j\neq 1}A_{ij}$. my question. If $\...
tony's user avatar
  • 405
0 votes
0 answers
52 views

Does "epsilon-regular" equal to "cut distance less than epsilon"?

Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal? $G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
tom jerry's user avatar
  • 349
1 vote
0 answers
99 views

Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
ABIM's user avatar
  • 5,405
1 vote
0 answers
164 views

Locally "unshortable" paths in graphs

Setup: Consider a connected graph G, with diameter "d". Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
Alexander Chervov's user avatar
3 votes
0 answers
151 views

Smallest dominating set

Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
Zach Hunter's user avatar
  • 3,499
2 votes
2 answers
286 views

Finding an easy example applying the general Lovász local lemma

Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks. General Lovász local lemma: Consider a set $...
Xin Zhang's user avatar
  • 1,190
2 votes
0 answers
91 views

Graphon convergence of uniform weighted graphs

I have a question that I need at some point my research. Suppose that the upper-triangular entries of an $n\times n$ symmetric matrix $A$ are i.i.d. Uniform$(0,1)$. Does the weighted graph with ...
Probabilist's user avatar
5 votes
1 answer
319 views

Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$

Let $G = (V, E)$ be a uniform random graph on $2n$ labeled vertices and let $S \subseteq {V}$ be the set of vertices with degree $\ge n$. Then what happens to $\mathbf{P}(|S|=n)$ as $n \to \infty$? ...
Nikita Gladkov's user avatar
8 votes
1 answer
392 views

What is this Ramsey problem?

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
Zach Hunter's user avatar
  • 3,499
1 vote
0 answers
115 views

Probability of (single) connecting paths in Erdos-Renyi graphs

In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of there ...
Scriddie's user avatar
  • 129
2 votes
1 answer
96 views

Lower bound on the number of balanced graphs

Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs and ...
35T41's user avatar
  • 143
6 votes
0 answers
164 views

Hamilton cycles in random graphs with just enough connectivity

What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
Dmytro Taranovsky's user avatar
6 votes
2 answers
723 views

Threshold function for a graph not being planar

A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property. It is well-known that every ...
W. Paul Liu's user avatar
3 votes
1 answer
163 views

The most pseudorandom subgraph of a dense graph

A bipartite graph $(A,B)$ is $(p, \beta)$-jumbled if for all subsets $A'\subseteq A$ and $B'\subseteq B$ we have that $\left|\mathrm{E}(A',B')-p|A'||B'|\right|\leq \beta \sqrt{|A'||B'|}$. A easy ...
alpmu's user avatar
  • 805
2 votes
1 answer
165 views

Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular ...
Karagounis Z's user avatar
3 votes
0 answers
148 views

Random graph - probability threshold for any linear size set to contain a fixed clique

Let $t\geq 3$ and $0<\varepsilon<1$ be fixed. Denote by $K_t$ the clique on $t$ vertices, and by $G_{n,p}$ the binomial random graph. Question: Is the threshold for the probability that "...
Thomas Lesgourgues's user avatar
1 vote
1 answer
119 views

Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?

We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...
Bernard Vatant's user avatar
2 votes
3 answers
230 views

Random graphs defined by a set of tiles

Related to this question, which I asked at MSE, I'd like to ask this one here: Consider a (large) graph $G$ and its multi-set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the ...
Hans-Peter Stricker's user avatar
1 vote
0 answers
40 views

Eigenvalue bounds of a random graph with a clique

I'm looking into this paper and having some problems proving (ii) of proposition 2.1. I don't quite understand how the lemma is proved. I also read the original paper where the lemma comes from but ...
Yikun Zhong's user avatar
2 votes
0 answers
282 views

Generating a random graph with bounds on degree and diameter

What would be a way to generate a random simple graph with diameter lesser than a given number, and in which there are given lower and upper bounds (bounds being uniform across vertices) on the degree ...
DSM's user avatar
  • 1,216
23 votes
4 answers
979 views

What nodes of a graph should be vaccinated first?

Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node). Choose some random number "K" of nodes which are "infected" initially. So we ...
Alexander Chervov's user avatar
2 votes
1 answer
426 views

Random subgraph properties

Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
lenhhoxung's user avatar
5 votes
0 answers
191 views

Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph

This question is very important for my research, which is why I ask it here. I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
mathlyfe's user avatar
3 votes
1 answer
164 views

making a random uniform hypergraph linear

Let $\mathcal{H}_{n,p,h}=(V,E)$ be a random $h$-uniform hypergraph on $[n]$, sampled according to the usual binomial distribution. We known that with high probability, the number of edges in $\mathcal{...
Thomas Lesgourgues's user avatar
3 votes
1 answer
159 views

Hyper-degree sequences: How to count them and how to construct hyper-graphs from them?

From an answer to this question I have learned how to ask this question properly. Consider a $k$-uniform hypergraph on $n$ nodes, i.e. a family of $k$-subsets of $[n]= \{1,2,\dots,n\}$ (the hyperedges)...
Hans-Peter Stricker's user avatar
3 votes
0 answers
209 views

Two kinds of generating functions

Sorry for a possibly off-the-topic question, but I am afraid to gain the necessary overview to give an answer (supposed the question is not ill-posed) is beyond my capabilities. In the course of ...
Hans-Peter Stricker's user avatar
3 votes
1 answer
138 views

Degree sequences after vertex removals

Consider a graph $G=(V, E)$ with $|V|=n$ vertices. Let $(v_1, \dots, v_n)$ be an ordered list of its vertices. Let $G_i=G[\{v_{i+1}, \dots, v_n\}]$ be the induced subgraph on the last $n-i$ vertices. ...
Jimmy's user avatar
  • 565
186 votes
3 answers
96k views

Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?

QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
user161819's user avatar
11 votes
1 answer
370 views

Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

Is the following lemma a well known result in graph theory? I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
Claus's user avatar
  • 6,917
1 vote
0 answers
140 views

Count shortest path with different lengths in random graph

Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
neverevernever's user avatar
1 vote
1 answer
436 views

Size of minimum cut in random graph

Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) The score of each ...
pi66's user avatar
  • 1,209
2 votes
0 answers
83 views

Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?

$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
Turbo's user avatar
  • 13.9k
3 votes
1 answer
598 views

Asymptotic formula for the number of connected graphs

It can be shown that the set of graphs with $N$ vertices $G_N$ has cardinality: \begin{equation} \lvert G_N \rvert = 2^{N \choose 2} \tag{1} \end{equation} Recently, I wondered how much bigger $\...
Aidan Rocke's user avatar
  • 3,871
1 vote
2 answers
116 views

How to use probability to find a matching in a family of graphs?

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
Henry Zagreb's user avatar
2 votes
2 answers
536 views

Modularity in a graph -- derivation of modularity score

Background I am currently reading "Modularity and community structure in networks" (2006) by Newman [1]. In it, he derives a score for the modularity of a graph ...
ngmir's user avatar
  • 121
3 votes
1 answer
108 views

Expected size of matchings in a cubic graph

Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$? In other ...
LeechLattice's user avatar
  • 9,501
3 votes
1 answer
822 views

Open Problems in Random Graphs [closed]

I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
Henry Zagreb's user avatar
3 votes
1 answer
206 views

Component properties in Euclidean graphs with distance threshold

In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
user929304's user avatar
12 votes
3 answers
1k views

A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
Sam Spiro's user avatar
  • 470
2 votes
1 answer
607 views

Component size distribution in small Erdos-Renyi networks

I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10. I would like to know the probability a random node is in a component of size $m$. It's ...
Joel's user avatar
  • 121
2 votes
0 answers
49 views

Size of the last non-empty $k$-core of a random graph

Given $n$ and $p$ for $G(n,p)$, how to find the distribution of the size of the non-empty $k$-core with largest $k$? In particular, what is the probability (for any $n$ and $p$) that only $c$ ...
Qi Dong's user avatar
  • 21
1 vote
1 answer
188 views

KPZ relation $\chi = 2 \xi -1$ in a random geometric graph

If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
apg's user avatar
  • 640
6 votes
1 answer
341 views

Bounds on degrees of minors obtained by edge contractions of regular graphs

Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...
delete000's user avatar
  • 163
1 vote
1 answer
1k views

An explicit formula for the number of different (non isomorphic) simple graphs with $p$ vertices and $q$ edges

I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it. Trying to ...
Eugen Rožić's user avatar
13 votes
1 answer
409 views

When is the union of a graph and a random permutation thereof connected?

First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...
H A Helfgott's user avatar
  • 20.2k
0 votes
1 answer
1k views

Random graphs- Erdos and Renyi 1959 paper

Please refer to this link. It is Erdos and Renyi's first paper on Random Graphs (1959). I am trying to work through it. I'm struggling with equations (16), (17) and (21). (16) I'm not sure why ...
Curious_Mel's user avatar
0 votes
1 answer
3k views

How to compute the clustering coefficient of a random graph?

How is the clustering coefficient defined for random graphs? For example, a first definition could be calling clustering coefficient of a random graph the expected value of the clustering coefficient ...
John K's user avatar
  • 23