Questions tagged [extremal-graph-theory]
Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.
253 questions
1
vote
1
answer
88
views
Bounds on the number of proper 3-colorings of cubic graphs
Are there known bounds on the number of proper 3-colorings of a 3-regular in terms of vertex count?
- 83
1
vote
2
answers
75
views
The edit distance from a large complete $p$-partite graph to the Turán graph
Let $K=K(V_1,V_2,\cdots,V_p)$ be a $p$-partite complete graph on $n$ vertices and $T_p(n)$ be the Turán graph.
Show that: if $e(K)\geq e(T_r(n))-t$ then $$\sum_{k=1}^p\left(|V_k|-\frac{n}{p}\right)^2\...
- 113
1
vote
2
answers
205
views
Extremal density of a graph without a non-backtracking $2k$-cycle
The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form
$$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$
while the ...
- 1,389
1
vote
1
answer
182
views
Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$
An oriented graph is a digraph without any self-loops, multiple arcs, or 2-cycles. What is the smallest minimum outdegree of an oriented graph on $n$ vertices that ensures there will always be a cycle ...
1
vote
0
answers
142
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
1
vote
0
answers
107
views
Turán number of even cycles with diagonal
Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle.
What is known about the Turán ...
- 19.1k
1
vote
0
answers
74
views
Graph removal lemma
The graph removal lemma says that for any graph $H$ and any $\epsilon>0$, there is a $\delta>0$ such that any $n$-vertex graph which contains at most $\delta n^{v(H)}$ copies of $H$ can be made $...
- 373
1
vote
0
answers
79
views
Partitioning of a set family that avoids small intersections
Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
- 135
1
vote
0
answers
22
views
Topology of densest graphs whose optimal $3D$-matching can be calculated efficiently
let $A=\lbrace a_1,\,\dots,\,a_k\rbrace $ and $B=\lbrace b_1,\,\dots,\,b_{2k}\rbrace,\ A\cap B=\emptyset$ be be a partition of a graph's vertex set $V$, i.e. $V\,=\,A\cup B$.
Question:
has $G:=\...
- 13.2k
1
vote
1
answer
147
views
Connected sets with a large boundary in a privileged set
Let $G=(V,E)$ be a connected, undirected graph. Define the boundary $\partial S$ of a set $S\subset V$ to be the set of all $v\notin S$ joined to $S$ by an edge, i.e.
$$\partial S = \{v\not \in S: \...
- 20.2k
1
vote
1
answer
139
views
Graph with two edge-disjoint Hamiltonian paths between the same vertex-pair
Provided existence, what is the smallest graph $G(V,E)$ with two edge-disjoint Hamiltonian paths between $u$ and $v;\ \lbrace u,v\rbrace\subset V$?
- 13.2k
1
vote
0
answers
78
views
Expected value of the difference of the Hadwiger number and the chromatic number
If $G$ is a finite, simple, undirected graph, its Hadwiger number $\eta(G)$ is the maximum integer $n$ such that $K_n$ is a minor of $G$. Given any integer $k>0$ let $E_k$ be the expected value of ...
- 48.9k
1
vote
0
answers
123
views
Number of maximum matchings in bipartite graphs of positive surplus
Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \...
- 5,590
1
vote
0
answers
53
views
At what aspect ratio does the Ruzsa-Szemeredi Theorem begin?
One of the many equivalent phrasings of the Ruzsa-Szemeredi theorem is as follows. Suppose one has a three-layered $n$-node graph $G = (V=L_1 \cup L_2 \cup L_3, E)$, and one can partition $E$ into ...
- 1,389
1
vote
0
answers
62
views
Cut norm and biclique gap?
Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\...
- 13.9k
1
vote
0
answers
54
views
Constructing graphs from subsets of a minimal alphabet
From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that ...
- 13.4k
1
vote
1
answer
299
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
- 11
1
vote
0
answers
131
views
What are constructions for induced $C_5$-free graphs?
During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...
- 19.1k
1
vote
0
answers
324
views
graphs with maximal number of paths of given length
Hi,
For a given number of edges, the non directed graph which maximises the number of paths of length 2 is the quasi-star or the quasi-complete graph.
Does anyone know :
1- what is the non directed ...
- 11
0
votes
1
answer
398
views
Forbidden Tripartite Graphs
I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...
- 1,129
0
votes
2
answers
309
views
Reference for a topological result
I am reading the short paper due to Erdös and Bollobás "On a Ramsey-Turán type problem", where they obtain a lower bound for the number of edges on an $n$-graph without $K_4$ as a subgraph ...
- 1,561
0
votes
1
answer
1k
views
Vertex cover of regular graph
(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...
user76479
0
votes
1
answer
814
views
Edge-disjoint cycles in graphs
Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...
- 903
0
votes
1
answer
143
views
A general Turan-like question
Thinking of an edge as of a $2$-clique, it's natural to consider a slightly more general question than Turan considered in his celebrated theorem: given $r \le k \le n$, what is the maximal possible ...
0
votes
1
answer
152
views
Intersection property of Szemerédi's regularity condition
We adopt common notations in the study of Szemerédi's regularity lemma and only focus on simple graph $G(V,E)$. For any two disjoint vertex sets $A,B\subset V$, we say the pair $(A,B)$ is $\varepsilon-...
- 139
0
votes
1
answer
341
views
Looking for source: Max num of edges of graph with given number of vertices and given girth
In a paper I am reading, the author states:
"It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
He says that a proof can be found on Extremal ...
- 193
0
votes
1
answer
424
views
Reference for Turan Density
I am working a 3-graph problem. I convert it to calculate Turan density, that is $lim_{n\to \infty}\frac{ex_3(n,F)}{\binom{n}{3}}$, where F is a3-graph. I'd like to know are there some methods and ...
- 281
0
votes
1
answer
83
views
Making graphs isomorphic with edge additions/removals
Consider simple graphs on the same vertex set $[n]$. For two graphs $G, H$, let $d(G, H) = \min_{H' \sim H} |E(G) \triangle E(H')|$ — the smallest number of edge additions/removals needed to make $G$ ...
- 5,590
0
votes
1
answer
66
views
Matching book thickness of the wheel graph $W_n$
In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
- 767
0
votes
1
answer
118
views
Matching book embedding of Cartesian products of graphs
In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...
- 767
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
0
votes
0
answers
55
views
Comparing spectral radius of two graphs using the entry of Perron vector
Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...
- 199
0
votes
0
answers
148
views
Szemeredi's regularity lemma for countably infinite graphs?
Consider the following version of Szemeredi's regularity lemma found in the Fox and Lovasz paper, "A tight lower bound for Szemeredi's regularity lemma", arXiv: 1403.1768v1 [math.CO] 7 Mar ...
- 6,132
0
votes
0
answers
253
views
What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?
The question is in the title. Szemerédi's Regularity Lemma is the following (according to the Wikipedia entry):
For every $\epsilon \gt 0$ and positive integer $m$ there exists an integer $M$ such ...
- 6,132
0
votes
0
answers
23
views
Does a connected $F_k$-free graph of order $n$ with the maximum singless Laplacian spectral radius belong to $Ex(n,F_k)$?
Let $G$ be a connected $F_k$-free graph of order $n$ with the maximum singless Laplacian spectral radius. Is $G\in Ex(n,F_k)$?
Here, $Ex(n,H)$ denotes the set of $H$-free graphs of order $n$ with $ex(...
- 1,182
0
votes
0
answers
70
views
(Weakly) connected sets with large (out-)boundary
Let $\Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every ...
- 20.2k
0
votes
0
answers
102
views
4-cycles vs eigenvalue information on quasi-random graphs
My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...
- 1,561
0
votes
0
answers
91
views
Properties of the collection of maximal independent sets of a graph
Let $G$ be a graph and define
$\mathscr{I}(G) = \{S \subset V(G)| S$ is a maximal indepedent set of $ G\}$
1. What is known about $\mathscr{I}(G)$?
What are some of the properties of $\mathscr{I}(G)...
- 1,034
0
votes
0
answers
153
views
A Non-trivial intersecting set system problem
Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$.
What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are $$\mbox{ subsets }L_1,L_2,\...
user94040
0
votes
0
answers
47
views
Possible Number of Repetation of a Submatrix
Notation:
$H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
- 267
0
votes
1
answer
431
views
Efficient isomorphic subgraph matching with similarity scores
I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
- 223