All Questions
16 questions with no upvoted or accepted answers
11
votes
0
answers
195
views
Number of triangle-free graphs with prescribed number of edges
This question is posted from StackExchange since it received no answer there.
Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
- 384
4
votes
0
answers
113
views
What properties do graphs avoiding large regular subgraphs have?
Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
- 557
4
votes
0
answers
104
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...
- 3,446
3
votes
0
answers
70
views
Boundary differences in two graphs
Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
- 20.2k
3
votes
0
answers
66
views
An extremal problem in directed path systems
The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$:
What is the asymptotically maximum $L = L(n)$ such that ...
- 1,389
1
vote
0
answers
141
views
Specific regularity in bipartite graphs
Let $G(A,B)$ be a bipartite graph with $|A| = |B| = n$, where $n$ is sufficiently large(thus, $o(n)/n,o(n^2)/n^2\ll 1$). The edge density of $G$ is $d = \frac{e(A,B)}{n^2}$, where $e(A,B)$ denotes the ...
- 359
1
vote
0
answers
63
views
Is there any other norms besides cut norm defined on graphon?
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 359
0
votes
0
answers
57
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, ...
- 359
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 ...
- 359
0
votes
0
answers
51
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 359
0
votes
0
answers
67
views
Does Sidorenko's conjecture hold when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 359
0
votes
0
answers
68
views
Proving we can minimize the number of crossings by having a planar embedding of $K_{2,2}$ encircle another out of any 2 such embeddings
Say that we draw a graph in the following way: we first draw $n$ planar embeddings of $K_{2,2}$ (that is, we first draw $n$ quadrilaterals) such there are no edges which cross. Then for each of the $...
- 1
0
votes
0
answers
43
views
Locally uniformly convexity in kernels (generalized definition of graphon) with cut norm
Let $\mathcal{W}$ denote the space of all bounded symmetric measurable functions
$W : [0, 1]^2 \rightarrow \mathbb{R}.$ For any $W\in\mathcal{W}$ we say it is a kernel and define its cut norm $\lVert ...
- 359
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|\...
- 359
0
votes
0
answers
49
views
Property of edge-vertex transitive graphs
Recently I am reading a paper (https://arxiv.org/abs/1504.00858) with respect to edge-vertex transitive graphs. What is the property of the graph that is edge transitive and vertex transitive? I know ...
- 359
0
votes
0
answers
39
views
Does this "linear-approximated" version of Graph Counting Lemma hold?
Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...
- 359