All Questions
19 questions with no upvoted or accepted answers
21
votes
0
answers
441
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 4,535
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
5
votes
0
answers
226
views
Diameter of subset sum graph
We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$.
Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...
- 2,896
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
2
votes
0
answers
190
views
The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$
Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...
- 237
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 ...
- 349
1
vote
0
answers
63
views
Lower bound for the minimum of the maximum frequency of an element - with restrictions
Consider a family $\mathcal{F}$ of non-empty sets, with
$n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$.
It is known that of the $\binom{n}{2}$ ways ...
- 990
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, ...
- 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 ...
- 349
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 ...
- 349
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 ...
- 349
0
votes
0
answers
67
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 ...
- 349
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|\...
- 349
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 ...
- 349
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 ...
- 349