# 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
Filter by
Sorted by
Tagged with
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 ...
161 views

76 views

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 ...
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 ...
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
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 ...
186 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(...
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&...