All Questions
8 questions
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 13
4
votes
0
answers
113
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., ...
- 557
3
votes
2
answers
276
views
Ramsey-Turán density function is well defined
Define
$$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$
and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as
$$f_l(\alpha)=\lim_{n\to \infty}...
- 227
4
votes
1
answer
230
views
Independence number of $C_4$-free graphs
It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$.
This bound cannot be improved over $\Theta(n^{\...
- 9,501
0
votes
0
answers
153
views
A Non-trivial intersecting set system problem
Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$.
What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are $$\mbox{ subsets }L_1,L_2,\...
user94040
7
votes
2
answers
362
views
Reference request: monochromatic paths in edge-colored complete graphs
Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.
...
- 71
15
votes
4
answers
639
views
Sets of points containing permutations - a Ramsey-type question
The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
- 711
6
votes
2
answers
317
views
Is there a graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free
Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nešetřil and Rödl proved that for every graph $G$, there exists a graph $F$ such that ...
- 61