# Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

202 questions
Filter by
Sorted by
Tagged with
0answers
12 views

### Different versions of Szemeredi's Regularity Lemma

I am having a hard time seeing how the statement of Szemeredi's Regularity Lemma used by Tao in this blogpost (Lemma 18) https://terrytao.wordpress.com/2010/11/27/nonstandard-analysis-as-a-completion-...
0answers
41 views

### Gallai partition

Gallai partition for edge coloring Reminder: If G is an edge-coloured complete graph on at least two vertices without a rainbow triangle, there is a nontrivial partition $P$ of $V(G)$ satisfying: (1) ...
0answers
13 views

### Applications of Hamiltonian Decompositions

A Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. What are some applications of Hamiltonian decompositions? In what ways are they important ...
1answer
38 views

### How to understand if task on graph-theory has analytical solution?

Several Top Secret Objects are connected by an underground railway in such a way that each Object is directly connected to no more than k = 3 others, and from each Object you can get underground to ...
1answer
37 views

### Largest matrix satisfying a rank constraint

Consider a matrix with entries in $\{0,1\}$. The matrix is of dimension $R\times N$, where $R$ should be viewed as much larger than $N$. Each row of this matrix has exactly $N/2$ ones and the rest are ...
0answers
20 views

### How to find the optimal value of a function? Given a function and a closed area in parametric form. How can this exercise be solved?

Given the following function: $f(x,y) = x^3 - 3*x^2*y + 3*x*y^2 - y^3$ All the critical points on this curve are asked in the exercise. While calculating this with the code underneath. The Delta-test ...
0answers
17 views

### Understanding edge density bound in extremal graph theory

I am struggling to understand the following statement about extremal graphs: (edge) density is defined to be $\frac{e(G)}{n \choose 2}$, where e(G) is the number of edges in G, and n the number of ...
1answer
51 views

### Random Graph without K3,3 subgraph

Prove there is a constant $c > 0$ s.t. for every sufficiently large n, there exists a graph with n vertices and at least $cn^{3/2}$ edges, but no K3,3-subgraph. Hint: let p be a suitably chosen ...
1answer
23 views

### Maximum number of edges in a 'layered' graph

What is the maximum number of edges in an $n$-vertex, undirected simple graph whose vertex set has been split into $k$ consecutive layers (or subsets), such that the only edges in the graph go between ...
0answers
52 views

### ε-regular pair (A, B) includes $K_{3,3}$ subgraph

Let G consist of just a single ε-regular pair (A, B) of density d > 0, with |A| = |B| = l. Prove that for any d, we have that if ε is sufficiently small and ` is sufficiently large, then we can ...
0answers
8 views

### Proofing that $|EX(n,P_k)|$ = 1

Let $P_k$ be path at size k vertexes , and $EX(n,P_k)$ the group of all unqiue graphs that dosent contain $P_k$ as a sub graph and have maximum amount of edges possible. Need to proof that there is ...
0answers
33 views

1answer
65 views

### Is the class of $k$-letter graphs finitely defined?

I am completely bamboozled by this problem, and although I believe the answer 'should' be yes, I cannot prove it for love nor money! I'll provide a couple of definitions for clarity's sake. A $k$-...
0answers
30 views

### Minimum Feedback Arc Set of Supergraph

Suppose we start from a directed graph $\mathcal{G}=(V,E)$, where $V$ is the set of vertices and $E\subset V \times V$ is the set of edges. Let $F \subset E$ be the solution to the minimum feedback ...
1answer
46 views

### Coloring an intersection graph of lines and a circle

Given a finite set of lines in the plane with no three meeting at a common point, and a circle that contain all intersection points of the lines in its interior, form a graph G whose vertices are the ...
0answers
32 views

1answer
38 views

### Let $(A,B)$ be a bipartition with $|A|=|B|=n$, show that if $\Delta(G)$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular

Suppose $G$ is a bipartite graph with bipartition $(A,B)$ with $|A|=|B|=n$, show that if the maximum degree of $G$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular. So here’s my ...
0answers
68 views

1answer
63 views

### Question about Turán's extremal theorem

I'm doing the exercise 5.10 at page 30 of Wilson's Introduction to Graph Theory. It says: Let $G$ be a simple graph on $2k$ vertices containing no triangles. Show, by induction on $k$, that $G$ has ...
3answers
233 views

1answer
67 views

### Prove that $R(Q_d) \leq 2^{3d}$, where $R(Q_d)$ is the Ramsey number of the $d$-dimensional hypercube $Q_d$.

I want to try a probabilistic proof for this problem. Please give some comments on this attempt at a proof. Let $G$ be our complete graph $K_{2^{3d}}$, with the edges colored red/blue randomly and ...
0answers
49 views

### Integer partition refinement, with minimal refinements

The setup I have two unordered partitions of N - example: 25 = 1 + 1 + 4 + 5 + 14 and 25 = 2 + 11 + 12. On each partitions I can only apply a refinement, which is to further partition one of its ...