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
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
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 ...
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
2
votes
1
answer
2k
views
The maximum number of edges in an even-cycle-free graph with $n$ vertices
Problem
Given any positive integer $n$, what is the maximum number of edges in an even-cycle-free graph with $n$ vertices?
Is the above problem an unsolved problem in extremal graph theory? Are there ...
- 1,997
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
-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
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
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
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
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
6
votes
0
answers
76
views
Cage graphs and even cycles
Let $G$ be a $(\nu,g)$-cage graph of degree $\nu$ with girth $g$ and $n=n(\nu,g)$ vertices.
Based on the known examples, I am wondering if the following can be proved/disproved:
Is it true that ...
- 13.4k
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 ...
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
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
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
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
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
2
votes
1
answer
252
views
Size of forbidden minors for treewidth
For any $k$, the class of graphs of treewidth at most $k$ can be characterized by a finite set of forbidden minors.
For treewidth $1$ and $2$, the set is of size $1$. Then for treewidth $3$, the set ...
- 311
3
votes
2
answers
100
views
Maximum density of a double-node-colored graph
Let $G$ be a graph with the following properties. $C$ is a set of colors. The nodes of $G$ are $C \choose 2$. For any node $v$, the neighborhood of $v$ is rainbow -- that is, for any two nodes $x, ...
- 1,389
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
9
votes
1
answer
2k
views
Bounds for number of edges of a graph, given girth and number of vertices
In reading a paper, I came across an affirmation
"a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
In a previous question I asked in this site about it, I was reffered to a ...
- 193
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
10
votes
0
answers
222
views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
- 986
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
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
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
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
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
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
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
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
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
2
votes
0
answers
134
views
Even cycle constrained edge coloring
Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
- 13.9k
2
votes
0
answers
78
views
Maximum cardinality general factor of a graph
Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
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
8
votes
2
answers
615
views
Embedding of planar graphs
I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
- 83
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
7
votes
2
answers
8k
views
How many simple cycles can a graph with $n$ vertices and $m$ edges have?
I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is $...
- 19.1k
7
votes
2
answers
362
views
Reference request: monochromatic paths in edge-colored complete graphs
Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.
...
- 71
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
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
-1
votes
1
answer
199
views
Maximum degree and matching number
Let $G=(V,E)$ be a finite graph. We write $\nu(G)$ for the matching number of $G$. Is there $\varepsilon > 0$ such that we have $$\frac{\nu(G)+\Delta(G)}{V(G)} \geq \varepsilon$$ for all finite ...
- 48.9k
15
votes
4
answers
639
views
Sets of points containing permutations - a Ramsey-type question
The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
- 711
23
votes
3
answers
3k
views
Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)
Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...
- 986
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
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
25
votes
3
answers
1k
views
Removal of non-isomorphic edges results in the same graph
There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
- 34.4k
6
votes
0
answers
315
views
Algorithms for computing the Resilience of Graphs
The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
- 903
8
votes
1
answer
338
views
Spectral lower bounds on the diameter of a graph
There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...
- 6,962
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