Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

Filter by
Sorted by
Tagged with
1
vote
1answer
46 views

Do sparse graphs contain regular pairs?

A corollary of the Szemeredi Regularity Lemma says that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. Could one make ...
1
vote
1answer
51 views

Sum related to Goodman's Formula

Suppose I have a (improper) 2-coloring of $E(K_n)$. Define the graph of all red edges to be $G$ and the graph of all blue edges to be $G'$. Then Goodman's formula says that the total number of ...
0
votes
1answer
53 views

Which graphs $G$ in which any circle is an edge separator maximize $||G||$ for fixed |G|?

Questions Is my solution to the following exercise correct? The exercise gives the following hint: Consider the complement of a spanning tree. How would you come up with that hint yourself? Do you ...
2
votes
2answers
35 views

Show that the size of the Turan graph $T_r(n)$ is at least $(1 - \frac{1}{r}) \binom{n}{2}$.

A Turan graph $T_r(n)$ is defined as the complete $r$-partite graph of order $n$ such that the number of vertices in each of the $r$ classes is either $\lfloor \frac{n}{r}\rfloor$ or $\lceil \frac{n}{...
1
vote
1answer
66 views

Maximum number of edges of a bipartite connected graph with vertex classes of size $n$ and with no perfect matching

At most how many edges can a connected bipartite graph with $n$ vertices in each class can have so that there is no perfect matching? If we omit the connectedness condition, then the maximum is $n(n-1)...
3
votes
0answers
31 views

Largest Independent Sets in Triangle Free Graphs

We know that in a triangle free graph, the set of neighbours for a vertex forms an independent set. One can show that the order of the largest independent set in a graph must be larger than (or equal ...
1
vote
0answers
12 views

Cardinality of the Minimum Feedback Vertex Set of a directed graph

Are nontrivial bounds known for the size of the minimum feedback vertex set of a directed graph in terms of the cardinalities of the edge and/or vertex sets? I've found quite a number of references ...
1
vote
1answer
25 views

In a random graph $G(n,p)$ with $\delta(G) \geq \delta$, how is the event $\{S \subset V \text{ is not a dominating set} \}$ characterized?

This is a problem from my class, with the first part of the solution. I'd like to ask something about the set $S \subset V$ as defined below. Problem: Given $G$ on $n$ vertices with $\delta(G) \geq ...
1
vote
1answer
22 views

Show ex$(n, H)\leq \left\lfloor\frac{n^2+n}{4}\right\rfloor$

Let $H$ be the graph on $4$ vertices with $5$ edges. Show ex$(n, H)\leq \left\lfloor\frac{n^2+n}{4}\right\rfloor$. You have to use that $\sum_{uv\in E(G)}d(u)+d(v)=\sum_{v\in V(G)}d(v)^2$. I know ...
1
vote
1answer
52 views

Extremal graph theory problems

I'm currently working on some assignments, but I'm not getting anywhere. Maybe you can give me some ideas. 1) Show for a graph $G:=(V,E)$ with $n$ vertices and minimum graph degree $$ \delta = \left\...
1
vote
1answer
63 views

Edges on $K_{2,m}$ free graph

Q: Let $G=(V,E)$, such that $|V|=n$. G does not contain as a sub-graph a $K_{2,m}$ - complete bipartite graph which one side contains 2 vertices, and the second $m$ vertices. Prove that that the ...
1
vote
1answer
71 views

Lower bound for number of triangles in simple graph.- very hard exercise

Let $G=(V,E)$ be a graph on $n$ vertices. Let $t(G)$ be a number of triangles in it. Prove that $t(G) \ge |E|\frac{4|E|-n^2}{3n}$ My approach |E| stands for number of edges in graph. For $t(G)=...
2
votes
1answer
66 views

If each edge of a graph $G=(V,E)$ belongs to exactly one triangle then $|E|=\omicron(n^{2})$.

Given $\epsilon > 0$, prove the existence of a $n_\epsilon \in \mathbb{N}$ such that, if $G=(V,E)$ is a graph on $n > n_\epsilon$ vertices, and each edge of $G$ belongs to exactly one triangle, ...
1
vote
1answer
35 views

Simplification of the $\epsilon$-regularity condition in graphs.

Let $G = (V,E)$ be a graph, and let $A,B \subset V$ be two disjoint non-empty sets of vertices, of sizes $a$ and $b$ respectively. Show that in order to check whether or not the pair $(A,B)$ is $\...
2
votes
0answers
44 views

Show that, if girth$(G) \geq g, \text{and } \delta(G) \geq d$, then $|V(G)|= n = \Omega(d^k), \text{where } k = \lfloor \frac{g-1}{2} \rfloor$.

I only have a rough idea, which I would like to have some comments on. Assume $d \geq 3$. Let $v$ be a vertex of $G$. We observe that any path starting from $v$ must have its ending vertex being ...
0
votes
0answers
25 views

A step in the proof of the degree lemma.

I'm reading this proof of the so-called degree lemma, in connection to Szemerédi's Regularity Lemma. In the last part, in the assumption for a contradiction that $|X| \geq \epsilon |C|$, we have $d(X,...
0
votes
0answers
31 views

Let $G$ be the graph on vertex set $[4]$ with edges $12, 13, 14, 23$ (triangle with a tail). Determine the Turán number $ex(n,G)$ for every $n$.

Please give your comment on the solution below. Let $H$ be a graph on $n$ vertices. My observation is that, if $H$ is triangle-free, then $H$ is also $G$-free. The triangle-free graph with the ...
1
vote
1answer
40 views

Parameter $d$ that makes the probability of the graph $G(n,\frac{d}{n})$ being $k$-colorable tends to $0$, as $n \to \infty$ , for $k \leq 2$.

This is an exercise that I'm doing. Let $\epsilon > 0$ and $d > 0$ be fixed. Prove that for $k \geq 2$, if $d \geq (1 + \epsilon)2k(\text{log} k + 1)$, then, $\lim\limits_{n \to \infty} \...
0
votes
0answers
19 views

Show that a 3-uniform hypergraph on $n \geq 5$ points, in which each pair of points occurs in the same (positive) number of edges, is not 2-colorable.

Here a graph is called properly colored if all of its edges contain vertices of different colors. I'm not sure that I understand the construction in the question correctly. It seems to me the ...
1
vote
0answers
33 views

Cups and caps inequality: $f(s,t) \leq {s+t-2 \choose {s-2}}+1$

A sequence of consecutive line segments in $\mathbb{R}^2$ is called a Cap if their slopes are monotonically decreasing, and a Cup if their slopes are monotonically increasing. Let $f(s,t)$ denote the ...
2
votes
2answers
37 views

Given a graph $G$, prove that $m(G) \ge n(G) - c(G) $

Prove that for any given graph $G$, $m(G) \ge n(G) - c(G) $ where $m(G)$ is the number of edges, $n(G)$ is the number of vertices and $c(G)$ is the number of components in $G$. I am not getting how ...
1
vote
1answer
109 views

What additional properties does a finite $k$-partite graph have if the endpoints of every edge have a common neighbor in each independent set?

I've been working through a proof for a while now, and I've come across this class of graphs as the output of the algorithm I'm analyzing, however, I've managed to get absolutely nowhere proving any ...
1
vote
1answer
53 views

For $t \geq 3$, if $n \geq R^{(3)}(t,t)$, then n points in $\mathbb{R}^2$ always contain either t collinear points, or t points in convex position.

Here $R^{(3)}(t,t)$ is the 3-uniform Ramsey number in the two colors red and blue. I'd like to ask for some hints. I've tried giving the 3-sets of $n$ points a meaningful coloring (e.g. red if the 3 ...
1
vote
0answers
49 views

Canonical Ramsey theorem in $m$-uniform setting admits $2^m$ canonical colorings.

This is an exercise I'm doing and I'd like some checking or comments. Given a coloring $c: {\mathbb{N} \choose 3} \to C$, a set $S \subset \mathbb{N}$ is said to be (i) rainbow if no two ...
3
votes
1answer
87 views

Coloring $\mathbb{N}$ with finitely many colors results in monochromatic $x,y,z \in \mathbb{N}$ such that $x+y = z$.

Here are the statements. I have several ideas on how to go about proving them, but I couldn't develop those ideas fully. I'd like to ask for some comments/hints. (i) Show that whenever the natural ...
0
votes
0answers
35 views

Let $H$ be a $k$-uniform hypergraph, for some $k \geq 2$, such that $|e \cap f| \neq 1$ for any two edges $e,f$. Show that $H$ is two-colourable.

This is an exercise I'm doing. Please have a look at my attempted solution below. In our class we define a proper coloring of a graph $H$ is one where none of the edges is monochromatic. Assume for ...
2
votes
2answers
60 views

Maximum clique in intersection graph of $3$-element subsets of a $9$-element set?

How big is the largest collection of $3$-element subsets of $\{1,\ldots,9\}$ such that every pair of sets intersects nontrivially? I have a hard time visualizing the problem, or getting a grip on it....
3
votes
2answers
139 views

Maximum number of cycles of length $4$

If a simple graph has $m$ edges, prove that it has at most $\frac{m^2}{2}$ cycles of length $4$.
0
votes
0answers
20 views

Little and Big O notation in graph theory, Even Circuit Theorem

I would like to ask what is it exactly that means the big and small O in the article about the even circuit theorem. More precisely, the wiki article states: "In extremal graph theory, the even ...
0
votes
0answers
17 views

Proof of canonical Ramsey theorem by colour patterns of $4$-sets.

I'm reading this proof (theorem 1.5) of the canonical Ramsey theorem, which analyses the colour patterns of the subsets of $4$ elements of $\mathbb{N}$. I'd like to ask for some clarification. In ...
0
votes
0answers
31 views

Lower bound of the Ramsey number $R(k,l)$ using probabilistic argument.

I'd like some hints for the following exercise. My guess is that the RHS is the number of vertices of a graph without a red $K_l$ or a blue $K_k$. If we interpret $p$ as the probability that an edge ...
0
votes
0answers
41 views

Deduce the finite Ramsey theorem from the infinite case.

I'd like to ask for some checking of my proof for the statement below. Using the fact that every $\textbf{red/blue}$ colouring of $\mathbb{N} \choose 2$ contains an infinite monochromatic clique, ...
0
votes
0answers
18 views

Recurrent relation on Ramsey hypergraph number: for $k \geq 2, s,t \geq k+1, R^{(k)}(s,t) \leq R^{(k-1)}(R^{(k)}(s-1,t),R^{(k)}(s,t-1))+1 $.

I'd like to ask for some checking on my idea of the proof below, in particular the part marked with (*). In our class, we use the following definition of the Ramsey hypergraph number: Given $k \in ...
2
votes
1answer
96 views

The number of edges when girth is large

For any positive constant $c$, the girth of graph $G$ is at least $cn$, where $n$ is the number of vertices. Show that, the number of edges, $\vert E \vert \leq n + o(n) $. Now I know that we should ...
1
vote
0answers
86 views

For the multicolour Ramsey numbers, prove that $R_r(t_1,t_2,…,t_r) \leq r^{1 + \sum_{i=1}^r (t_i - 1)}$.

I'm trying to imitate the proof below for the symmetric Ramsey numbers $R(s,s) \leq 4^s$, by looking for an appropriately long right-monochromatic sequence in a $r$-color graph on $r^{1 + \sum_{i=1}^r ...
0
votes
0answers
34 views

Extreme points and directions

Consider the space $S$ defined by $S:=\{ (x,y) \mid 2x+y=2,~x,y \geq 0 \}$. Find the extreme points and the extreme direction of $S$. I found that there are two extreme points : $(1,0)$ and $(0,2)$. ...
5
votes
2answers
95 views

Smallest $k$-regular unit-distance graph

We can create arbitrary $k$-regular unit-distance graphs by using a "hyper-cube construction": taking a $k-1$-regular unit-distance graph, making a copy and translating it one unit distance that is ...
1
vote
0answers
18 views

How to interpret the intuitive idea behind Szemerédi regularity lemma?

I'm reading a text discussing Szemerédi regularity lemma. I'm not sure I understand the difference between the quasirandom part and the structured part as stated in the text. Also the analysis of ...
2
votes
2answers
48 views

Prove that the size of a graph is at most $16$

Suppose $G$ has order $7$ and $\chi(G) = 3$. Prove that the size of $G$ is at most $16$. I am really not so sure how to do this problem. This is from a book which teaches some extremal graph theory,...
2
votes
2answers
111 views

What is the maximum number of directed triangles contained in an oriented complete graph?

Assume there are $n$ vertices, every pair of vertices is connected by an arrow. Then how many directed triangles (for example{ $(1,2),(2,3),(3,1)$})does a graph of this type contain at most?
0
votes
0answers
33 views

Extremal graph theory problem - number of cliques in a graph with a given number of edges

Show that for every $\epsilon > 0$ and $k \geq 1$ there is $c = c(\epsilon,k)$ so that any graph with at least $(1-\frac{1}{k} + \epsilon)\frac{n^2}{2}$ edges contains at least $cn^{k+1}$ copies of ...
0
votes
0answers
28 views

Number of special subgraphs of complete graph

Let $n,k$ be natural numbers that $n \ge k$ There is a complete graph $A=K_{n}$. How many are there subgraphs $G$ of $A$, so that every $k$-clique in $A$ has at least one common edge with $G$? Let ...
0
votes
0answers
25 views

Interesting (topological?) topics in extremal graph theory

I am currently taking a course in extremal graph theory and am supposed to pick a topic or a paper (about extremal graph theory, of course; in particular, my teacher wants it to talk about "global ...
1
vote
1answer
87 views

Maximum number of edges in a $k$-connected graph for $k = 2,3$.

What is the maximum number of edges in a $k$-connected (but not $(k+1)$-connected) $n$-vertex graph for $n \geq 6$ and $k = 2,3$? My approach for finding the $\textbf{minimum}$ number of edges was to ...
0
votes
0answers
39 views

Given a tree with n vertices, is there a transformation by which we can get all the trees with n vertices

Given a tree with n vertices, is there a transformation or a series of transformations by which one can get all the trees with n vertices? For example, when $n=4$, there are two non isomorphic trees $...
1
vote
1answer
165 views

Maximum number of edges in minimally $k$-edge-connected multigraph

A graph or multigraph is $k$-edge-connected if it cannot be disconnected by deleting fewer than $k$ edges. It is minimally $k$-edge-connected if it loses this property when any edges are deleted. (...
1
vote
0answers
49 views

Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?

Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints. The answer to Every simple planar graph ...
1
vote
1answer
335 views

Graph with $2n$ vertices and $n^2+1$ edges has at least $n$ triangles

I have the following graph theory problem. Problem. Given a graph $G=(V, E)$ with $|V|=2n$ and $|E|=n^2+1$. Prove that there at least $n$ triangles in graph $G$. Clearly, from Turan's theorem we ...
0
votes
1answer
56 views

Smallest $r$-regular graph with girth at least $n$.

For a reason non-related with graph theory, I need to construct a family of graphs (acyclic, without loops) $\langle G_n:n\in \mathbb{N}\rangle$ satisfying the following: Each $G_n$ is regular (say $...
0
votes
1answer
55 views

Using Turan's theorem to calculate a bound for triangle free graphs.

Using $$ \alpha(G) \ge \frac{n^2}{2\mathbb{E}(G) + n} $$ prove that any graph on n vertices with no triangles has at most $\frac{n^2}{4}$ edges. $\alpha(G)$ is the maximum size of independent ...