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
4
votes
0
answers
116
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
- 211
7
votes
1
answer
410
views
Drawing trees on small number of lines in 2D and 3D
Problem. Given a tree do we need fewer lines in 3D than in 2D in order to draw it straightline and crossing-free?
(Asked 01.10.2016 by Alexander Wolff on page 20 of Volume 1 of the Lviv Scottish Book)...
- 4,535
4
votes
1
answer
887
views
Existence of triangle-free graphs for regular graphs of degree at most n/2
It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to half the number of vertices (...
- 43
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
13
votes
0
answers
741
views
Is there a weak strong regularity lemma?
A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
- 29k
3
votes
1
answer
121
views
The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles.
Clearly, $c(n, 1) = 1$ and it not very hard to ...
- 1,034
2
votes
2
answers
2k
views
Maximum number of edges in bipartite graph without cycles of length 4
Let $ex(n,H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. Let $ex(n,m,H)$ denote the maximum number of edges of a bipartite graph with parts' sizes $m$ ...
- 251
-1
votes
1
answer
94
views
Existence of a graph with strong restrictions
Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:
all nodes but $v$ have full degree $k$ ($v$ having a lower ...
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
4
votes
1
answer
1k
views
What is the minimum diameter of $r$-regular, $k$-connected graphs?
Let $md_r^k(n)$ be the minimum diameter over all $r$-regular, $k$-connected graphs on at least $n$ vertices. (Let us assume $r, k \geq 2$).
Problem: Find lower and upper asymptotic bounds on $md_r^...
- 399
21
votes
4
answers
1k
views
A graph with few edges everywhere
Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue.
Suppose the following two conditions hold:
for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$
for any $...
- 1,359
-3
votes
2
answers
349
views
Concepts of criticality in graph theory
A graph $G=(V,E)$ is said to be vertex-critical if removing a vertex $v\in V$ reduces the chromatic number $\chi(\cdot)$. Edge-criticality is defined in a similar manner. Moreover, $G$ is called ...
- 48.9k
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
9
votes
0
answers
156
views
Minimal number of colours in distinguishing colouring of biconnected graphs
A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...
- 4,535
1
vote
1
answer
137
views
Lower bound construction for the extremal number of $C_{2k}$-free bipartite graph
Suppose $G(V_1 \cup V_2, E)$ is a bipartite graph with parts $|V_1|=n$ and $|V_2|=m.$ What is the best known lower bound construction for the maximum number of edges in $G$ when $G$ does not have a ...
- 389
2
votes
1
answer
239
views
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...
- 393
13
votes
2
answers
870
views
Strongly connected directed graphs with large directed diameter and small undirected diameter?
This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...
- 156k
4
votes
0
answers
143
views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
- 13.2k
6
votes
2
answers
863
views
Minimal graphs of prescribed girth and chromatic number
The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...
- 3,463
9
votes
3
answers
983
views
Number of Geodesic Paths Passing Through a Vertex in an Expander Graph
Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum ...
- 3,626
3
votes
1
answer
179
views
Reference Request: designing a tree of "main roads" in a graph
Let $G = (V, E)$ be an undirected finite connected graph. Let $u$ be a specified vertex of $G$. Then the sum of distances
$$
\sum_{v \in V} d_G(u,v)
$$
is defined. Now we want to decrease this value, ...
- 1,551
3
votes
1
answer
289
views
Graph properties that imply a bounded number of edges
Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a ...
- 1,072
22
votes
2
answers
2k
views
Largest graphs of girth at least 6
Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6.
Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.
...
- 37.7k
9
votes
1
answer
1k
views
Smallest Connected Graph for Given Degree Sequence
For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of non-...
user39815
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
4
votes
1
answer
220
views
Maximal number of perfect matchings that pairwise form a Hamiltonian cycle
Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle.
Question: Is it true that $MH(...
- 3,004
3
votes
2
answers
859
views
Complete k-partite graph covers all K_k of a graph
Suppose that we have a complete graph $G$ of $n$ vertices. What is the minimum number of complete $k$-partite graph (subgraph of $G$) that covers all the complete graph of $k$ vertices of $V(G)$? Are ...
- 356
6
votes
0
answers
108
views
What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3
For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph ...
- 42k
12
votes
1
answer
850
views
How to find or constrain "particularly good" (two-sided) spectral expanders?
I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
- 3,612
4
votes
1
answer
976
views
What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?
Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...
- 1,233
4
votes
1
answer
183
views
Minimal size of the maximal biclique
We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, ...
- 968
5
votes
2
answers
383
views
Extremal graph theory for directed graphs
In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and $t(\...
- 131
7
votes
0
answers
232
views
The smallest order of a 4-chromatic graph of given girth
Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-...
- 537
3
votes
1
answer
2k
views
If many triangles share edges, then some edge is shared by many triangles
Let $G=(V,E)$ be a graph.
Let $t$ denote the number of triangles in the graph, and $x$ denote the number of pairs of distinct triangles that share an edge.
(For example in $K_4$ we have $t=4$ and $x=6$...
- 337
4
votes
0
answers
125
views
Percolation in torus under threshold rule
As part of my graduate research I am currently studying the last section in the paper "Random Majority Percolation" by Balister, Bollobas et al. The paper itself is very complicated but the last two ...
- 41
6
votes
2
answers
349
views
extremal bipartite graph
I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number of ...
- 161
2
votes
1
answer
278
views
Finite limit to the size of an intersecting family of k-sets with no smaller intersecting set?
Suppose we have a family $F$ such that:
For each $A \in F$ we have $|A| = k$
For each $A,B \in F$ we have $A \cap B \neq \emptyset$
If we have $C$ such that for each $A \in F$ we get $C \cap A \neq \...
- 529
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
2
votes
1
answer
291
views
Help on the following extremal problem?
An induced cycle is a cycle that is an induced subgraph of G; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes.
Can anyone please tell me what ...
- 519
2
votes
0
answers
399
views
possible degree sequences for a graph with multiple edges but no loops
Let $G$ be a graph on $n$ vertices. $G$ is allowed to have multiple edges but no loops. The degree sequence of $G$ is the tuple $(d_1,d_2,\ldots,d_n)$ with $d_1\geq d_2 \geq\cdots\geq d_n\geq 0$ ...
- 501
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
5
votes
2
answers
516
views
Vertex expansion of the Hamming graph
Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is
$$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} \right\}.$$...
- 419
10
votes
1
answer
333
views
Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?
In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...
- 1,091
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
1
vote
2
answers
360
views
Tight bound of Turan number for K_{1,t,t}
I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.
The motivation is that we now $ex_2(n,K_{t,t})=O(...
- 281
2
votes
1
answer
356
views
Extremal combinatorics on bipartite graphs
One open question in extremal graph Theory is the so-called Zarankiewicz problem
(see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...
- 1,561
2
votes
1
answer
407
views
On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections
Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...
- 307
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
3
votes
0
answers
97
views
What is the number of independent sets in graph of this type?
Suppose we have a graph $G(V,E)$
What is the number of independent sets in graph of this type?
I have an idea to use reccurence
$$|G|=|G\backslash \{v\}|+|G\backslash n(v)|$$
where $|G|$ is the ...
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