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

244
questions

0
votes

0
answers

16
views

### Homomorphism density of complete bipartite graph via local Sidorenko

Let $0<p<1$ and $G$ be a graphon with edge density $p$ and $\lVert G-p \rVert_\square\leq1.1p.$
Let $K_{ab}$ be a complete bipartite graph with each part's order $a,b.$ Let $t(K_{ab},G)$ be the ...

0
votes

0
answers

48
views

### Cut norm via power trick

Let $G$ be a graph with vertex set $V$ and edge set $E(G)$, define it's $k$'th power trick as a graph $G^k$ with vertex set $V^k$ and for any $x=(x_1,x_2,\dots , x_k), y=(y_1,y_2,\dots , y_k)\in V^k$, ...

0
votes

0
answers

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

0
votes

0
answers

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

3
votes

1
answer

139
views

### Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?

Does the following holds?
For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as ...

0
votes

0
answers

27
views

### Does there exist a Graph Counting Lemma in the Cut density condition?

Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...

0
votes

0
answers

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

4
votes

1
answer

318
views

### A question related to "Locally Sidorenko" type problem

Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant.
Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...

3
votes

1
answer

68
views

### Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...

4
votes

1
answer

182
views

### Sizes of triangle-free graphs with independence number $k$

A triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. The independence number $α = α(G)$ of a graph $G$ is the cardinality of a maximum in dependent set of ...

4
votes

0
answers

135
views

### "Neighborhood-Bounded" regular graphs

Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $...

0
votes

0
answers

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

2
votes

0
answers

56
views

### Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs,
Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi:
Lemma: For any $\alpha>0$ and a graph $F$, ...

1
vote

1
answer

69
views

### Lower bound for the sum of the number of vertices of some subgraphs of a directed graph

Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$.
Let $C(V_i)$ be the union of ...

1
vote

2
answers

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

0
votes

0
answers

25
views

### From average degree to a highly connected subhypergraph

I'm looking for a result in $k$-uniform hypergraphs analogous to the following result for graphs, due to Mader:
Every graph of average degree $4r$ has a $r$-connected subgraph.

4
votes

1
answer

127
views

### Longest paths and cycles in Steiner triple systems

A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists
of $2t$ cyclically ...

1
vote

1
answer

155
views

### Gentle(-er) Introduction to Erdős–Bollobás's solution to Ramsey–Turán Type Problem

I am currently trying to understand the construction of maximal graph which contains no $K_4$ and sub-linear number of independent points in the graph. The original paper On a Ramsey–Turán type ...

4
votes

0
answers

100
views

### What properties do graphs avoiding large regular subgraphs have?

Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...

3
votes

1
answer

131
views

### Sharp upper bound of the number of edges for graphs of thickness two

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...

2
votes

0
answers

46
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

152
views

### Clique number of $k$-critical graphs

A graph $G$ is called a ${\it{k}}$-${\it{critical}}$ graph if $\chi(G)=k$ and for any proper subgraph $H$ of $G$ we have $\chi(H)<k$， where $\chi(G)$ denotes the chromatic number of $G$. The ...

2
votes

1
answer

173
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

130
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

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

1
vote

2
answers

132
views

### Regarding a specific Turán 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

227
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

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

0
votes

2
answers

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

5
votes

1
answer

104
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

191
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

53
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

244
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

92
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

249
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

199
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

458
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

185
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

70
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

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

4
votes

1
answer

190
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

126
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

174
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

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

10
votes

1
answer

343
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

533
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

452
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

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

4
votes

1
answer

319
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

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