Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with extremal-graph-theory
Search options not deleted
user 2233
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.
4
votes
Complete k-partite graph covers all K_k of a graph
For every graph $G$, the smallest number of complete bipartite subgraphs needed to cover the edges of $G$ is called the biclique covering number, and is denoted by $bc(G)$. The corresponding partitio …
- 32.1k
3
votes
Minimal Non-planar Extensions of a Graph
For a connected example, take a path with 6 vertices. Then, $K_{3,3}$ and $K_5$ together with an additional edge sticking out are both minimal non-planar extensions, again obviously not isomorphic. …
- 32.1k
3
votes
What is the state of the art for the Turán number of $K_{4,4}$?
Here is a near answer. In Turan Numbers of Bipartite Graphs and Related Ramsey-Type Questions, Alon, Krivelevich, and Sudakov prove that $ex(n; K_{s,t}) \leq O(n^{2-1/s})$. They note that this bound …
- 32.1k
3
votes
Accepted
The lower bound of number of vertices covered by maximum matching in $3$-regular graph
The bound $\frac{7}{8}n$ is tight. The example shown below (image courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ …
- 32.1k
5
votes
Accepted
Density of bipartite $d$-degenerate graph
Theorem. A $d$-degenerate $n$-vertex bipartite graph has at most $\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor$ edges if $n < 2d$ and at most $d(n-d)$ edges if $n \geq 2d$. Moreover, both …
- 32.1k
11
votes
Accepted
The maximum number of edges in an even-cycle-free graph with $n$ vertices
The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. …
- 32.1k
2
votes
Accepted
Is there any study on the bounds on the number of even cycles for planar bipartite graphs?
Every $n$-vertex planar graph has at most $O(n^k)$ copies of $C_{2k}$. Note that the bipartite assumption is not needed. A more general result is proven in my paper Subgraph densities in a surface w …
- 32.1k
1
vote
Accepted
On the number of disjoint subsets of a large set families
Your first question is simply asking what is the minimum number of edges an $n$-vertex graph must have to force a matching of size $m$. This number was determined exactly by a classic result of Erdős …
- 32.1k
1
vote
Sets of points containing permutations - a Ramsey-type question
Regarding the weak version, I can prove that there exists an $f$ such that for every two colouring of the $f(n) \times f(n)$ grid, every permutation of $[n]$ is contained in either $B$ or $W$. The pro …
- 32.1k
5
votes
How many simple cycles can a graph with $n$ vertices and $m$ edges have?
To supplement Igor's answer, here is some more information on the maximum number of cycles a graph on $n$ vertices with $m$ edges can have. I apologize that this does not answer your question. Entr …
- 32.1k
1
vote
Accepted
Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$
Out-degree $k-2$ is sufficient to force a directed cycle of length at least $k$. To see this, consider a longest directed path $P:=v_1v_2 \dots v_\ell$. Since $P$ is a longest path and there are no …
- 32.1k
12
votes
Accepted
Existence of triangle-free graphs for regular graphs of degree at most n/2
Yes, it is always possible to find regular triangle-free graphs of any degree up to half the number of vertices (as long as the number of vertices is even). To see this, by Hall's Theorem the edges o …
- 32.1k
6
votes
Accepted
Graph combinatorial optimization problem
The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $ …
- 32.1k
3
votes
Accepted
Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$
This follows from Proposition 2.1 of the paper Many $T$ copies in $H$-free graphs by Alon and Shikhelman.
Theorem (Alon and Shikelman)
Let $T$ be a fixed graph with $t$ vertices. Then $ex(n,T,H)=\Ome …
- 32.1k
2
votes
Clique number of $k$-critical graphs
For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and …
- 32.1k