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
1
answer
137
views
On the number of disjoint subsets of a large set families
Let $[n] := \{1,\dots,n\}$, for some large integer $n$, and let $\mathcal{F}$ be a family of 2-element subsets of $[n]$.
The famous Erdös-Ko-Rado (EKR) theorem says that if $|\mathcal{F}| > {n - 1 ...
- 43
4
votes
1
answer
205
views
Is there any study on the bounds on the number of even cycles for planar bipartite graphs?
In 1979, Hakimi and Schmeichel [1] initiated such a study by determining the maximum number of triangles and 4-cycles possible in an $n$-vertex planar graph (see also [2] for a small correction).
[1] ...
- 1,851
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
11
votes
1
answer
396
views
Dense triangle-free graphs and their independent sets
Recall that a graph is triangle-free if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities ...
- 3,499
6
votes
5
answers
540
views
Existence of connected set with large edge boundary
Let $\Gamma=(V,E)$ be a finite connected graph.
Pretty standard notation. Given a set $S\subset V$, write $\Gamma|_S$ for the restriction of $\Gamma$ to $S$, i.e., the subgraph $(S,\{\{v,w\}\in E: v,w\...
- 20.2k
6
votes
1
answer
482
views
Average and max. hitting time to a specific vertex
Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes.
Let
$H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
- 73
4
votes
2
answers
269
views
Intuition on inequality in proving a bound on the sum of squares of degrees of a graph
Given a simple connected graph $G$ with $n$ vertices and $m$ edges, let $d_1, ..., d_n$ denote the degrees of the vertices of the graph. In this very short paper, the author prove the inequality
$$\...
- 662
4
votes
1
answer
366
views
The upper bound of edges of the generalized cactus graphs
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple ...
- 1,851
5
votes
0
answers
156
views
$K_4$ or n vertices without triangles
For which minimal $m(n)$ any graph on $m$ vertices contains either a complete subgraph on 4 vertices $K_4$ or $n$-vertices subgraph without triangles? I know a quadratic upper bound $2n^2$, but I am ...
- 115
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
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
8
votes
0
answers
305
views
Maximum number of cycles on regular graphs
Let $G$ be a $d$-regular graph on $n$ vertices. I'm interested in upper bounds on the number of cycles of length $k$ that hold for any such $G$. The regime I'm interested in is:
$d$ is fixed, and $...
- 133
7
votes
0
answers
152
views
Inequality of product of discrete cosines
Let $k,a,b,c$ be odd positive integers. Consider the following inequality:
$$
\sum_{x,y \in [k]} \cos^a\bigg(\frac{2\pi}{k}\cdot x\bigg) \cdot \cos^b\bigg(\frac{2\pi}{k}\cdot y\bigg) \cdot \cos^c\bigg(...
- 71
1
vote
2
answers
419
views
Graphs constructed from sums of perfect matchings
Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.
Let $V$ be the set of vertices of cardinality $|V|=2n$ and let $\mathcal{...
- 965
4
votes
1
answer
195
views
Explicit constructions of regular graphs with very sparse induced subgraphs
Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...
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
4
votes
0
answers
102
views
Connected sets with large boundary in a multigraph
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
2
votes
1
answer
210
views
3-uniform tetrahedron-free hypergraph on seven vertices
My problem concerns 3-uniform hypergraphs. Let $f(n)$ be the maximal number of edges in a 3-uniform hypergraph such that no four edges form a "tetrahedron", i.e., four edges that join the ...
- 2,811
4
votes
0
answers
257
views
Graphs with high girth and low diameter
As the title says, I'm interested in graphs with high girth and low diameter.
Given a class $\Gamma$ of finite $k$-regular graphs, call a $\Gamma$-graph GD-extremal if every $\Gamma$-graph either has ...
- 3,612
2
votes
0
answers
36
views
Is homomorphism density of partially labeled graph continuous with respect to cut metric
Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
- 371
5
votes
1
answer
171
views
Graph combinatorial optimization problem
Let $G$ be a simple graph with vertex set $V$, such that for any two vertices $u,v\in V$, we have at least $k$ edge-disjoint paths of length $2$ (i.e., formed by $2$ edges) connecting $u$ with $v$. ...
- 1,677
1
vote
1
answer
165
views
Combinatorial graph optimization problem on integer adjacency matrices
We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.
Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\...
- 1,677
2
votes
1
answer
237
views
The lower bound of number of vertices covered by maximum matching in $3$-regular graph
Let $G$ be a $3$-regular graph (cubic graph) with order $n$.
From here, the lower bound of # of vertices covered by maximum matching in $G$ is $\frac{3}{4}n$.
And from here, the lower bound is $\frac{...
- 341
2
votes
1
answer
392
views
Maximum number of leaf blocks in 3-regular (cubic) graph
The definition of block is
Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.
Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in ...
- 341
3
votes
2
answers
276
views
Ramsey-Turán density function is well defined
Define
$$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$
and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as
$$f_l(\alpha)=\lim_{n\to \infty}...
- 227
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 ...
2
votes
0
answers
64
views
Two conjectures on a special type of graph
I want to analyze a special type of weighted directed graph where out degrees is equal to in degrees at each vertex.
$n \in Z$ and $n \geq 3$ ,
Set
$x_n=\left(1,1,\dots,1\right)^T \in \mathbb{R}^{n}...
- 89
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
2
votes
0
answers
61
views
Beurling’s extremality criterion for curves: two versions
I see Beurling’s extremality criterion at two places: the proof is almost identical, but the statement is very different. Below,
$$
\ell_\rho (\gamma) = \int_\gamma \rho(z) |dz|.
$$
"Extremal&...
- 1,755
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
3
votes
1
answer
139
views
Turán density of an unbalanced complete $r$-partite $r$-graph
In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following:
Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ ...
- 131
4
votes
2
answers
2k
views
The number of monochromatic triangles
It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula
$$M(n)=\binom n3-\left\lfloor\frac n2\...
- 13.4k
10
votes
2
answers
452
views
Conjecture on minimum size of graph
Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
- 225
4
votes
3
answers
432
views
How to show that random graphs cannot be embedded with short edges
For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio
$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
- 9,720
2
votes
2
answers
273
views
Number of edge-disjoint cycles in a holey graph
Let $\Gamma$ be a connected graph with $H^1(\Gamma) \cong \mathbb{Z}^d$. Can we give a lower bound (preferably of the form $\gg d$) on the maximal number of edge-disjoint cycles one can find in $\...
- 20.2k
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
2
votes
1
answer
155
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
- 1,677
2
votes
0
answers
108
views
What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph
By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
- 1,190
2
votes
0
answers
55
views
Expectation of Hadwiger number of a random graph
For any integer $n$, let ${\cal G}_n$ denote the set of simple, undirected graphs $G = (V, E)$ where $V = \{1,\ldots,n\}$. The Hadwiger number $\eta(G)$ of a finite graph $G$ is the maximum integer $m$...
- 48.9k
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
6
votes
2
answers
426
views
Snake algorithm that minimizes straight lines
How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself?
Here's an example we have ...
- 61
3
votes
1
answer
174
views
Minimum size of regular graph with no short cycles
For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we ...
- 284
13
votes
2
answers
597
views
Graph in which no cycle has two crossing chords
Let $G$ be a graph which does not contain a simple cycle $v_1\ldots v_k$ and two "crossing" chords $v_iv_j$ and $v_pv_q$, $i<p<j<q$. An example of such graph is a triangulation of ...
- 109k
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
17
votes
3
answers
464
views
Graph that minimizes the number of b/w colorings where white vertices have an odd number of black
motivated from a physical context, we are currently interested in the following graph coloring problem:
Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white ...
- 323
2
votes
1
answer
114
views
Smallest size of graph covered by infinite tree
Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed)...
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
16
votes
1
answer
596
views
Spanning trees: the last darn $1/4$
Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991),
if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning
tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
- 20.2k
7
votes
0
answers
177
views
Szemerédi's regularity lemma for binary operations
Szemerédi's regularity lemma is an approximate structure theorem for
all large graphs (symmetric binary relations). There are versions for
multicolored graphs and directed graphs. Is there an ...
- 50.8k