# 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.

219
questions

2
votes

0
answers

40
views

### Size of set of positive integers no sum of two distinct elements giving square

Question: find the size of a maximal subset $A$ of $[n]=\{1,\cdots,n\}$ satisfying that for any distinct elements $x,y\in A$, $x+y$ is not a perfect square.
Consider a graph with $n$ vertices: $x$ and ...

2
votes

1
answer

161
views

### Discrete maximization of geometric mean - reference request

This is a follow-up to my previous MO question:
A discrete optimization problem related to the AM-GM inequality
Let $n,k$ be integers such that $1\le k\le n$. Define the quantity
$$
P(n,k):=\max\ a_1\...

2
votes

1
answer

113
views

### Turán density of hypergraphs with very few edges

As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...

4
votes

1
answer

91
views

### Are there decompositions of $K_{16}$ by certain 3-regular graphs?

This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering:
Can the (edges ...

0
votes

0
answers

39
views

### Regarding a specific Turan number of graphs

I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can ...

4
votes

0
answers

200
views

### Weight transfer proof of Turán’s theorem

Turán’s theorem, which states that a $K_{p+1}$-free graph contains at most $(1-1/p)\frac{N^2}{2}$ edges, can be proven in many different ways, as pointed out, for example in M. Aigner, G. M. Ziegler, ...

1
vote

1
answer

109
views

### Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$

I know that it must be a simple consequence of the Kővári–Sós–Turán (and Erdős–Stone) theorem, but I am struggling to formulate a proof: Let $H$ be a fixed-size $r$-chromatic graph. Then there exists $...

1
vote

1
answer

215
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 ...

0
votes

0
answers

131
views

### A question about Jacob Fox's graph removal lemma

I have a question about the paper "A new proof of the graph removal lemma" by Jacob Fox.
I will preface this by saying I've looked around in papers citing this paper and couldn't find an ...

5
votes

1
answer

101
views

### Maximal graphs with a property that is invariant w.r.t. vertex removal

Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$.
Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...

5
votes

1
answer

122
views

### Cover a graph with small size complete graphs

Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$:...

0
votes

0
answers

46
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 ...

2
votes

1
answer

191
views

### Union closed family of sets with at most a certain number of couples of sets with non-empty intersection

Is it possible to find a union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, such that there are at most:
$$\left(1-\frac{1}{\left\lfloor \frac{n-1}{2} \...

3
votes

0
answers

76
views

### Harper's theorem on the general Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is
$$ \min_{S\subseteq ...

3
votes

0
answers

185
views

### Behrend's construction vs. Triangle removal lemma

I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand.
Theorem 2.3.1 (Triangle removal lemma) For all $\...

6
votes

1
answer

156
views

### Graphs without short cycles and with linear number of edges

Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C_3, C_4, \ldots, C_{f(n)})$-free, i.e. $G$ contains ...

4
votes

1
answer

453
views

### Turán's theorem for cosets of groups

Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...

10
votes

0
answers

160
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 ...

1
vote

0
answers

68
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 $...

2
votes

0
answers

47
views

### A variant of the regularity lemma that depends on the number of vertices

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side.
For sets $X \subseteq U$ and $Y \subseteq V$,
let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...

5
votes

1
answer

104
views

### Quasi-random vs pseudo-random graphs

My question is somehow concerning terminology on extremal graph theory.
Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...

4
votes

1
answer

109
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 ...

4
votes

1
answer

137
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] ...

0
votes

0
answers

132
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 ...

9
votes

1
answer

248
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 ...

6
votes

5
answers

527
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\...

6
votes

1
answer

364
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$, ...

4
votes

2
answers

250
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
$$\...

3
votes

0
answers

198
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 ...

5
votes

0
answers

129
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 ...

0
votes

0
answers

239
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 ...

1
vote

0
answers

76
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 ...

8
votes

0
answers

186
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 $...

7
votes

0
answers

136
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(...

1
vote

2
answers

291
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{...

4
votes

1
answer

156
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:=\...

1
vote

1
answer

113
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: \...

4
votes

0
answers

98
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: \...

2
votes

1
answer

142
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 ...

4
votes

0
answers

171
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 ...

1
vote

0
answers

21
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) ...

5
votes

1
answer

168
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
vote

1
answer

148
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:=\...

2
votes

1
answer

172
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{...

3
votes

2
answers

249
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}...

0
votes

1
answer

126
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

61
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}...

0
votes

0
answers

21
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(...

2
votes

0
answers

60
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&...